当前位置：首页 > news >正文

【排序算法】⑥快速排序：Hoare、挖坑法、前后指针法

news 2025/8/12 14:50:32

系列文章目录

第一篇：【排序算法】①直接插入排序-CSDN博客

第二篇：【排序算法】②希尔排序-CSDN博客

第三篇：【排序算法】③直接选择排序-CSDN博客

第四篇：【排序算法】④堆排序-CSDN博客

第五篇：【排序算法】⑤冒泡排序-CSDN博客

第六篇：【排序算法】⑥快速排序：Hoare、挖坑法、前后指针法-CSDN博客

第七篇：【排序算法】⑦归并排序-CSDN博客

目录

系列文章目录

前言

一、快排思想

二、以Hoare算法为核心实现快排

1.三数取中函数

2.经典Hoare快排

细节：为什么左做key，内循环一定要右边先找？

完整代码框架

优化快排

三、算法拓展

挖坑法

前后指针法

四、分析快速排序

总结

前言

快速排序是当前最常用到的排序算法，快速排序整体的综合性能和使用场景都是较优的，所以才敢叫快速排序。

本文以经典Hoare快排算法为主，并结合其他函数先为读者展现一个完整的快排代码框架，之后再介绍挖坑法与前后指针法。

一、快排思想

快速排序是Hoare于上世纪60年代提出的一种类似二叉树结构的交换排序方法，其基本思想为：

任取待排序元素数组中的某元素作为基准值，按照该基准值将待排序集合分割成两子序列，使左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

该算法的实现有递归与非递归两种方式，非递归方式需要用到自定义数据结构“栈”，因此本文用较为简单的递归方式为例介绍。

// 假设按照升序对a数组中[left, right]区间中的元素进行排序
void QuickSort(int* a, int left, int right)
{if (left >= right)return;if (!a)return;int div = PartSort1(a, left, right);// 递归排[left, div)QuickSort(a, left, div-1);// 递归排[div+1, right)QuickSort(a, div + 1, right);
}

解释：

①其中形参*a是需要排序的数组，left与right分别指向该数组的第一个元素与最后一个元素的数组下标；

②其中调用的PartSort1函数为具体实现函数——即做到“按照该基准值将待排序集合分割成两子序列，使左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值”。

③不同的算法有不同的实现过程，咱们以PartSort1代指经典的Hoare快排算法；PartSort2为挖坑法；PartSort3为前后指针法。它们都会返回基准值的数组下标。

④利用递归不断分区，直至单个元素返回。将每一个待排数据实现“左序列中所有元素均小于基准值，右子序列中所有元素均大于基准值”，此时整个数组有序。如：1，2，3，4，5，6，7。

二、以Hoare算法为核心实现快排

1.三数取中函数

首先我们需要选定一个基准值作为比较对象，使得小于该基准值的数据都移动到它左边，大于它的移动到右边。因此该基准值最好选择该数组中的非最大值或最小值，若选择最大值或最小值为基准值，则算法效率大幅下降。

三数取中函数的目的就是确保：基准值非最大值或最小值。

GetMid：三数取中

//三数取中
int GetMid(int* a, int left, int right)
{int mid = (right - left) / 2;if (a[mid] < a[right]){if (a[mid] > a[left])return mid;else return a[left] < a[right] ? left : right;}else{if (a[right] > a[left])return right;else return a[left] > a[mid] ? mid : left;}
}

解释：

①left与right、mid都是存储的数组下标；

②我们从数组首元素、末元素和中间元素三个数据中选择一个中间值，确保基准值非最大值或最小值，并返回其数组下标。

③第一个if 条件中的else：如果a[mid]小于a[right]，但a[mid]又小于等于a[left]（未满足if），那么返回a[left]与a[right]中的较小值下标即可。第二个if 条件中的else同理；

现在，再次明确目的：如何才能做到“使左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值”？

2.经典Hoare快排

算法介绍：

①通过三数取中函数得到基准值，将其与首元素交换，再定义key变量存储基准值下标；

②从数组右边开始寻找大于a[key]（基准值）的元素，若存在则right最后指向的就是它；从数组左边开始寻找小于a[key]（基准值）的元素，若存在则left最后指向的就是它；

③确保left与right没有跑过的情况下，将上述找到的值交换。然后重复②。

④结束时，也就是left与right相遇时，将相遇所在的位置的数据与基准值交换，并返回交换后基准值下标；

