快速排序的基本思路¶
快速排序是一种高效的排序算法，它基于“分而治之”的思想。简单来说，就是先从数组中选一个元素作为“基准值”（pivot），然后把数组分成两部分：一部分所有元素都比基准值小，另一部分所有元素都比基准值大。接着，对这两部分分别递归地应用快速排序，直到整个数组有序。
分区过程详解¶
分区是快速排序的核心步骤，我们通过一个例子来理解它：
假设数组为 [5, 3, 8, 4, 2, 7, 1, 6]，我们选第一个元素 5 作为基准值。分区过程如下：
- 初始化指针：
left指向数组左侧（初始为0，对应元素5），right指向数组右侧（初始为7，对应元素6）。 - 移动指针：
- 先移动right指针，直到找到比基准值小的元素。这里right从7开始，元素6>5，左移到6（元素1），1<5，停止移动。
- 再移动left指针，直到找到比基准值大的元素。left从0开始，元素5是基准，左移到1（元素3），3<5，继续左移到2（元素8），8>5，停止移动。
- 交换元素：交换left（2）和right（6）的元素，数组变为[5, 3, 1, 4, 2, 7, 8, 6]。 - 重复过程：继续移动指针，直到
left >= right。最终left和right会在中间位置（此时left=right=4），交换基准值（位置0）和left位置的元素，得到分区结果：[2, 3, 1, 4, 5, 7, 8, 6]。
此时，基准值 5 左边的元素（[2, 3, 1, 4]）都小于5，右边的元素（[7, 8, 6]）都大于5。
Python代码实现¶
分区函数（partition）¶
分区函数的作用是确定基准值的最终位置，并将数组分为左右两部分：
def partition(arr, low, high):
pivot = arr[low] # 选择第一个元素作为基准值
left = low # 左指针
right = high # 右指针
while left < right:
# 右指针向左移动，直到找到比基准值小的元素
while left < right and arr[right] > pivot:
right -= 1
# 左指针向右移动，直到找到比基准值大的元素
while left < right and arr[left] < pivot:
left += 1
# 交换左右指针指向的元素
if left < right:
arr[left], arr[right] = arr[right], arr[left]
# 将基准值放到最终位置（left=right处）
arr[low], arr[left] = arr[left], arr[low]
return left # 返回基准值的索引
快速排序函数（quick_sort）¶
递归调用分区函数，对左右子数组分别排序：
def quick_sort(arr, low, high):
if low < high: # 递归终止条件：子数组长度为1或0时停止
# 分区，获取基准值位置
pivot_index = partition(arr, low, high)
# 递归排序左子数组（基准值左侧）
quick_sort(arr, low, pivot_index - 1)
# 递归排序右子数组（基准值右侧）
quick_sort(arr, pivot_index + 1, high)
测试代码¶
# 测试快速排序
arr = [5, 3, 8, 4, 2, 7, 1, 6]
n = len(arr)
quick_sort(arr, 0, n - 1)
print("排序后的数组：", arr) # 输出：排序后的数组： [1, 2, 3, 4, 5, 6, 7, 8]
代码解释¶
- 基准值选择：我们选数组第一个元素作为基准值（也可随机选择，避免极端情况）。
- 分区逻辑：通过左右指针
left和right遍历数组，交换不满足条件的元素，最终让基准值左边都是小于它的元素，右边都是大于它的元素。 - 递归终止条件：当
low >= high时，子数组长度为1或0，已经有序，无需排序。
复杂度分析¶
- 时间复杂度：平均情况下为 O(n log n)（每次分区将数组分为大致相等的两部分，递归深度为 log n，每层分区需遍历 n 个元素）。
- 最坏情况：若数组已排序且每次选第一个元素为基准，时间复杂度退化为 O(n²)（可通过随机选基准优化）。
总结¶
快速排序通过“分治+递归”的思想，高效地对数组进行排序。核心是分区过程：选基准、调整元素、递归处理子数组。它是实际应用中最常用的排序算法之一，理解其原理和实现对掌握排序算法至关重要。
通过本文的例子和代码，你可以逐步理解快速排序的执行过程，并尝试修改基准值选择方式（如随机选基准）来优化算法。