文章目录
一、递归的整体思路
整体思路：
每次固定一个数的位置
默认当前范围的第一个数就是要固定的数
比它大的放左边，比它小的放右边
递归
分析：
每次固定好一个数的位置后，去左区间固定一个数，右区间固定一个数，以此类推，直到要固定数的范围只剩一个数或范围不存在就停止
begin == end表示这个范围只有一个数，begin>end表示范围不存在
PartSort这个函数的功能是：从当前范围中固定好一个数的位置，并返回固定后的位置下标，具体如何实现这个功能，下面右三种方法
代码示例：
void QuickSort(int* a, int begin, int end)
{
if(begin>=end)
return;
int keyi = PartSort(a,begin,end);
QuickSort(a,begin,keyi-1);
QuickSort(a,keyi+1,end);
}
二、固定好一个位置的三种方法
1. hoare版本
具体步骤：
- 先从范围最后一个位置开始找比a[keyi]小的值，找到就停下；再从最开始的位置找比a[keyi]大的值，找到就停下；交换这两个值。
- 重复步骤1，直到左边和右边相遇或右边和左边相遇（left == right）停止，此时left这个位置的值是小于a[keyi]的
- 最后，交换a[keyi]和a[left]的值，再令keyi = left;此时a[keyi]就被固定在它排序好的位置
初版代码示例：
根据上面步骤，演示代码
//haore
int PartSort1(int* a, int left, int right)
{
int keyi = left;
while (left < right)
{
//右边找小
while (a[right] > a[keyi])
{
right--;
}
//左边找大
while (a[left] < a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
keyi = left;
return keyi;
}
注意：
- 问题1：死循环
如果左右两边都有等于a[keyi]的值,这时left和right都会停下，然后交换，交换后继续找大或找小，但left和right仍然不动，继续交换，一直重复这个操作，成为死循环
解决方法：
遇到等于a[keyi]就继续++/–
右边找小的条件：a[right]>=a[keyi]
左边找大的条件：a[left]<=a[keyi]
- 问题2：越界
极端情况下，这个范围里的值刚好是升序的，right先走，一直找小，找不到，来到了left的位置，依然没找到，所以right继续走，走到了left前面的位置，此时right就已经越界，Swap(&a[left],&a[right])时就会非法访问
解决方法：
right和left每次找值的时候先判断是否已经相遇，若相遇就不今小循环
增加的条件left<right
修改后的代码示例：
修改后的代码：
//haore
int PartSort1(int* a, int left, int right)
{
int keyi = left;
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[keyi], &a[left]);
keyi = left;
return keyi;
}
如何保证相遇位置一定比a[keyi]小
两种方案：
- 最左边的值做key,右边先走，保障了相遇位置的值比a[keyi]小
- 最右边的值做key,左边先走，报章了相遇位置的值比a[keyi]大
根据方案1分情况讨论：
右边先走：L遇R，R遇L
- 情况一：L遇R
此时R已经走过了，并且停下的位置的值小于a[keyi]，那么L遇R的位置就比a[keyi]小 - 情况二：R遇L
- L没动： R遇L可能是R第一次走，一次性就到L，L还没动，这时相遇的位置就是L的初始位置keyi
- L动了： R遇L，L已经走过了，说明L已经找到了大并且与R进行了交换，交换后的L的值是小于a[keyi]的，所以R遇L的位置的值比a[keyi]小
2. 挖坑法
思路：
- 将范围最左边的值作为坑hole，用key将a[left]的值保存起来
- 右边先走，找小，找到后将right位置上的值赋给hole的值,再更新坑hole的位置，hole = right;左边找大，找到后将left位置上的值赋给hole的值，再更新坑hole的位置，hole = left。
- 重复步骤2，直到左右相遇，相遇的位置就是坑hole，将key的值赋给这个坑，结束
代码示例：
//挖坑法
int PartSort2(int* a, int left, int right)
{
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;
}
3. 前后指针法
思路：
- 先定义两个下标prev、cur，prev指向范围中最左边的值，cur指向prev的下一个值
- cur找小，遇到大于等于key的直接cur++；遇到小于key的，先++prev，再将prev和cur位置的值进行交换，cur++。
- 重复步骤2，直到cur走出这个范围，此时prev指向的是所有大于key位置的前一个，最后交换prev和keyi位置的值
分析
- 当cur遇到比key大的值后，cur++，prev不动
- 当cur遇到比key小的值后，与++prev的位置交换，把小于key的值移到左边，大于可以的值移到右边，相当于把大于key的值向右推
代码示例：
//前后指针法
int PartSort3(int* a, int left, int right)
{
int prev = left;
int cur = left + 1;
int keyi = left;
while (cur <= right)
{
//cur找小，与++prev交换
if (a[cur] < a[keyi] && ++prev != cur)//++prev != cur是一点优化，针对prev和cur之间没有大于a[keyi]的值时的原地交换
{
Swap(&a[prev], &a[keyi]);
}
//if (a[cur] < a[keyi])
//{
// ++prev;
// Swap(&a[prev], &a[keyi]);
//}
//无论a[cur]大于小于还是等于a[keyi]，cur都++
cur++;
}
//prev指向的是所有大于a[keyi]的前一个位置
Swap(&a[prev], &a[keyi]);
keyi = prev;
return keyi;
}
三、非递归思路
思路:
用栈模拟递归的过程
- 先将最开始的范围分别压入栈中，压两次，先压右边界，再压左边界
- 一次弹出两个值，表示一个范围，在该范围中固定好一个值的位置，然后将这个值的右区间的两个边界值入栈，再将左区间的两个边界入栈
- 重复步骤2，直到栈为空停止，最后销毁栈
代码示例：
//快排非递归方法
void QuickSortNonR(int* a, int left, int right)
{
ST st;
STInit(&st);
//将左右区间压入栈中
STPush(&st, right);
STPush(&st, left);
while (!STEmpty(&st))
{
//弹出左右范围
int leftrange = STTop(&st);
STPop(&st);
int rightrange = STTop(&st);
STPop(&st);
//在这个范围中固定好一个值
int keyi = PartSort1(a, leftrange, rightrange);
//先压右后压左区间是为了模拟递归的调用过程
//如果keyi的右区间的个数至少大于一个就说明还需要固定值，所以压栈
if (keyi + 1 < rightrange)
{
STPush(&st, rightrange);
STPush(&st, keyi + 1);
}
//如果keyi的做区间的个数至少大于一个就说明还需要固定值，所以压栈
if (keyi - 1 > leftrange)
{
STPush(&st, keyi - 1);
STPush(&st, leftrange);
}
}
STDestory(&st);
}
四、时间复杂度分析
最好的情况，每次要固定的位置都在最中间，这样的时间复杂度是O(N*logN)
最坏的情况，要排的本来就是升序，每次要固定的位置都在最左边，时间复杂度是O(N2)
时间复杂度与选的key是有关的，这个key越靠近中间位置，时间复杂度越小
解决方案：
- 随机数选key
- 三数取中
五、对递归法的优化
由于快排的时间复杂度跟每次选的key值有关，如果每次固定的值刚好是最小值，那么快排的速度就会非常慢，几乎是O(N2)级别
这种情况的例子就是有序
那么如何在有序或接近有序的情况让快排的速度提高呢？
三数取中
三数取中
在当前范围中选取左边界，中间和右边界三个数，比较大小，将中间的值作为key，与左边界的值进行交换，然后再进行固定key的操作
//快排的优化：三数取中
int GetMidIndex(int* a, int left, int right)
{
int mid = left + (right - left) / 2;
if (a[left] > a[mid])
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return right;
}
else //a[left]>a[mid], a[left]<a[right]
{
return left;
}
}
else //a[mid]>a[left]
{
if(a[right]>a[mid])
{
return mid;
}
else if (a[right] > a[left])
{
return right;
}
else //a[mid]>a[left], a[left]>a[right]
{
return left;
}
}
}
三路分化
当要排的数据含有大量重复的值甚至全部一样，我们的快排就会被克制，
每次确定一个值的位置，但按照上图的过程进行下去，最后的时间复杂度到达O(N2)，为了保证遇到这类情况也会很快的解决，使用三路划分即可
思路：
将小于key的值弄到左侧，大于key的值弄到右侧，等于key的值弄到中间，这样排一次就可以固定好多个等于key值的值
三个指针l,r,cur;l指向左边界，r指向右边界，cur指向l的下一个位置
步骤：
- 当a[cur]<key，交换cur、l位置的值，cur++，l++；
- 当a[cur]>key，交换cur、r位置的值，r–；
- 当a[cur]==key，cur++；
- 直到cur大于r时停止，再将左区间(left,l-1)，右区间(r+1,right)进行递归
分析：
- l指向的是等于key值的最左边的位置，r指向的是大于key值的组左边的位置
- cur和l之间是等于key的值
- cur找到小后与key交换的目的是将小于key的值移到左侧，等于key的值向中间移动，交换后的a[cur]是等于key的值，所以cur++，交换后的a[l]是小于key的值，所以l++,指向等于key值的最左边的位置
- cur找到大于key的值后与r位置的值交换，交换后，a[r]的值大于key，r–指向大于key值的最左边的位置；此时a[cur]的值是不知道的，因为交换前的a[r]与key的大小关系并不清楚，所以现在的a[cur]需要判断，不能++
本质：
- 小的甩到左边，大的甩到右边
- 跟key相等的只推到中间
代码实现：
//快排的优化：三路划分
void QuickSort2(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int l = begin;
int r = end;
int cur = begin + 1;
int key = a[begin];
while (cur <= r)
{
if (a[cur] < key)
{
Swap(&a[cur], &a[l]);
cur++;
l++;
}
else if (a[cur] > key)
{
Swap(&a[cur], &a[r]);
r--;
}
else
{
cur++;
}
}
QuickSort2(a, begin, l - 1);
QuickSort2(a, r + 1, end);
}