快速排序（Quick Sort）

# /*
# 快速排序（Quick Sort）
# --------------------------------------------------------
# 原理：
# “分而治之”思想的经典代表。
# 通过选择一个基准值 pivot，将序列划分为：
#       小于 pivot 的一部分
#       大于 pivot 的一部分
# 对左右部分继续递归排序，最终组合成有序序列。
#
# 因为每次都能把序列分成更小的部分，因此平均效率非常高。
# */

def quick_sort(arr):
    # 当序列长度为 0 或 1 时，天然有序
    if len(arr) <= 1:
        return arr

    pivot = arr[0]              # 选第一个元素作为基准
    left = [x for x in arr[1:] if x <= pivot]   # 小于等于 pivot
    right = [x for x in arr[1:] if x > pivot]   # 大于 pivot

    # 递归排序左右两侧，再合并
    return quick_sort(left) + [pivot] + quick_sort(right)


# 示例演示
data = [10, 7, 8, 9, 1, 5]
print("排序前：", data)
result = quick_sort(data)
print("排序后：", result)

# --------------------------------------------------------
# 关键要点总结：
# 1) 基于“分治思想”推进排序；
# 2) 通过 pivot 把序列分成左右两部分；
# 3) 对左右子序列递归排序；
# 4) 平均时间复杂度 O(n log n)，最坏可达 O(n²)；
# 5) 不稳定排序；
# 6) 是实际应用中最常用、性能极高的排序算法之一。
# */

# 排序前： [10, 7, 8, 9, 1, 5]
# 排序后： [1, 5, 7, 8, 9, 10]