数据结构 之 【排序】(递归实现快速排序)
目录
1.快速排序的思想
2.基准值的选取
2.1三数取中
2.2随机选数
2.3基准值选取代码
3.单趟排序的三种方法
3.1hoare法
3.1.1hoare法单趟图解
3.1.2hoare法单趟代码
3.2挖坑法
3.2.1挖坑法单趟图解
3.2.2挖坑法单趟代码
3.3前后指针法
3.3.1前后指针法单趟图解
3.3.2前后指针法单趟代码
4.快速排序排序图解及完整代码
5.快速排序的时间复杂度与空间复杂度
以升序为例
1.快速排序的思想
以升序为例，单趟排序时，选取一个基准值并将其放在数组中的正确位置，即让左边的数小于等于基准值，右边的数大于等于基准值，然后以该基准值所在位置为界，将数组分割为左右两个部分(均不包含基准值位置)并分别对这两个部分重复进行选取基准值并放到正确位置的操作，直到区间不存在时停止，此时数组有序
2.基准值的选取
固定选取当前数组的首元素或尾元素作为基准值，可能会因递归层次太深(后续讲解)导致效率低下(O(N^2))甚至栈溢出
一般使用三数取中或随机选数来确定基准值然后将其与首或尾位置元素进行交换
2.1三数取中
int GetMidi(int* a, int left, int right){int midi = left + (right - left) / 2;if (a[left] > a[midi]){if (a[midi] > a[right])return midi;else if (a[left] > a[right])return right;else return left;}else//a[left] <= a[midi]{if (a[left] > a[right])return left;else if (a[midi] > a[right])return right;else return midi;}
}三数取中就是说在数组的首元素、中间位置元素和最后一个元素当中选择中位数
这里我们返回该元素的下标，便于后续交换
int midi = (left + right) / 2，可能会导致溢出
int midi = left + (right - left) / 2; 中间偏左int midi = left + (right - left + 1) / 2; 中间偏右
中间偏左与标准库一致，减少维护成本。除非有明确证据表明中间偏右在特定场景下性能显著更优，否则应默认使用中间偏左的计算方式
2.2随机选数
srand((unsigned int)time(NULL));
int midi = left + rand() % (right - left + 1);left 是 当前区间的首元素的下标，通过rand函数产生随机值以随机选择基准值
随机选数的方法，可能会因分区不平衡导致效率降低，
三数取中能够保持平均性能，降低极端分区不平衡的风险
所以我们一般使用三数取中来选取基准值
2.3基准值选取代码
int midi = GetMidi(a, left, right);if (midi != left)Swap(&a[left], &a[midi]);3.单趟排序的三种方法
我们选好了基准值，就需要将其放置在正确的位置上此时有
hoare法、挖坑法、前后指针法实现该操作
3.1hoare法
3.1.1hoare法单趟图解
未作三数取中处理
以升序为例
hoare版本的思想就是：
(1)left、right初始值分别是当前区间首元素的下标、尾元素的下标(也可以是指针)
(1)选定的基准值Key是首元素，就让right 先向左移动找到比Key小的元素，再让left 向右移动找到比Key大的元素，找到之后交换两元素的位置，再继续让right先走找小left后走找大， 直到left\right相遇为止，此时交换Ke和相遇位置的元素的位置
(1)选定的基准值Key是尾元素，就让left先向右走找大，right后走找小......
首元素是基准值时，必须让right先走才能使相遇位置的元素小于等于基准值：
(1)right找到小，left找不到大，left碰right直接相遇，交换位置可满足正确位置的定义
(2)right找不到小，直接与left位置即基准值相遇，自己与自己交换，不影响
(3)right找到小，left找到大，交换之后再发生上面两种情况而已
如果left先走1个位置，就可能发生right找不到小而直接与left相遇的情况
此时，基准值本应自己与自己交换变为了与下一个位置交换，不符合正确位置的定义
如果让left先走找大，也可能出现找不到大而直接与right相遇的情况，交换后不符合正确位置的定义
3.1.2hoare法单趟代码
int PartSort1(int* a, int left, int right)
{//三数取中获取基准值int midi = GetMidi(a, left, right);if (midi != left)Swap(&a[left], &a[midi]);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[right]);//返回相遇位置的下标，便于后续分区间递归keyi = right;return keyi;
}
(1)在找大、小的过程中要时刻注意left、right不要越界
(2)等于Key的数组元素既可以在正确位置的左边也可以在右边，所以
while (left < right && a[right] >= a[keyi])这里面需要用>=、<=，如果不加等于，当数组中间有与Key相等的两个值时，就会出现死循环的现象
3.2挖坑法
3.2.1挖坑法单趟图解
基准值未作三数取中处理
以升序为例
挖坑法的思想就是：
(1)left、right初始值分别是当前区间首元素的下标、尾元素的下标(也可以是指针)
(1)创建变量Key存储基准值
(1)选定的基准值Key是首元素，就让right 先向左移动找到比Key小的元素，找到就填充坑位，坑位转移到右边，再让left 向右移动找到比Key大的元素，找到就填充坑位，坑位转移到左边再继续让right先走找小填充坑位并转移坑位left后走找大填充坑位并转移坑位，..... 直到left\right相遇为止，此时用Key填充坑位
(1)选定的基准值Key是尾元素，就让left先向右走找大，right后走找小......
首元素是基准值时，必须让right先走才能使相遇位置成为正确的坑位：
(1)right找到小，填充坑位并正确转移之后，left找不到大，left碰right相遇，位置满足正确位置的定义
(2)right找不到小，直接与left位置即基准值相遇，原位置填充，不影响
(3)right找到小，left找到大，交换之后再发生上面两种情况而已
如果left先走1个位置，就可能发生right找不到小而直接与left相遇的情况
此时，基准值本应填充原位置变为了填充下一个位置，不符合正确位置的定义
如果让left先走找大，也可能出现找不到大而直接与right相遇的情况，填充坑位并正确转移之后，最终坑位不符合正确位置的定义
3.2.2挖坑法单趟代码
int PartSort2(int* a, int left, int right){//三数取中获取基准值int midi = GetMidi(a, left, right);if (midi != left)Swap(&a[left], &a[midi]);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.3前后指针法
3.3.1前后指针法单趟图解
基准值未作三数取中处理
以升序为例
选定的基准值Key是首元素时，前后指针的思想就是：
(1)prev、cur初始值分别是当前区间首元素的下标、第二个元素的下标(也可以是指针)
如果cur位置的值小于Key，++prev，然后交换cur位置与prev位置的值，再++cur
如果cur位置的值大于等于Key，++cur
这样之后，prev要么紧邻cur，要么与cur之间间隔着比Key大的值
反复进行上面操作之后，比Key大的值就会向后移动，比Key小的值就会向前移动
prev所在位置的元素小于等于Key，prev最终所在位置就是正确位置
3.3.2前后指针法单趟代码
int PartSort3(int* a, int left, int right)
{//三数取中获取基准值int midi = GetMidi(a, left, right);if (midi != left)Swap(&a[left], &a[midi]);int keyi = left;int prev = left;int cur = left + 1;//cur位置的值小于基准值，就与++prev位置的值进行交换，++cur// 大于 ，++curwhile (cur <= right){if (a[cur] < a[left] && ++prev != cur)Swap(&a[cur], &a[prev]);++cur;}//基准值与prev位置的值交换//prev位置的值始终是小于等于基准值的Swap(&a[keyi], &a[prev]);keyi = prev;return keyi;
}if (a[cur] < a[left] && ++prev != cur)Swap(&a[cur], &a[prev]);这段代码巧妙地运用了&&运算符短路求值及前置++先++再返回的特点来
减少自己与自己交换的冗余操作
4.快速排序排序图解及完整代码
单趟排序将选取的基准值放置到正确位置之后，数组被分割为左右两部分
左右两部分再重复进行选值放值分割的操作，直到区间只有一个元素或不存在为止
例如，当数组只有 0、1两个元素时，hoare法返回的keyi是0，
区间就会被分割为[0, -1](不存在)、[1, 1](只有一个元素)
整个排序类似于二叉树的前序遍历
void QuickSort(int* a, int left, int right)
{if (left >= right)return;int keyi = PartSort1(a, left, right);//[left, keyi - 1] keyi [keyi + 1, right]QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}小规模(小于16)数组使用递归会冗余，
这点数量的数组选择直接插入的方法进行优化更好
void QuickSort(int* a, int left, int right) {if (left >= right)return;if (right - left + 1 < 10){InsertSort(a + left, right - left + 1);}else{int keyi = PartSort1(a, left, right);//[left, keyi - 1] keyi [keyi + 1, right]QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);} }
5.快速排序的时间复杂度与空间复杂度
递归实现快速排序时：
(1)固定选取当前数组的首元素或尾元素作为基准值，而不采用三数取中、随机选数调参时，
当数组有序，会导致每次划分只能减少一个元素（即每次递归调用处理的子数组长度仅减少 1），导致递归层次太深，遍历次数变为(N + 1) * N) / 2 时间复杂度退化为O(N^2)
(1)调参之后
前面说了，递归调用相当于时二叉树的前序遍历
此时就约有logN层，而每一层的个数还是在N这个量级(尽管有减少)，记住结论就行
所以时间复杂度可被优化为O(N*logN)
(1)快速排序的空间复杂度主要由递归调用栈的深度决定，此外还包括划分过程中的临时变量开销（可忽略）
所以时间复杂度最好为O(logN)，最差为O(N)
