快速排序的深入优化探讨

快排性能的关键点分析

决定快排性能的关键点是每次单趟排序后，key对数组的分割，如果每次选key基本⼆分居中，那么快排的递归树就是颗均匀的满⼆叉树，性能最佳。但是实践中虽然不可能每次都是⼆分居中，但是性能也还是可控的。但是如果出现每次选到最小值/最大值，划分为0个和N-1的子问题时，时间复杂度为O(N^2)，数组序列有序时就会出现这样的问题，但是当数组中有大量重复数据时，之前的快速排序方法就会比较慢，因此我们需要更进算法。

三路排序

三路划分算法思想讲解：
当面对有大量跟key相同的值时，三路划分的核心思想有点类似hoare的左右指针和lomuto的前后指针的结合。核心思想是把数组中的数据分为三段 [比key小的值]、[跟key相等的值] 、[比key大的值]，所以叫做三路划分算法。结合下图，理解⼀下实现思想：

1. key默认取left位置的值。
2. left指向区间最左边，right指向区间最右边，cur指向left+1位置。
3. cur遇到比key小的值后跟left位置交换，换到左边，left++，cur++。
4. cur遇到比key大的值后跟right位置交换，换到右边，right--。
5. cur遇到跟key相等的值后，cur++。
6. 直到cur>right结束

#include<stdio.h>
#include<time.h>
#include<stdlib.h>void swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}void Print(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ",a[i]);}printf("\n");
}void QuickSort(int* a, int left,int right)
{if (left >= right)return;//随机选keyint randi = left + (rand() % (right - left + 1));swap(&a[left], &a[randi]);int begin = left;int end = right;int key = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[key]){swap(&a[cur],&a[left]);cur++;left++;}else if (a[cur] > a[key]){swap(&a[cur], &a[right]);right--;}else if (a[cur] == a[key]){cur++;}}QuickSort(a,begin,left-1);QuickSort(a, right + 1, end);
}int* sortArray(int* nums, int numsSize, int* returnSize) 
{srand((unsigned int)time(NULL));QuickSort(nums, 0, numsSize - 1);*returnSize = numsSize;return nums;
}int main()
{int arr[] = {2,5,7,6,1,4,3,9,8};int n = sizeof(arr) / sizeof(arr[0]);Print(arr,n);int* tmp=sortArray(arr, n,&n);Print(tmp, n);return 0;
}

自省排序（ introsort）

自省排序的思路就是进行自我侦测和反省，快排递归深度太深（sgi stl中使用的是深度为2倍排序元素数量的对数值）那就说明在这种数据序列下，选key出现了问题，性能在快速退化，那么就不要再进行快排分割递归了，改换为堆排序进行排序。

#include<stdio.h>
#include<time.h>
#include<stdlib.h>void Print(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ",a[i]);}printf("\n");
}void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
//向下调整算法
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){//选出左右孩⼦中⼤的那⼀个if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
//堆排序
void HeapSort(int* a, int n)
{//建堆--向下调整建堆-- O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);--end;}
}
//插入排序
void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++){int end = i - 1;int tmp = a[i];//将tmp插⼊到[0, end]区间中，保持有序while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}void IntroSort(int* a, int left, int right, int depth, int defaultDepth)
{if (left >= right)return;//数组⻓度⼩于16的小数组，换为插入排序，简单递归次数if (right - left + 1 < 16){InsertSort(a + left, right - left + 1);return;}//当深度超过2 * logN时改用堆排序if (depth > defaultDepth){HeapSort(a + left, right - left + 1);return;}depth++;int begin = left;int end = right;int randi = left + (rand() % (right - left + 1));Swap(&a[left], &a[randi]);int prev = left;int cur = prev + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;IntroSort(a, begin, keyi - 1, depth, defaultDepth);IntroSort(a, keyi + 1, end, depth, defaultDepth);
}void QuickSort(int* a, int left, int right)
{int logn = 0;int depth = 0;int N = right - left + 1;for (int i = 1; i < N; i *= 2){logn++;}IntroSort(a, left, right, depth, logn * 2);
}int* sortArray(int* nums, int numsSize, int* returnSize) 
{srand((unsigned int)time(NULL));QuickSort(nums, 0, numsSize - 1);*returnSize = numsSize;return nums;
}int main()
{int arr[] = {2,5,7,6,1,4,3,9,8};int n = sizeof(arr) / sizeof(arr[0]);Print(arr,n);int* tmp=sortArray(arr, n,&n);Print(tmp, n);return 0;
}