代码参考：

// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{//左第一个做keyint mid = GetMid(a, left, right);swap(&a[mid], &a[left]);int key = left;while (left < right){// 左做key，右先走// 找大于a[key]的值while (left < right && a[right] >= a[key])right--;  // 找小于a[key]的值while (left < right && a[left] <= a[key])left++;  if (left < right){swap(&a[left], &a[right]);}}swap(&a[key], &a[left]);return left;
}void swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}

（本文以a[left]与基准值交换，实际上可以是left也可以是right，只不过内循环执行顺序不同）

举个例子解释说明：可结合下方图解与上述代码查看

假设有数组int a[ ]={7，5，2，3，6，4，9，1，0}，执行一次上述代码流程为：

图解：

当外循环结束，此时数组满足基准值左边都小于基准值，基准值右边都大于基准值。

返回基准值的下标给div，接着执行QuickSort余下代码：

	int div = PartSort1(a, left, right);QuickSort(a, left, div-1);QuickSort(a, div + 1, right);

// 快速排序递归实现
void QuickSort(int* a, int left, int right)
{if (left >= right)return;if (!a)return;int div = PartSort1(a, left, right);QuickSort(a, left, div-1);QuickSort(a, div + 1, right);
}

将基准值左右两边的数据集当作新的数组（传入的是数组下标，实质还是在原数组上修改），以递归思想再次传入QuickSort函数。

何时函数执行结束？

这样套娃一直递归下去，直到传入的新数组只有一个元素（一个元素肯定有序），或者传入数组下标不合理，如left>right等，会通过 if 而返回。

if (left >= right)return;

细节：为什么左做key，内循环一定要右边先找？

这是为了预防情况：

①如果在某次交换完成后，right一直左移，直到与left相遇，那么此时相遇位置的值一定是小于基准值的！——因为刚发生了交换，小于基准值的被交换到了left的位置。所以再执行外循环外的swap(&a[key], &a[left]);时可以防止将大于基准值的数交换到数组前边去。

如果是左边先找，就会出现将大于基准值的数交换到数组前边去。

②如果压根就没有发生交换，一开始就right一直向左直至遇到left，此时“swap(&a[key], &a[left])”交换的是同一个位置的值（没有影响）；但如果右边先走就会出现将大于基准值的数交换到数组前边去。

完整代码框架

// 快速排序递归实现
void QuickSort(int* a, int left, int right)
{if (left >= right)return;if (!a)return;if (right - left <= 10){InsertSort(a + left, right - left + 1);return;}int div = PartSort1(a, left, right);QuickSort(a, left, div-1);QuickSort(a, div + 1, right);
}// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{//左第一个做keyint mid = GetMid(a, left, right);swap(&a[mid], &a[left]);int key = left;while (left < right){// 右边指针while (left < right && a[right] >= a[key])right--;  // 左边指针while (left < right && a[left] <= a[key])left++;  if (left < right){swap(&a[left], &a[right]);}}swap(&a[key], &a[left]);return left;
}//三数取中
int GetMid(int* a, int left, int right)
{int mid = (right - left) / 2;if (a[mid] < a[right]){if (a[mid] > a[left])return mid;else return a[left] < a[right] ? left : right;}else{if (a[right] > a[left])return right;else return a[left] > a[mid] ? mid : left;}
}//直接插入排序:用于优化hoare版本
void InsertSort(int* a, int n)
{if (!a){perror("arr is NULL");return;}//【0，end】为有序，temp即a[end+1]为插入数据；//在一遍for循环结束后，【0，end+1】变有序；//内循环while的作用是为a[end+1]寻找在【0，end+1】中合适的位置for (int i = 0; i < n - 1; ++i){int end = i;int temp = a[end + 1];while (end >= 0){if (a[end] > temp){a[end + 1] = a[end];end--;}else{break;}}//走到这里end已经变成-1a[end + 1] = temp;}
}void swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}

优化快排

读者可能已经注意到上述代码与之前分析有不同之处：加入了InsertSort直接插入排序。

为什么？

在上述的例子中我们用了几个数据为例，分析了快排实际执行流程，但现实使用中很少出现这种几个数排序的的情况。

实际上几个数快排造成的函数调用等的时间损耗，比直接InsertSort插入排的时间损耗还多。

具体原因有：

1.减少递归开销：

