优化
借助题目：排序数组
给一个数组，要求给他排序，要求很简单，却只有50%的通过率，力扣标记简单不一定简单，标记中等那一定是有点难。
这题很显然，普通的排序比如冒泡排序，插入排序，选择排序是过不了的，我们刚刚学习了快排，何不尝试一波。
void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } void QuickSort1(int* a, int begin, int end) { if (begin >= end) { return; } int keyi = PartSort1(a, begin, end); QuickSort1(a, begin, keyi - 1); QuickSort1(a, keyi + 1, end); } //hoare版本 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]); return left; } int* sortArray(int* nums, int numsSize, int* returnSize){ QuickSort1(nums, 0, numsSize-1); *returnSize=numsSize; return nums; }
快排解题的代码如下
然而却发现
用hoare大佬的方法走一遍，发现时间复杂度在这组用例上为O(N^2)，right一直向右移，不会分成左右两组，一直递归n次，right向前的次数从n到1，这样的话花费的时间太多了，针对这种情况进行优化，就要介绍三数取中。
三数取中
如何防止上面最坏的情况发生？
只需要防止最左边的数为该组数里最小的数即可。
可以找出left位置的值和right位置的值及（left+right)/2数组中间下标的值，找出他们三个中间大小的一个，与a[left]进行交换，这样就可以防止left是数组中最小的元素这种情况的发生。
将三数取中抽离成函数
//三数取中 int GetMidi(int* a, int left, int right) { int mid = (left + right) / 2; //left mid right if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return left; } else { return right; } } else { if (a[mid] > a[right]) { return mid; } else if (a[left] > a[right]) { return left; } else { return right; } } }
在每次partsort前搞来中间值的坐标，与left进行交换
int midi=GetMidi(a,left,right)
Swap(&a[left[,&a[midi]);
加上三数取中再次运行
然而。。。。
再次出乎意料，如果是全部数字都一样或者有大量重复数据，right还是像刚才有序数组的情况一样，right一直向左，时间复杂度为O(N^2)，此时三数取中也没用了，无论怎么取，取到的都是2。针对这种情况怎么办？
三路分化
将hoare大佬的方法和双指针法结合起来，将数组分为三个部分，左边小于key，中间的区段是等于key的，右边的部分是大于key的。
设置三个指针，两个指针用于位置的交换是数组划分为三个区间，一个指针用于遍历。
看思路
最后在left和right之间的部分就是等于5的部分，left之前皆小于key，right之后皆大于key。
总结下来只有以下三种情况
- cur的值小于key，交换cur的值和left的值，cur++,left++。
- cur的值等于key，直接++cur
- cur的值大于key，交换cur和right的值，cur不能动。
代码实现
void QuickSort1(int* a, int left, int right) { if (left >= right) { return; } int begin = left;//记录左右边界 int end = right; int midi = GetMidi(a, left, right); Swap(&a[left], &a[midi]); int key = a[left]; int cur = left + 1; while (cur <= right) { if (a[cur] < key)//重点理解 { Swap(&a[cur], &a[left]); ++left; ++cur; } else if (a[cur] > key) { Swap(&a[cur], &a[right]); } else { ++cur; } } QuickSort1(a, begin, left-1); QuickSort1(a, right+1, end); }
这次我们信心满满，如果数组的元素全部为2的话，遍历一遍，right和left直接相遇，甚至只需要O(N)的时间就可以完成。
更改代码后运行。
还是超出时间限制，这又是为什么呢？这道题对快速排序做了针对性的处理，普通的快排很难过这道题，他会检测我们的三数取中，然后搞出对应的一串数字，让每次取出的数都是数组中倒数第二大，这样的话时间复杂度还是很大。
解决方法：
选取数组中任意位置的数和left位置和right作比较选出keyi，而不是一直取中间坐标与他们相比较，用rand函数进行操作，使我们选数位置没有规律可循，这样编译器就不能根据我们所写的代码搞出针对性用例。
代码如下：
int GetMidi(int* a, int left, int right) { //int mid = (left + right) / 2; int mid =left+(rand()%(right-left)); //left mid right if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return left; } else { return right; } } else { if (a[mid] > a[right]) { return mid; } else if (a[left] > a[right]) { return left; } else { return right; } } } void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } void QuickSort1(int* a, int left, int right) { if (left >= right) { return; } int begin = left;//记录左右边界 int end = right; int midi = GetMidi(a, left, right); Swap(&a[left], &a[midi]); int key = a[left]; int cur = left + 1; while (cur <= right) { if (a[cur] < key) { Swap(&a[cur], &a[left]); ++left; ++cur; } else if (a[cur] > key) { Swap(&a[cur], &a[right]); --right; } else { ++cur; } } QuickSort1(a, begin, left-1); QuickSort1(a, right+1, end); } int* sortArray(int* nums, int numsSize, int* returnSize){ srand(time(NULL)); QuickSort1(nums, 0, numsSize-1); *returnSize=numsSize; return nums; }
运行后如图
可以发现所用时间还是很长，这道题如果用堆排序和shell排序都是很好过的，放在这里是为了提升我们对快排的理解和掌握。
小区间优化
在上边显示递归流程的图中，我们可以看到递归的过程，类比树的结构，树的每一个节点都是一次递归，树的最后一排的节点个数占全部节点的50%，倒数第二行占总个数的25%，如果分成的数组的量的变小到一定的个数的时候可以不再使用递归，而是选择其他的方法进行排序，可以减少大量的递归次数。
这种方法叫做小区间优化，使用什么排序比较好呢？冒泡排序和选择排序的时间复杂度为O（N²），选择排序的时间复杂度最高为O（N²），可以使用选择排序进行小区间优化，从而减少大量的递归次数
插入排序及小区间优化后的代码如下
//插入排序 void InsertSort(int* a, int n) { //[0,end]有序，把end+1的位置插入到前序序列 //控制[0,end+1]有序 for (int i = 0; i < n - 1; i++) { int end = i; int tmp = a[end + 1]; while (end >= 0) { if (tmp < a[end]) { a[end + 1] = a[end]; } else { break; }-+ --end; } a[end + 1] = tmp; } } //加上小区间优化 void QuickSort2(int* a, int begin, int end) { if (begin >= end) { return; } if ((end - begin + 1) > 10)//如果一个数组的元素小于10，就进行插入排序 { int keyi = PartSort2(a, begin, end); QuickSort2(a, begin, keyi - 1); QuickSort2(a, keyi + 1, end); } else { InsertSort(a + begin, end - begin + 1); } } //加上小区间优化 void QuickSort2(int* a, int begin, int end) { if (begin >= end) { return; } if ((end - begin + 1) > 10) { int keyi = PartSort2(a, begin, end); QuickSort2(a, begin, keyi - 1); QuickSort2(a, keyi + 1, end); } else { InsertSort(a + begin, end - begin + 1); } }
快排非递归版
复习一下：它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归 进行，以此达到整个数据变成有序序列。
将一整个数组不断细分，在不断划分的过程中进行有序化，最终完成排序的功能。在前边partsort函数中，我们只要通过某种方法得到分成一组一组的小数组段的left和right即可。
上边的说明递归的流程图是直接全部展开的，实际上是一直向左划分，直到分出的数组left和right相等，然后回到上步。
如图所示
结合代码就很容易明白。
在非递归版本我们想和递归的步骤相同，如何得到上述递归过程中的left和right?这是问题之所在，而且在递归过程中向partsort1传入不同的left和right。
可以借助栈先进先出的功能来实现，push起始的left和right，进行第一次partsort，知道了left和right后，将他们再pop掉。
void QuickSortNonR(int* a, int begin, int end) { ST st; STInit(&st); STPush(&st, end); STPush(&st, begin); while (!STEmpty(&st)) { int left = STTop(&st); STPop(&st); int right = STTop(&st); STPop(&st); int keyi = PartSort1(a, left, right); if (keyi + 1 < right) { STPush(&st, right); STPush(&st, keyi + 1); } if (left < keyi - 1) { STPush(&st, keyi - 1); STPush(&st, left); } } STDestroy(&st); }
快排讲到这里就结束啦，如果你有耐心看完的话你一定会对快排的掌握有所提升哒。
加油！
