详解八大排序（三）------（快速排序）
文章目录
- 前言
- 1. 递归版本（QuickSort）
- 1.1 hoare版本
- 1.1.1 核心思路
- 1.1.2 实现代码
- 1.2 挖坑法
- 1.2.1 核心思路
- 1.2.2 实现代码
- 1.3 lomuto版本
- 1.3.1 核心思路
- 1.3.2 实现代码
- 2. 非递归版本（QuickSortNonR）
- 2.1 核心思路
- 2.2 实现代码
- 3.完整代码
前言
快速排序的本质是找到数组中的中间值，然后从中间值对半二分数组，再从二分之后的两个数组里面找到新的中间值，再二分。直到数组全部二分完成，无法二分之后，再返回数组。
那么，问题来了。我们应该如何找到这个中间值呢？
下面我会介绍三个找到中间值的方法。
1. 递归版本（QuickSort）
1.1 hoare版本
1.1.1 核心思路
hoare版本的核心思路就是直接定义第一个数为基准值，然后把数组排序成基准值位于中间。
再二分数组，将两个数组的第一个数定义为各自的基准值，将数组排序，让基准值位于中间。
如此重复，直到新的数组无法再找基准值。
此时，递归结束，函数之间返回。
以上述数组为例。我们将4定义为中间值，那么从左边和右边开始比较，也就是2和5。
先从右边开始比较，右边放置的数均要大于基准值。因为5大于4，所以从倒数第二个数开始比较，一直比较到1。
右边比较完成，再从左边开始比较，因为左边的数均要小于基准值。因为2小于4，所以再比较1，一直到8。
此时得到：
此时再将基准值与right交换，得到：
此时数组的基准值4，位于基准值左边的数均小于基准值，位于基准值右边的数均大于基准值。满足二分要求。我们就可以将数组一分为二。得到：
此时的1和8是各自数组的基准值。以新的基准值重复上面的操作，得到：
可以知道，左边数组基准值的右边均大于1，右边数组基准值的左边等于5，右边均大于5。然后继续二分之一，寻找基准值，并且交换后，得到：
重复上述步骤，我们最终可以得到：
此时递归结束，将这些数组全部返回到原数组，得到：
1.1.2 实现代码
// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* arr, int left, int right)
{
int keyi = left;//以数组的第一个数为基准值
++left;//从第二个数开始比较
while (left <= right)//当left大于等于right时，说明所有的数比较完毕
{
while (left <= right && arr[right] > arr[keyi])//基准值右边的数大于大于基准值
{
right--;
}
while (left <= right && arr[left] < arr[keyi])//基准值左边的数小于基准值
{
left++;
}
if (left <= right)//进入此判断条件说明，left遇到了大于等于基准值的数，right均遇到了小于等于基准值的数
{
Swap(&arr[left++], &arr[right--]);//交换left和right的值，同时++，判断下一个数
}
}
//退出循环，说明此时right指针的左边均小于基准值，右边均大于基准值。
Swap(&arr[keyi], &arr[right]);//让基准值与right交换
return right;//此时right指针指向基准值
}
//快速排序---需要借助其他方法找到中间值
void QuickSort(int* arr, int left, int right)
{
if (left >= right)//如果left大于right，说明所有的数比较完，可以直接返回
{
return;
}
int keyi = PartSort1(arr, left, right);//优先找到中间值
QuickSort(arr, left, keyi - 1);//二分之后再找左边的中间值，再二分，直到二分到只剩下一个数据
QuickSort(arr, keyi + 1, right);//左边的二分完成之后，再二分右边的数值
}
1.2 挖坑法
1.2.1 核心思路
挖坑法的核心思路是将第一个数定义为坑，坑的左边均小于坑，坑的右边均大于坑。
以上述数组为例。我们可以将4定义为坑，4定义为left，5定义为right，同时定义一个key = 4。得到：
我们先从right开始比较，大于key的，我们让right减少，right停止减少之后，再把right位置的值赋值给hole位置，同时让hole指向right位置。得到：
再从left开始比较，比key小的位置，让left增加，再把left位置的值赋值给hole位置，同时让hole指向left位置。得到：
此时由于left大于right。循环退出，再把key的值赋值给hole位置。得到：
此时数组的基准值4，位于基准值左边的数均小于基准值，位于基准值右边的数均大于基准值。满足二分要求。我们就可以将数组一分为二。得到：
我们再按照上述步骤重复定义第一个数组的hole为1，第二个数组的hole为8。可以得到
以第二个数组为例，我们重复上面的步骤。得到：
之后的步骤与上面的一致。最终得到：
1.2.2 实现代码
// 快速排序挖坑法
int PartSort2(int* arr, int left, int right)
{
int hole = left;//把第一个数定义为坑
int key = arr[hole];//把坑的数值记录在key里面
while (left < right)
{
while (left < right && arr[right] > key)
{
right--;//从右边起，找到第一个比hole要小的数
}
arr[hole] = arr[right];
hole = right;//把hole放在right位置
while (left < right && arr[left] <= key)
{
left++;
}
arr[hole] = arr[left];
hole = left;
}
arr[hole] = key;
return hole;
}
//快速排序---需要借助其他方法找到中间值
void QuickSort(int* arr, int left, int right)
{
if (left >= right)//如果left大于right，说明所有的数比较完，可以直接返回
{
return;
}
int keyi = PartSort2(arr, left, right);//优先找到中间值
QuickSort(arr, left, keyi - 1);//二分之后再找左边的中间值，再二分，直到二分到只剩下一个数据
QuickSort(arr, keyi + 1, right);//左边的二分完成之后，再二分右边的数值
}
1.3 lomuto版本
1.3.1 核心思路
lomuto的核心思路是快慢指针的运用。
以上述数组为例，可以定义两个指针，prev指向4，cur指向2，再记录下第一个数的值，keyi = 4。得到：
在比较时，我们将cur指向的数与prev指向的数进行对比，当cur指向的值小于prev指向的值并且cur不位于prev的下一位时，我们可以将cur的值与prev交换。全部交换完成后，prev指向的位置就是中间值的位置，让prev的值与keyi交换。得到：
之后再将数组一分为二，得到：
再重复上面的步骤，得到：
1.3.2 实现代码
// 快速排序前后指针法
int PartSort3(int* arr, int left, int right)
{
int prev = left, cur = left + 1;
int keyi = left;
while (cur <= right)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
Swap(&arr[prev], &arr[keyi]);
return prev;
}
//快速排序---需要借助其他方法找到中间值
void QuickSort(int* arr, int left, int right)
{
if (left >= right)//如果left大于right，说明所有的数比较完，可以直接返回
{
return;
}
int keyi = PartSort3(arr, left, right);//优先找到中间值
QuickSort(arr, left, keyi - 1);//二分之后再找左边的中间值，再二分，直到二分到只剩下一个数据
QuickSort(arr, keyi + 1, right);//左边的二分完成之后，再二分右边的数值
}
2. 非递归版本（QuickSortNonR）
2.1 核心思路
非递归版本的核心思路与lomuto版本的思路非常像。只不过我们需要借助栈（Stack）这一数据结构来帮助我们排序好基准值。
由于栈这一数据结构只能从栈顶一端进，一端出，那么可以给待排序数组的底部划分序号。得到：
将数组的最后一个位置和第一个位置的下标放入栈中，得到：
再取出这两个数，作为需要比较的数组的区间，并且将begin定义为0，prev定义为0，cur定义为0 + 1，end定义为7。得到：
然后根据lomuto版本的比较法，依次比较，得到：
第一个基准值已经找好了，接着找第二个基准值，把 [begin,keyi - 1] 和 [keyi + 1,end] 放入栈中。得到：
再取出两个数，作为下一次比较的数组的区间。将这一区间比较好之后，再取出两个数。直到取出的区间均小于1。就可以返回数组。得到：
2.2 实现代码
// 快速排序 非递归实现
void QuickSortNonR(int* arr, int left, int right)
{
ST st;
STInit(&st);
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st))
{
//取栈顶元素---取两次
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
//[begin,end]---找基准值
int prev = begin;
int cur = begin + 1;
int keyi = begin;
while (cur <= end)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
Swap(&arr[keyi], &arr[prev]);
keyi = prev;
//根据基准值划分左右区间
//左区间：[begin,keyi-1]
//右区间：[keyi+1,end]
if (keyi + 1 < end)
{
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
if (keyi - 1 > begin)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
STDestroy(&st);
}
3.完整代码
#include<stdio.h>
#include<stdlib.h>
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//打印函数
void PrintArr(int* arr,int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* arr, int left, int right)
{
int keyi = left;//以数组的第一个数为基准值
++left;//从第二个数开始比较
while (left <= right)//当left大于等于right时，说明所有的数比较完毕
{
while (left <= right && arr[right] > arr[keyi])//基准值右边的数大于大于基准值
{
right--;
}
while (left <= right && arr[left] < arr[keyi])//基准值左边的数小于基准值
{
left++;
}
if (left <= right)//进入此判断条件说明，left遇到了大于等于基准值的数，right均遇到了小于等于基准值的数
{
Swap(&arr[left++], &arr[right--]);//交换left和right的值，同时++，判断下一个数
}
}
//退出循环，说明此时right指针的左边均小于基准值，右边均大于基准值。
Swap(&arr[keyi], &arr[right]);//让基准值与right交换
return right;//此时right指针指向基准值
}
// 快速排序挖坑法
int PartSort2(int* arr, int left, int right)
{
int hole = left;//把第一个数定义为坑
int key = arr[hole];//把坑的数值记录在key里面
while (left < right)
{
while (left < right && arr[right] > key)
{
right--;//从右边起，找到第一个比hole要小的数
}
arr[hole] = arr[right];
hole = right;//把hole放在right位置
while (left < right && arr[left] <= key)
{
left++;
}
arr[hole] = arr[left];
hole = left;
}
arr[hole] = key;
return hole;
}
// 快速排序前后指针法
int PartSort3(int* arr, int left, int right)
{
int prev = left, cur = left + 1;
int keyi = left;
while (cur <= right)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
Swap(&arr[prev], &arr[keyi]);
return prev;
}
//快速排序---需要借助其他方法找到中间值
void QuickSort(int* arr, int left, int right)
{
if (left >= right)//如果left大于right，说明所有的数比较完，可以直接返回
{
return;
}
int keyi = PartSort3(arr, left, right);//优先找到中间值
QuickSort(arr, left, keyi - 1);//二分之后再找左边的中间值，再二分，直到二分到只剩下一个数据
QuickSort(arr, keyi + 1, right);//左边的二分完成之后，再二分右边的数值
}
// 快速排序 非递归实现
void QuickSortNonR(int* arr, int left, int right)
{
ST st;
STInit(&st);
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st))
{
//取栈顶元素---取两次
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
//[begin,end]---找基准值
int prev = begin;
int cur = begin + 1;
int keyi = begin;
while (cur <= end)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
Swap(&arr[keyi], &arr[prev]);
keyi = prev;
//根据基准值划分左右区间
//左区间：[begin,keyi-1]
//右区间：[keyi+1,end]
if (keyi + 1 < end)
{
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
if (keyi - 1 > begin)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
STDestroy(&st);
}
int main()
{
//int arr[] = { 5,2,7,8,1,3,9,4,6 };
int arr[] = { 4,2,1,8,5,6,9,5 };
//int arr[] = { 2,3,6,5 };
int sz = sizeof(arr) / sizeof(int);
printf("排序前：");
PrintArr(arr, sz);
//QuickSort(arr, 0, sz - 1);
QuickSortNonR(arr, 0, sz - 1);
printf("排序后：");
PrintArr(arr, sz);
return 0;
}