快速排序是递归算法，每次递归调用都会产生函数调用栈的开销

对于小数组（如10个元素），递归调用产生的开销可能超过排序本身的成本

插入排序是原地排序，没有递归开销

2.实验表明，当n<15时，插入排序通常比快速排序更快。

所以当排序数据量小于等于10时，采用直接插入排序。这点在代码中体现为：

	if (right - left <= 10){InsertSort(a + left, right - left + 1);return;}

到这里一个完整的快排算法框架就算是搭好了，接下来介绍挖坑法与前后指针法。

三、算法拓展

挖坑法与前后指针法都可以用作快排中的核心算法，它们与Hoare算法作用一样，读者可随自己喜好随意用哪种。

之所以先介绍Hoare算法，完全是为了先搭好一个快排的框架。

至于框架内用哪种算法解决“使左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值”，它们三个都可以完成。

挖坑法

挖坑法顾名思义，就是拿符合条件的值去填坑。

算法介绍：

①通过三数取中函数得到基准值，将它与首元素交换，再定义key变量存储基准值，定义变量hole做坑，初始值为hole=left；

②从后往前，先找小于key（基准值）的元素。找到后，将这个值填入坑中，即a[hole]=a[right]，然后这个right当作新坑，接着执行③

③从前往后，找大于key的元素。找到后，将这个值填入坑中，即a[hole]=a[left]，然后这个leftt作当作新坑；

④重复②和③，直到left与right相遇，最后把key值填入坑中。

代码参考：

// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{int mid = GetMid(a, left, right);swap(&a[left], &a[mid]);int key = a[left];int hole = left;while (left < right){while (left < right && a[right] >= key){right--;}a[hole] = a[right];hole = right;while (left < right && a[left] <= key){left++;}a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}

举个例子解释说明：可结合下方图解与上述代码查看

假设有数组int a[ ]={7，5，2，3，6，4，9，1，0}，执行一次上述代码流程为：

图解：

一轮结束后，基准值的下标被放回，实现基准值（6）左边都小于它，右边都大于它。

前后指针法

算法介绍：

①通过三数取中函数得到基准值，将它与首元素交换。再定义key变量存储基准值，定义变量pre=left，定义变量cur=pre+1；

②pre变量存储小于等于基准值的最后一个元素的数组下标；

③cur遍历数组，当cur遇到小于基准值key的值时，pre++，并交换pre下标与cur下标所对应的值；

④cur++，重复③

⑤遍历结束后，将基准值与最后pre到达的位置对应的值进行交换。返回基准值下标。

代码实现：

// 正确的快速排序前后指针法
int PartSort3(int* a, int left, int right)
{// 1. 三数取中选择基准int mid = GetMid(a, left, right);swap(&a[left], &a[mid]);int key = a[left];// 2. 初始化指针int pre = left;      // 指向小于基准的最后一个元素int cur = left + 1;  // 遍历指针// 3. 遍历分区while (cur <= right){// 当前元素小于基准时，与pre后元素交换//if (a[cur] < key)//{//    pre++;//    swap(&a[pre], &a[cur]);//}//cur++;//优化后if (a[cur] < key&&++pre!=cur){swap(&a[cur], &a[pre]);}cur++;}// 4. 将基准放到正确位置swap(&a[left], &a[pre]);return pre;
}

依旧举个例子解释说明：可结合下方图解与上述代码查看

假设有数组int a[ ]={7，5，2，3，6，4，9，1，0}，执行一次上述代码流程为：

图解：

一轮结束后，基准值的下标被放回，实现基准值（6）左边都小于它，右边都大于它。

四、分析快速排序

Hoare、挖坑法、前后指针法这三种方法本质上都是实现快速排序核心思想——分区操作的不同策略，但它们的目标完全一致：

选取一个基准值，将数组划分为两部分，使得左边部分的元素都小于等于基准值，右边部分的元素都大于等于基准值。 基准值最终会落在其正确的位置上。

特性分析

1.三种算法的时间复杂度都是O(n logN);

2.三种算法的空间复杂度都是原地排序O(1)，但栈空间消耗完全取决于递归深度，通过用直接插入排序优化，在一定程度上减少了栈空间的消耗。

3.三种算法都是不稳定的！——非相邻交换导致相等元素顺序颠倒的可能性在三种方法中都存在。

4.Hoare最经典，挖坑法最好理解，前后指针法最易编写；