快速排序（Hoare&Lomuto）及其多种优化
快速排序（Hoare&Lomuto）及其多种优化
快速排序是一种高效的排序算法，由英国计算机科学家托尼·霍尔（Tony Hoare）在1960年提出。它使用分治法（Divide and Conquer）来将一个大数组分成两个子数组，然后递归地排序这两个子数组。本文将详细介绍快速排序的基本思想、实现方法、复杂度分析以及多种优化策略。
一、快速排序基本思想
1.什么是快速排序
快速排序（Quicksort）是一种高效的排序算法，是对于冒泡排序的改进，与冒泡排序同属于交换排序的范畴。它使用分治法（Divide and Conquer）来将一个大数组分成两个子数组，然后递归地排序这两个子数组。
2.实现思路
（1）找到基准（Pivot）
快速排序的精髓就在于将数组头部的数（begin）看作基准（pivot），设置基准以后用来作为分治两个小数组的分界点。
（2）分区（Partitioning）（快速排序的核心）
两种方案
<1>Lomuto分区方案（前后指针法）
使用一个 j 来记录从begin到end向后遍历的位置。
向后遍历的时候，与数列最左边的基准（pivot）作比较。
如果比基准要大，则位置不变。
如果比基准要小，则将j的位置和i+1交换（i是记录了小于等于pivot的数据的最后一个位置）
遍历到最后将pivot与i交换可以用pivot区分出两个新的小数组，达到了分区（partition）的目的。
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int left, int right) {
int pivot = arr[right]; // 选择最右边的元素作为基准
int i = left - 1; // i 是小于等于基准的子数组的最后一个元素的索引
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]); // 交换元素
}
}
swap(&arr[i + 1], &arr[right]); // 将基准元素放到正确的位置
return i + 1;
}
void quicksort(int arr[], int left, int right) {
if (left < right) {
int pi = partition(arr, left, right); // 分区索引
quicksort(arr, left, pi - 1); // 递归排序基准左侧的子数组
quicksort(arr, pi + 1, right); // 递归排序基准右侧的子数组
}
}
<2>Hoare分区方案（类似挖坑法）
设置left和right分别代表了数组头尾数据的下标，left由begin向end向右遍历，right由end想begin向左遍历
内层循环：
先走left，如果遍历到的数小于等于pivot，则往后遍历，如果遇到比pivot大的数，则暂停遍历，开始走right，如果遇到大于等于pivot的数，则向前遍历，如果遇到比pivot小的数，则暂停遍历。
交换left和right的位置
外层循环：
继续重复上面内层循环找数的过程，直到left和right相遇，交换pivot和left。
（交换pivot和left的原因：先走的left遍历，最后一定会停在小于等于pivot的数上面）
（3）递归（Recursive）
然后就是递归，我们再区分开小数组之后，对于小数组还可以用新的pivot再区分，一直递归下去，画出递归展开图我们会发现形似二叉树的结构。直到每个 小数组都被排序好，整个快速排序就完成了
二、hoare法经典快速排序代码实现
这里我们的pivot用keyi表示，根据上面提供的思路，相信大家也可以轻而易举地写出下面的代码。
//快速排序
//目的是在一趟快排中找到我们key的对应位置
void QuickSort(int* a, int begin,int end) {
if (begin >= end) {
return;
}
int left = begin, right = end; //left=begin可以保证在递归到还剩下两个数的时候，left会与keyi也就是自己交换
int keyi = begin;
while (left < right) {
while (left<right && a[right] >= a[keyi]) {
right--;
}
while (left<right && a[left] <= a[keyi]) {
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
keyi = left;
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
三、快速排序复杂度分析
1.hoare分区方案复杂度
（1）时间复杂度
最优时间复杂度（O(n log n)）： 在最优情况下，每次分区将数组大致平分，递归深度为log n。 每层递归需要线性时间 O(n) 来进行分区操作。 因此，最优情况下的总时间复杂度为 O(n log n)。
最坏时间复杂度（O(n^2)）： 在最坏情况下，每次分区选择的枢轴是当前数组的最大或最小值，导致分区极度不平衡。 这种情况下，递归深度为 n，每层递归仍然需要 O(n) 的时间。 因此，最坏情况下的总时间复杂度为 O(n^2)。
平均时间复杂度（O(n log n)）： 在平均情况下，分区大致将数组分为相等的两部分，递归深度为 log n。 每层递归需要 O(n) 的时间。 因此，平均情况下的总时间复杂度为 O(n log n)。
（2）空间复杂度
递归调用栈： 在最优情况下，递归深度为 log n，因此空间复杂度为 O(log n)。 在最坏情况下，递归深度为 n，因此空间复杂度为 O(n)。
辅助空间： Hoare分区方案是原地排序算法，不需要额外的辅助数组，因此辅助空间复杂度为 O(1)。
2.比较Lomuto方案和Hoare方案
Lomuto分区方案：
使用单个指针
i
来管理分区。代码实现简单，但在处理重复元素时可能效率较低。
更适合教学和理解快速排序的基本概念。
Hoare分区方案：
使用两个指针
left
和
right
来进行分区。通常效率更高，尤其是在处理大量重复元素时。
实现稍微复杂一些，但实际应用中更常用。
四、可快速排序的优化
接下来的代码我将只给出partition的实现。
1.hoare法的局限性
（1）枢轴的选择
枢轴的选择如果刚好平衡时间复杂度和空间复杂度分别可以达到最好的O（NlogN）/ O（logN）
但如果遇到最坏的情况，枢轴在头或者尾，时间复杂度和空间复杂度就会很高，体现不出快排的优势
（2）递归/交换的小题大做
在递归到尾部的时候，接着递归会多开出栈空间，影响性能，同时做不必要的交换也是了浪费快速排序的性能。
（3）不稳定性
在之前我们讲到不稳定性带来的部分场景的不适用，这是快排的原理使然，无法改变。
2.优化选取枢轴
由于上面所说，枢轴的位置决定了快速排序的性能，我们如何让每次分区都接近二分以达到平衡从而提升性能。
三数取中法：选取数组前、中、后三点的数据，取其平均值，将midi作为pivot，则海洋可以大致二分数组。
//优化选取枢轴
int GetMidi(int* a, int begin, int end)
{
int midi = (begin + end) / 2;
// begin midi end 三个数选中位数
if (a[begin] < a[midi]){
if (a[midi] < a[end])
return midi;
else if (a[begin] > a[end])
return begin;
else
return end;
}
else {// a[begin] > a[midi]
if (a[midi] > a[end])
return midi;
else if (a[begin] < a[end])
return begin;
else
return end;
}
}
//快速排序的本质就是将key元素插入到指定位置
int Partition(int* a, int begin, int end){
int midi = GetMidi(a, begin, end);
Swap(&a[midi], &a[begin]);
int left = begin, right = end;
int keyi = begin;
while (left < right){
// 右边找小
while (left < right && a[right] >= a[keyi]){
--right;
}
// 左边找大
while (left < right && a[left] <= a[keyi]) {
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
return left;
}
3.优化不必要交换
（1）插入排序优化小数组时排序方案
在排序区间太小的时候，快速排序有些大材小用，用插入排序可以解决这个问题。
if (end - begin + 1 <= 10){
InsertSort(a + begin, end - begin + 1); //小区间优化，插入排序对于小区间有序数据非常有效
}
（2）挖坑法
从右向左扫描，找到第一个小于枢轴的元素，将其放入左指针指向的坑中；从左向右扫描，找到第一个大于枢轴的元素，将其放入右指针指向的坑中。
// 挖坑法---对于hoare法的优化
int Partition(int* a, int begin, int end){
int midi = GetMidi(a, begin, end);
Swap(&a[midi], &a[begin]);
int key = a[begin];
int hole = begin;
while (begin < end){
// 右边找小，填到左边的坑
while (begin < end && a[end] >= key){
--end;
}
a[hole] = a[end];
hole = end;
// 左边找大，填到右边的坑
while (begin < end && a[begin] <= key){
++begin;
}
a[hole] = a[begin];
hole = begin;
}
a[hole] = key;
return hole;
}
4.优化递归
（1）优化尾递归
递归操作对于性能由影响，当函数到达尾部的时候递归会耗费一定的栈空间，如果可以减少递归次数，就可以提升性能。优化尾递归，我们采用迭代而不是递归的方法可以缩减对战深度，提升整体性能。
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void QuickSort(int arr[], int low, int high) {
while (low < high) {
int pi = partition(arr, low, high);
// 优先处理较小的子数组
if (pi - low < high - pi) {
optimized_quicksort(arr, low, pi - 1);
low = pi + 1;
} else {
optimized_quicksort(arr, pi + 1, high);
high = pi - 1;
}
}
}
（2）非递归实现快速排序
同样，非递归的方法也可以减少栈空间消耗，我们使用栈来存储原来数组的数据，和原来递归快排的实现原理相同，用栈存储数据同样可以达到分区的效果，每次取出栈顶的前两个元素，用来获取pivot分界点，再入栈。
//非递归快速排序 要结合递归法来看 递归方法传的数据位置和非递归如出一辙
void QuickSortNonR(int* a, int begin, int end){
ST s;
StackInit(&s);
StackPush(&s, end);
StackPush(&s, begin);
while (!StackEmpty(&s)){
int left = StackTop(&s); //入栈，从栈顶元素提取left
StackPop(&s);
int right = StackTop(&s);
StackPop(&s);
int keyi = PartSort3(a, left, right);
// [left, keyi-1] keyi [keyi+1, right]
if (left < keyi - 1) {
StackPush(&s, keyi - 1);
StackPush(&s, left);
}
if (keyi + 1 < right){
StackPush(&s, right);
StackPush(&s, keyi + 1);
}
}
StackDestroy(&s);
}
五、总结
在所有排序算法中，快速排序算是最具有影响力，应用范围最广的一种了。