【数据结构】快排的详细讲解
已于 2023-11-23 20:42:48 修改
阅读量1.1k
收藏
16
点赞数
13
江河入海，知识涌动，这是我参与江海计划的第7篇。
目录：
介绍
一，递归快排确定基准值
二，递归遍历
三，非递归的快排
四，快排的效率
介绍
快排是排序算法中效率是比较高的，快排的基本思想是运用二分思想，与二叉树的前序遍历类似，将数据划分，每次划分确定1个基准值(就是已经确定好有序后位置的数据)，以升序为例，基准值左面的数据都比此值小，右面的数据都比此值大，然后以基准值为分界线，经过不断划分，最终基准值的个数达到n，数据即有序，因此，递归运用是不二选法，也可运用非递归，但是比较麻烦。
一，递归快排确定基准值
确定基准值的方法常用的有三种，普通法，挖坑法，前后指针法。
1，普通法，具体思想图如下(以升序为例)：
上面说过，基准值的确定过程要保证左面的数据都比此值小或大，右面的数据都要比此值大或小，因此，此基准值就确定了在整个数据中的位置。以升序为例，我们可以从开头和末尾遍历数据，比开头(以首元素为基准)元素大的放在最后，比开头元素小的数据放在前面，最终当两者相遇后再与开头元素交换即可确定基准值(注意：此步骤有细节，具体后面会说明)。如下图：
基准值过程图
现在有个注意要素套提一下，当上图中的前面L和后面R相遇时，如何保证此值一定比首元素小呢？这里我们需要控制好L的走向即可，即让R先走，当遇见比首元素小时退出，然后让L走，最后让两者进行交换，这样一来无论出现什么情况，当L与R相遇时对应的数据将一定比首元素(即以第一个元素为基准)小，此步骤称为预排序。
基准值的确定代码如下：
void Swap(int* x1, int* x2) {
int t = *x1;
*x1 = *x2;
*x2 = t;
}int PartSort1(int* a, int begin, int end) {
int key = begin;
while (begin < end) {
//注意此步骤，end必须先开始(即当左边开始行走右边一定有比key小的值)，
//因为要控制最后的begin最终比key（开头元素）小，因此，右边必须先走.
while (begin < end && a[end] >= a[key]) {
end--;
}
//当走左边时，最终会Swap(a + end, a + begin);交换后begin的最终比key小
while (begin < end && a[begin] <= a[key]) {
begin++;
}
Swap(a + end, a + begin);
}
Swap(a + key, a + begin);
return begin;
}
2，挖坑法，原理图如下(以升序为例)：
挖坑发大致思想与普通法一样，不同的是挖坑发有了坑位。挖坑发是先将首元素保存，将此位置形成坑位(其实坑位上有数据，但坑位的数据不影响，为了方便理解，所以在上图中的坑位就没写上去)，然后开始首尾遍历（尾要先遍历，原理同上），比key大的元素放在后面，比key小的元素放在前面，一旦不满足此情况，这个数据将给到位置L或位置R，原本的位置将会形成坑位，直到两者相遇为止，结束遍历，最后把key的值放入坑位即可。代码如下：
int PartSort2(int* a, int begin, int end) {
int key = a[begin];
int hole = begin;//开头先形成坑位
while (begin < end) {
// 右边先走（原理与PartSort1原理一样），找小，填到左边的坑，右边形成新的坑位
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;
}
3，前后指针法（prev是前指针，cur是后指针，此指针是位置指针，不是我们所常说的指针型），原理图如下：
前后指针法跟上面两种方法有很大不同，如上，以第一个元素为基准，即定义key值为首元素，cur往前遍历，prev随之跟上cur的步伐，当prev遇到的数据比key小，prve向前移动；当prev遇到的数据比key大，prev停止移动，此时，cur不断向前移动，一旦找到比key小的数据就会跟prev指向的数据进行交换，最后，当cur遍历完整个数据后cur与key会进行交换，确定此时key所对应的值比左边数据大，比右边数据小。代码如下：
void Swap(int* x1, int* x2) {
int t = *x1;
*x1 = *x2;
*x2 = t;
}
int PartSort3(int* a, int begin, int end) {
int front = begin + 1;
int back = begin;
while (front <= end) {
if (a[front] <= a[begin]) {
back++;
Swap(a + back, a + front);
}
front++;
}
//因为后指针控制，所以当程序结束后back所指向的数据都比keyi所指向的数据小
Swap(a + begin, a + back);
return back;
}
总：以上三种遍历确定基准值的方法在快排称为预排序，每一趟预排序都可确定数据中一个元素的排序位置，每当确定一个数据后相对位置后，我们只需要不断以上次遍历时确定的基准值为界，递归遍历数据，即可确定最终确定序列。
二，递归遍历
当我们明白如何确定基准值后，接下来就是程序的结构搭建了，上面说过，快排递归跟二叉树的前序遍历一样，并且还需要以基准值为分界线，不断确定基准值，具体思路导图如下：
当确定好基准值key后，以区间[begin, key - 1]和区间[key + 1, end]进行划分（begin是要进行遍历时，开头元素的坐标，end是要遍历时，结尾元素的坐标，如上图），以次区间不断进行与二叉树前序遍历相同的递归，根据上图所示，很明显，当begin>=end时结束下一层递归。代码如下：
void QuickSort(int* a, int begin, int end)
{
//即当不存在区间时结束，即就排好了一个数
if (begin >= end)
return;
//运用普通法PartSort1，此算法是返回一个顺序表中中间值的坐标，在坐标左边都小于此数，在坐标的右边都大于此数
int keyi = PartSort1(a, begin, end);//也可用挖坑法和前后指针法
// 区间递归: 以keyi为界，左[begin, keyi-1]，右[keyi+1, end],一直缩小，最终会逐渐会缩小成有序
QuickSort(a, begin, keyi - 1);//在keyi的左面进行遍历
QuickSort(a, keyi + 1, end);//在keyi的右面进行遍历
}
下面是总代码：
#include <stdio.h>
void Swap(int* x1, int* x2) {
int t = *x1;
*x1 = *x2;
*x2 = t;
}
int PartSort1(int* a, int begin, int end) {
int key = begin;
while (begin < end) {
//注意此步骤，end必须先开始(即当左边开始行走右边一定有比key小的值)，
//因为要控制最后的begin最终比key（开头元素）小，因此，右边必须先走.
while (begin < end && a[end] >= a[key]) {
end--;
}
//当走左边时，最终会Swap(a + end, a + begin);交换后begin的最终比key小
while (begin < end && a[begin] <= a[key]) {
begin++;
}
Swap(a + end, a + begin);
}
Swap(a + key, a + begin);
return begin;
}
void QuickSort(int* a, int begin, int end)
{
//即当不存在区间时结束，即就排好了一个数
if (begin >= end)
return;
//PartSort1算法是返回一个顺序表中中间值的坐标，在坐标左边都小于此数，在坐标的右边都大于此数
int keyi = PartSort1(a, begin, end);
// 区间递归: 左[begin, keyi-1] keyi 右[keyi+1, end],一直缩小，最终会逐渐会缩小成排序
QuickSort(a, begin, keyi - 1);//在keyi的左面进行遍历
QuickSort(a, keyi + 1, end);//在keyi的右面进行遍历
}
void Print(int* a, int n) {
for (int i = 0; i < n; i++) {
fprintf(stdout, "%d ", a[i]);
}
puts("");
}
void TestQuickSort()
{
int a[] = { 6,1,2,7,9,3,4,5,10,8 };
QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
Print(a, sizeof(a) / sizeof(int));
}
int main() {
TestQuickSort();
return 0;
}运行图：
三，非递归的快排
运用非递归，大多数要运用栈结构，因为递归本身其实就是不断入栈和出栈，递归过程跟栈结构一样，进入递归就是入栈，出函数就是出栈，都是先进后出。快排的非递归实现，我们也可用栈来实现。根据前面递归的运用，递归是不断进行区间分割，我们可将此区间放入栈中，然后进行不断循环遍历，每当遍历时就将区间放入栈中，一旦用完此区间就释放，因为此区间我们已经遍历完了，释放此区间后是为了后面的区间遍历，跟递归中函数栈帧的创建与销毁一样。非递归结构代码如下：
1，栈的建立
typedef struct stack {
int* Data;
int Capacity;
int Top;
}Stack;
//以下三个是要运用栈结构的算法
void StackInit(Stack* S);
void StackPop(Stack* S);
void StackPush(Stack* S, int X);
//栈功能的实现
void StackInit(Stack* S) {//初始化栈
assert(S);
S->Data = 0;
S->Capacity = 0;
S->Top = -1;
}
void StackPop(Stack* S) {//出栈
assert(S || S->Data || S->Top != -1);
S->Top--;
}
void StackPush(Stack* S, int X) {//入栈
assert(S);
if (!S->Data) {
S->Data = (int*)malloc(sizeof(int) * 4);
assert(S->Data);
S->Capacity = 4;
}
else if (S->Top == S->Capacity - 1) {
S->Data = (int*)realloc(S->Data, (sizeof(int) * S->Capacity) * 2);
assert(S->Data);
S->Capacity *= 2;
}
S->Data[++S->Top] = X;
}
2，非递归的结构
void QuickSort(int* a, int left, int right) {
//创建栈结构S，以栈来模仿递归过程
Stack* S = (Stack*)malloc(sizeof(Stack));
StackInit(S);
StackPush(S, right);
StackPush(S, left);
while (S->Top != -1) {
//确定左右区间，每当遍历完一次时要及时更换，即从栈中去除操作
int begin = S->Data[S->Top];
StackPop(S);
int end = S->Data[S->Top];
StackPop(S);
//用指定好的区间进行预排序，即一次遍历
int key = PartSort1(a, begin, end);
//进行左区间的遍历
if (end - 1 > begin) {
//注意栈结构先进后出的特点，要先把end装进去
StackPush(S, end - 1);
StackPush(S, begin);
}
//进行右区间的遍历
if (begin + 1 < end) {
//同理，要先把end装进去
StackPush(S, end);
StackPush(S, begin + 1);
}
}
free(S);
//注意，不能在此算法内这样写，因为这是的a是首元素地址，即指针，sizeof(a)为地址的大小
//Print(a, sizeof(a) / sizeof(int));
}
以上是非递归过程中的逻辑代码，除此两大步，其它的逻辑运用与递归无任何区别，总代码如下：
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef struct stack {
int* Data;
int Capacity;
int Top;
}Stack;
//以下三个是要运用栈结构的算法
void StackInit(Stack* S);
void StackPop(Stack* S);
void StackPush(Stack* S, int X);
//栈功能的实现
void StackInit(Stack* S) {//初始化栈
assert(S);
S->Data = 0;
S->Capacity = 0;
S->Top = -1;
}
void StackPop(Stack* S) {//出栈
assert(S || S->Data || S->Top != -1);
S->Top--;
}
void StackPush(Stack* S, int X) {//入栈
assert(S);
if (!S->Data) {
S->Data = (int*)malloc(sizeof(int) * 4);
assert(S->Data);
S->Capacity = 4;
}
else if (S->Top == S->Capacity - 1) {
S->Data = (int*)realloc(S->Data, (sizeof(int) * S->Capacity) * 2);
assert(S->Data);
S->Capacity *= 2;
}
S->Data[++S->Top] = X;
}
void Swap(int* x1, int* x2) {
int t = *x1;
*x1 = *x2;
*x2 = t;
}
int PartSort1(int* a, int begin, int end) {
int key = begin;
while (begin < end) {
//注意此步骤，end必须先开始(即当左边开始行走右边一定有比key小的值)，
//因为要控制最后的begin最终比key（开头元素）小，因此，右边必须先走.
while (begin < end && a[end] >= a[key]) {
end--;
}
//当走左边时，最终会Swap(a + end, a + begin);交换后begin的最终比key小
while (begin < end && a[begin] <= a[key]) {
begin++;
}
Swap(a + end, a + begin);
}
Swap(a + key, a + begin);
return begin;
}
void QuickSort(int* a, int left, int right) {
//创建栈结构S，以栈来模仿递归过程
Stack* S = (Stack*)malloc(sizeof(Stack));
StackInit(S);
StackPush(S, right);
StackPush(S, left);
while (S->Top != -1) {
//确定左右区间，每当遍历完一次时要及时更换，即从栈中去除操作
int begin = S->Data[S->Top];
StackPop(S);
int end = S->Data[S->Top];
StackPop(S);
//用指定好的区间进行预排序，即一次遍历
int key = PartSort1(a, begin, end);
//进行左区间的遍历
if (end - 1 > begin) {
//注意栈结构先进后出的特点，要先把end装进去
StackPush(S, end - 1);
StackPush(S, begin);
}
//进行右区间的遍历
if (begin + 1 < end) {
//同理，要先把end装进去
StackPush(S, end);
StackPush(S, begin + 1);
}
}
free(S);
//注意，不能在此算法内这样写，因为这是的a是首元素地址，即指针，sizeof(a)为地址的大小
//Print(a, sizeof(a) / sizeof(int));
}
void Print(int* a, int n) {
for (int i = 0; i < n; i++) {
fprintf(stdout, "%d ", a[i]);
}
puts("");
}
int main() {
int a[] = { 0,5,7,9,3,4,1,6,2,8 };
QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
Print(a, sizeof(a) / sizeof(int));
return 0;
}运行图：
分析：
此非递归的运用是每次通过基准值来确定的，当确定好一个基准值时就将此基准值的左右要遍历的区间加入栈中，因为无法保证每次进栈的区间跟递归程序一样，所以我们以基准为界，将左右区间加入，一直往下遍历，当区间缩小到一定的返回后就停止加入，最后再遍历栈中的区间即可。
四，快排的效率
1，快排的效率分析
快排效率在平常说是效率比较高的，大致根据二叉树原理计算，快排时间复杂度为O(nlogn)，空间复杂度为O（logn），但这只是对于大多时候，其实快排的时间效率是很不确定的，快排的效率跟数据的原有序列有关，序列越接近有序，快排效率越低。我们先观察以下图：
快排效率最好情况
快排效率最坏情况
可知，快排预排序的时间效率在区间[logn，n]，当原有序列越有序时，无论是递归还是非递归时间效率都很低，有序时效率最低，而遍历元素的时间复杂度不变，一直是O(n)，因此快排的时间效率在区间[nlogn，n^2]。
2，三数取中
当快排在有序时(升序为例)，数据会靠近左边进行排序，而要想提高快排的效率，就必须尽量让基准值尽量往中间靠拢，但这样很难控制，因为这与数据原有的序列有关。虽然说我们不能直接控制，但是我们可控制最坏情况来进而控制时间效率，即序列有序时的情况。
通常，我们是选取首元素为基准值的，因此，只要控制好首元素不为基准值的情况即可，也就是三数取中。
三数取中是将判断首元素，尾元素，中间元素三者之间的大小，将中间大的数据与首元素交换，使首元素不可能为基准值。代码如下：
int GetMidi(int* a, int left, int right)
{
int mid = (left + right) / 2;//中间数mid
//下面比较 left mid right 三者之间大小，将中间大的数据的下标返回过去
//先人left与mid比较，然后进一步判断right
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right]) // mid是最大值
{
return left;
}
else
{
return right;
}
}
else
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right]) // mid是最小
{
return left;
}
else
{
return right;
}
}
}
具体思想就是先两两比较，然后进一步与第三者比较，上面代码中选举了left与mid两者之间比较，然后再跟第三者right比较，满足中间大的数据返回其下标。
3，改善后算法的运用
有了三数取中，快排将不会出现最坏情况，虽说有可能会出现次坏情况，但基本是不可能的，因为这种情况很是要求原序列的次序和三数取中的交换，因次，如若在算法中加上三数取中后算法的时间复杂度基本为O(nlogn)。下面是改进后运用的代码：
int GetMidi(int* a, int left, int right)
{
int mid = (left + right) / 2;//中间数mid
//下面比较 left mid right 三者之间大小，将中间大的数据的下标返回过去
//先人left与mid比较，然后进一步判断right
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right]) // mid是最大值
{
return left;
}
else
{
return right;
}
}
else
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right]) // mid是最小
{
return left;
}
else
{
return right;
}
}
}
void Swap(int* x1, int* x2) {
int t = *x1;
*x1 = *x2;
*x2 = t;
}
//普通法
int PartSort1(int* a, int begin, int end) {
//运用三数取中，与每次预排序的区间首元素交换，防止出现最坏情况
int midi = GetMidi(a, begin, end);
Swap(a + begin, a + midi);
//以下代码正常不变
int key = begin;
while (begin < end) {
//注意此步骤，end必须先开始(即当左边开始行走右边一定有比key小的值)，
//因为要控制最后的begin最终比key（开头元素）小，因此，右边必须先走.
while (begin < end && a[end] >= a[key]) {
end--;
}
//当走左边时，最终会Swap(a + end, a + begin);交换后begin的最终比key小
while (begin < end && a[begin] <= a[key]) {
begin++;
}
Swap(a + end, a + begin);
}
Swap(a + key, a + begin);
return begin;
}
//挖坑发
int PartSort2(int* a, int begin, int end) {
//运用三数取中，与每次预排序的区间首元素交换，防止出现最坏情况
int midi = GetMidi(a, begin, end);
Swap(a + begin, a + midi);
//以下代码正常不变
int key = a[begin];
int hole = begin;//开头先形成坑位
while (begin < end) {
// 右边先走（原理与PartSort1原理一样），找小，填到左边的坑，右边形成新的坑位
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;
}
//前后指针法
int PartSort3(int* a, int begin, int end) {
//运用三数取中，与每次预排序的区间首元素交换，防止出现最坏情况
int midi = GetMidi(a, begin, end);
Swap(a + begin, a + midi);
//以下代码正常不变
int front = begin + 1;
int back = begin;
while (front <= end) {
if (a[front] <= a[begin]) {
back++;
Swap(a + back, a + front);
}
front++;
}
//因为后指针控制，所以当程序结束后back所指向的数据都比keyi所指向的数据小
Swap(a + begin, a + back);
return back;
}
在以上中，除了预排序算法需要改进，其它的都不用动即可实现高效的快排。最后，跟大家再次强调一下快排的效率，快排在大多数情况下确实效率很高，但快排的效率受原数据的序列影响比较大，当序列越接近有序时，快排的效率可能还没有其它算法高，在以后的运用中要不要用快排还需根据原数据的情况而定。
3187
暂无认证
到【灌水乐园】发言
南木元元: 内容干货很多，学到了，支持~
普通网友: 干货满满，实用性强，博主的写作风格简洁明了，让人一目了然。文章涵盖了很多实用的知识点。【我也写了一些相关领域的文章，希望能够得到博主的指导，共同进步！】
林戈的IT生涯: 笔落半寸惊风雨，技法文成泣鬼神。 林戈捋过不忍去，留评四句作余音。
_BugMan: 【C++】哈希结构，赞一个喃
屿小夏: 博主讲解的很详细，结构严谨。感谢博主分享，期待博主持续输出好文，同时也希望可以来我博客指导我一番！