? ? ? ? 其实就是对快速排序的优化。
一、挖坑法
? ? ? ? 这种方法其主要是好理解，其快排的本质却没有改变。
? ? ? ? 其主要思路是，把key对应位置空出来，然后两边同样找大找小，只不过这次把找到的数，放到空位置处。
? ? ? ? 找到最后左边和右边相遇，此时相遇的位置必定为坑，再把key放过来就好。
? ? ? ? 这样一次排序就完成了。如果其左边有坑，天然要从右边开始找。如果key找的是右边，其天然要从左边开始找。
? ? ? ? 这种找法跟传统的排序其本质差不多，但是要注意其数据移动的位置的不同于传统快排的。如果有选择题是，快排的移动顺序的题目，要考虑到这个点。
//挖坑法
int PostSort(int* arr, int begin, int end)
{
int key = arr[begin];
int piti = begin;
while (begin<end)
{
while (begin<end && arr[end]>=key) {
end--;
}
arr[piti] = arr[end];
piti = end;
while (begin<end && arr[begin]<=key)
{
begin++;
}
arr[piti] = arr[begin];
piti = begin;
}
arr[piti] = key;
return piti;
}
void QuickSort(int* arr, int begin, int end)
{
if (begin >= end) {
return;
}
int pos = PostSort(arr,begin,end);
QuickSort(arr, begin, pos - 1);
QuickSort(arr, pos + 1, end);
}二、前后指针法
? ? ? ? 定义两个指针，cur往前走，遇到数据小于 key 则 pre 往前走一步。cur遇到比key大的，自己往前走，pre不动。
????????直到遇到下一个比key小的数，pre往前走一步，然后交换数据。
?????????
????????
? ? ? ? cur遇到比key大的数据后，两个指针就拉开了距离。
?
? ? ? ? ?继续重复上面的步骤，直到cur到头后，交换key和pre位置的数据。
?
代码：
//前后指针法
int PostSort2(int* arr, int begin, int end)
{
int cur = begin + 1;
int pre = begin;
int key = arr[begin];
while(cur <= end) {
if (arr[cur]<key && ++pre!=cur) {
swap(&arr[pre], &arr[cur]);
}
cur++;
}
swap(&arr[pre],&arr[begin]);
return pre;
}
void QuickSort(int* arr, int begin, int end)
{
if (begin >= end) {
return;
}
int pos = PostSort2(arr, begin, end);
QuickSort(arr, begin, pos - 1);
QuickSort(arr, pos + 1, end);
}三、 快排速度优化
? ? ? ? 注意，理解了快速排序的原理，那么就知道，如果key找到后的位置，一直是中位数，那么其数组区间二分 logN。递归下去每一层的时间复杂度为 N。
? ? ? ? 所以得，其快速排序时间复杂度最快的情况为 N*logN。
? ? ? ? 如果key选择的是最小或者最大，那么其为最坏的情况。而如果数组有序（或者接近有序），那么其选择的key一定为最小或最大。
? ? ? ? 其时间复杂度为一个等差数列，所以得出，快速排序在有序或者接近有序的情况下，时间复杂度为O(N^2)。
PS：而且这里递归太深会造成，栈溢出。
1、三数取中
? ? ? ? 取开始 中间 结尾，选不是最大，也不是最小那个。强行把数组变为二分，提高运行效率。
//三数取中
int GetMidIndex(int* arr, int begin, int end)
{
int mid = (begin + end) / 2;
if (arr[begin] < arr[mid]) {
if (arr[mid] < arr[end])
{
return mid;
}
else if (arr[end] < arr[begin])
{
return begin;
}
else //arr[begin] < arr[end]
{
return end;
}
}
else { // arr[begin] > arr[mid]
if (arr[mid] > arr[end])
{
return mid;
}
else if (arr[begin] > arr[end])
{
return end;
}
else //arr[begin]<arr[end]
{
return begin;
}
}
}
//前后指针法
int PostSort2(int* arr, int begin, int end)
{
int cur = begin + 1;
int pre = begin;
int key = begin;
int mid = GetMidIndex(arr, begin, end);
swap(&arr[key],&arr[mid]);
while(cur <= end) {
if (arr[cur]<arr[key] && ++pre != cur) {
swap(&arr[pre], &arr[cur]);
}
cur++;
}
swap(&arr[pre],&arr[begin]);
return pre;
}
void QuickSort(int* arr, int begin, int end)
{
if (begin >= end) {
return;
}
int pos = PostSort2(arr, begin, end);
QuickSort(arr, begin, pos - 1);
QuickSort(arr, pos + 1, end);
}
2、小区间优化
? ? ? ? 假设一个数组进行快速排序，其递归图入下。
? ? ? ? ?这里可以发现，部分小区间，其实就没必要再使用快速排序，这里可以使用其他排序来代替。
PS：这里把最后一层优化掉，就相当于去掉了50%的调用。
//前后指针法
int PostSort2(int* arr, int begin, int end)
{
int cur = begin + 1;
int pre = begin;
int key = begin;
int mid = GetMidIndex(arr, begin, end);
swap(&arr[key],&arr[mid]);
while(cur <= end) {
if (arr[cur]<arr[key] && ++pre != cur) {
swap(&arr[pre], &arr[cur]);
}
cur++;
}
swap(&arr[pre],&arr[begin]);
return pre;
}
// 插入排序
void InsertSort(int* a, int n)
{
for (int i = 0; i < n; i++) {
int end = i;
int temp = a[end + 1];
while (end >= 0)
{
if (temp < a[end]) {
a[end + 1] = a[end];
end--;
}
else {
break;
}
a[end + 1] = temp;
}
}
}
//小区间优化
void QuickSort_2(int* arr, int begin, int end)
{
if (begin >= end) {
return;
}
if (end - begin > 2) { //区间小于 2 ，就使用插入排序
int pos = PostSort2(arr, begin, end);
QuickSort(arr, begin, pos - 1);
QuickSort(arr, pos + 1, end);
}
else {
//插入排序
InsertSort(arr + begin, end - begin + 1 ); //
}
}
3、递归改非递归
? ? ? ? 如果递归深处太深，那么会出现栈溢出。那么这里可以使用数据结构——栈来模拟递归的结构。因为这里栈的数据都在堆上生成的，堆的空间很大，所以可以进行深层次的调用。
?
? ? ? ? 首先为了对应其递归的顺序，这里先把right入栈，这样出来先使用的就是left。
? ? ? ? 再这个区间内排序完成后呢，再次把以key为分割的两个区间，再入栈。
? ? ? ? ?然后再进行排序，不过这里要注意，这里key-1到 left 的区间要全部排完后，才会轮到key+1到 right 区间排序。
? ? ? ? 会发现这里就跟递归非常相似了（跟二叉树的前序遍历也非常像）。
代码：
//前后指针法
int PostSort2(int* arr, int begin, int end)
{
int cur = begin + 1;
int pre = begin;
int key = begin;
int mid = GetMidIndex(arr, begin, end);
swap(&arr[key],&arr[mid]);
while(cur <= end) {
if (arr[cur]<arr[key] && ++pre != cur) {
swap(&arr[pre], &arr[cur]);
}
cur++;
}
swap(&arr[pre],&arr[begin]);
return pre;
}
//快速排序 递归改非递归
void QuickSortNonR(int* arr, int begin, int end)
{
stack St;
StackInit(&St);
StackPush(&St,end);
StackPush(&St,begin);
while (!StackIsEmpty(&St))
{
int left = StackTop(&St);
StackPop(&St);
int right = StackTop(&St);
StackPop(&St);
int key = PostSort2(arr,left,right);
if (right > key + 1) {
StackPush(&St, right);
StackPush(&St, key + 1);
}
if (left < key - 1) {
StackPush(&St, key-1);
StackPush(&St, left);
}
}
StackDestory(&St);
}
测试：
?
拓展思路：
? ? ? ? 使用队列来模拟递归，实现快速排序。其与用栈模拟的方式，单趟排序的顺序不一样。
? ? ? ? 这里先把 left 和 right 入列，在此区间内进行排序。
? ? ? ? 排序完成后把以key分割的两个区间入列。
? ? ? ? 这里前一个区间排序完成后，把它下一个区间入列。
? ? ? ? ?再下一次取出的区间是6 到 9 ，会发现跟前面的二叉树的层序遍历相似。
? ? ? ? ?虽然其排序的顺序跟递归的方式不同，但是其每个区间相互不影响，所以其结果是相同的，效果一样。