C 语言快速排序详解与多种优化变式
前言
在掌握了希尔排序和插入排序之后,我们继续探索更高效的排序算法。今天重点讲解被广泛集成于标准库中的快速排序(Quick Sort)。本文将从基础实现入手,逐步深入到三数取中、小区间优化以及非递归实现,帮助读者全面理解其核心逻辑。
一、快速排序(初阶)
1. 算法思想
快速排序的核心在于分治策略。选取一个基准值(Key),将数组分为两部分:左侧所有元素小于 Key,右侧所有元素大于 Key。此时 Key 的位置已确定,后续只需对左右两个子区间递归执行相同操作,直到区间不可再分。
2. 实现思路
(1)定 Key 值
初始阶段,通常选择第一个元素作为基准值(后续会讨论优化方案)。
(2)大小交换
使用双指针法:
- 右指针从右向左移动,寻找比 Key 小的值。
- 左指针从左向右移动,寻找比 Key 大的值。
- 当两指针均停下时,交换对应位置的值。
(3)循环与分割
重复上述过程直到两指针相遇。将 Key 与相遇点交换,完成一次分区。随后递归处理左右区间。
3. 实现代码
void QuickSort1(int* a, int left, int right) {
if (left >= right) {
return;
}
int key = left; // 确定 key 的值,为第一个元素
int L = left;
int R = right; // 记录原始左右下标
while (left < right) {
// 右小人向左走,直到找到比 key 小的值
while (left < right && a[right] >= a[key]) {
right--;
}
// 左小人向右走,直到找到比 key 大的值
while (left < right && a[left] <= a[key]) {
left++;
}
Swap(&a[left], &a[right]); // 交换大的值和小的值
}
Swap(&a[right], &a[key]); // 最后交换 key 和相遇点对应的值
key = right; // key 的下标也要改变
QuickSort1(a, L, key - 1); // 递归 key 的左区间
QuickSort1(a, key + 1, R); // 递归 key 的右区间
}


