目录
11.5 快速排序
快速排序（quick sort）是一种基于分治策略的排序算法，运行高效，应用广泛。
快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。具体来说，哨兵划分的流程如图 11-8 所示。
- 选取数组最左端元素作为基准数，初始化两个指针
i和j分别指向数组的两端。 - 设置一个循环，在每轮中使用
i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素。 - 循环执行步骤
2.，直到i和j相遇时停止，最后将基准数交换至两个子数组的分界线。
图 11-8 哨兵划分步骤
哨兵划分完成后，原数组被划分成三部分：左子数组、基准数、右子数组，且满足“左子数组任意元素 ≤ 基准数 ≤ 右子数组任意元素”。因此，我们接下来只需对这两个子数组进行排序。
快速排序的分治策略
哨兵划分的实质是将一个较长数组的排序问题简化为两个较短数组的排序问题。
quick_sort.c
/* 元素交换 */
void swap(int nums[], int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
/* 哨兵划分 */
int partition(int nums[], int left, int right) {
// 以 nums[left] 为基准数
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left]) {
j--; // 从右向左找首个小于基准数的元素
}
while (i < j && nums[i] <= nums[left]) {
i++; // 从左向右找首个大于基准数的元素
}
// 交换这两个元素
swap(nums, i, j);
}
// 将基准数交换至两子数组的分界线
swap(nums, i, left);
// 返回基准数的索引
return i;
}
11.5.1 算法流程
快速排序的整体流程如图 11-9 所示。
- 首先，对原数组执行一次“哨兵划分”，得到未排序的左子数组和右子数组。
- 然后，对左子数组和右子数组分别递归执行“哨兵划分”。
- 持续递归，直至子数组长度为 1 时终止，从而完成整个数组的排序。
图 11-9 快速排序流程
quick_sort.c
/* 快速排序 */
void quickSort(int nums[], int left, int right) {
// 子数组长度为 1 时终止递归
if (left >= right) {
return;
}
// 哨兵划分
int pivot = partition(nums, left, right);
// 递归左子数组、右子数组
quickSort(nums, left, pivot - 1);
quickSort(nums, pivot + 1, right);
}