快速排序是目前实际工程中最常用、综合效率最高的通用排序算法，由图灵奖得主 Tony Hoare 在 1960 年提出。
快速排序的核心思想为“分治法 + 挖坑填数”，思路如下：
（1） 选一个基准数（pivot）
（2）把数组分成两部分：
左边：全部 ≤ 基准
右边：全部 ≥ 基准
（3）对左右两部分递归重复上述过程
（4）直到所有区间长度为 1（自然有序）
以 [5, 1, 9, 3, 7, 2, 8] 为例
（1）选基准，通常选：第一个元素、最后一个元素、中间元素或者随机元素（避免最坏情况），这里选第一个 5 作为基准。
（2）分区（partition）
比 5 小的放左边
比 5 大的放右边
一轮分区后可能变成：[2, 1, 3, 5, 7, 9, 8]
（3）递归：对左边 [2,1,3] 和右边 [7,9,8] 分别再做快速排序。
（4）结束：当子数组只有 0 或 1 个元素时，递归终止，整体有序。
完整过程如下：
[2, 1, 3, 5, 7, 9, 8] 选择 5 为基数 → [2, 1, 3] 5, [7, 9, 8]，继续对 [2, 1, 3] 和 [7, 9, 8] 进行快速排序：
[2, 1, 3] 选择 2 为基数 → [1] 2, [3]
[7, 9, 8] 选择 7 为基数 → 7, [9, 8]
排序完成后，数组内容为 [1] 2, [3] 7, [9, 8]，继续对 [9,8] 进行快速排序：
[9, 8] 选择 9 为基数 → [8], 9
最后，把所有有序片段按顺序拼接：
[1,2,3] + [5] + [7] + [8,9] = [1, 2, 3, 5, 7, 8, 9]
此时，数组排序已完成。
下面是通过 Python 实现的快速排序：
def quick_sort(arr):
# 递归终止条件：数组长度 <=1 已经有序
if len(arr) <= 1:
return arr
# 选择基准（这里选中间元素，比选首尾更稳定）
pivot = arr[len(arr) // 2]
# 分区
left = [x for x in arr if x < pivot] # 小于基准
middle = [x for x in arr if x == pivot]# 等于基准
right = [x for x in arr if x > pivot] # 大于基准
# 递归 + 合并
return quick_sort(left) + middle + quick_sort(right)
# 测试
if __name__ == "__main__":
test_arr = [5, 1, 9, 3, 7, 2, 8, 6]
print("原始数组:", test_arr)
sorted_arr = quick_sort(test_arr)
print("排序结果:", sorted_arr)运行结果：
原始数组: [5, 1, 9, 3, 7, 2, 8, 6]
排序结果: [1, 2, 3, 5, 6, 7, 8, 9]
川公网安备51010802032098