前言：
还记得上次的快速排序吗？还记得 key 是怎么取的吗？当时我直接把数组的起始元素作为了 key 值，其实这样做是有弊端的，试想：一个降序的数列，要排列成升序的序列，最大的数字作为 key 值，那岂不是效率较低？所以，这就意味着仍有优化的空间，那么这期就来优化下快速排序。
注：
这篇博客属于数据结构内容，建议学习完C语言的小伙伴食用~
目录
Part1:取随机数法
1.思想
这个思想就是字面意思啦 ~ 就是取一个数组中极大值与极小值之间的一个随机数
为什么这样做会优化一点时间呢？
我们回忆一下快速排序，它的思想就是找一个 key 值，一趟下来，数组 左部分 的数字都 小于 key， 右部分 的数字都 大于 key；
我们进行调整，就是在 key的选取上下功夫，
试想：你选择的 key 值是数组中最大的，一趟下来，只有 key 值的位置变了，那岂不是挫到家了？
我们要尽量避免这种情况发生，就可以随机一些，数字的量越大，取到最大值的概率越小，近似认为避免了这种情况。
2.实现
实现很简单，加一个生成随机数的函数，由于取的是 keyi，即 key 的下标，所以随机数模上数组的长度，再加上 left 即可(一趟过后开始递归， 左部分下标不是从0开始 )：
//快排(前后指针法)(取随机数优化) void QuickSort3(int* a, int left, int right) { if (left >= right) return; // 取随机数 //int randi = left + (rand() % (right - left)); //Swap(&a[randi], &a[left]); // 交换randi与left对应的数字 int keyi = left; int key = a[left]; int prev = left; int cur = left + 1; while (cur <= right) { if (a[cur] < key && ++prev != cur) Swap(&a[cur], &a[prev]); cur++; } Swap(&a[keyi], &a[prev]);//与下标为keyi的交换 keyi = prev; //递归 QuickSort3(a, left, keyi - 1); QuickSort3(a, keyi + 1, right); }
Part2:三数取中法
1.思想
在看随机数排列的时候，我相信你已经开始思考这个问题了：
与其说是避免取到不合适的值，不如说是直接取最合适的值 ，
是的，三数取中法就是取最合适的值，那么什么样的值是最合适的呢？
中值最合适；
如何找到中值呢？
最简单的就是取三个值：最左值，最右值，中间值挨个比较；
下面看看是如何实现的：
2.实现
//三数取中 int GetMidi(int* a, int left, int right) { int mid = (left + right) / 2; if (a[left] < a[mid]) { if (a[mid] < a[right]) return mid; else if (a[left] > a[right]) return left; else return right; } else // a[left] > a[mid] { if (a[left] < a[right]) return left; else if (a[mid] > a[right]) return mid; else return right; } }
解释：
其实就是分两种大情况：
在这两种大情况下取中。
接入排序中，就是这样的：
int midi = GetMidi(a, left, right); if (midi != left) Swap(&a[midi], &a[left]);
Part3:小区间调整
1.思路
有这种调整方法是因为当数据数量较小时，利用快速排序未免有杀鸡焉用牛刀的感觉，
想想，五个数字排有序，需要调用七次快排函数，是不是大题小作？
所以在这种数据量小的情况下，不妨利用其他的排序，
那么选择哪个排序呢？
选择最灵活的， 稳定的，那就是插入排序。
2.实现
可以在数字长度小于10的情况下进行插入排序，大于10就进行快速排序：
void QuickSort(int* a, int left, int right) { if (left >= right) return; int keyi = PartSort3(a, left, right); // 小区间调整 if ((right - left + 1) > 10) { QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); } InsertSort(a + left, right - left + 1);// 插入排序不再赘叙 }
Part4:三种方法对比
1.测试性能的试金石
生成N个随机数，测试每种排序的性能，输出的是排序所用的时间（单位毫秒）
// 测试排序的性能对比 void TestOP() { srand(time(0)); const int N = 1000000;// 数据的数量 int* a1 = (int*)malloc(sizeof(int) * N); int* a2 = (int*)malloc(sizeof(int) * N); int* a3 = (int*)malloc(sizeof(int) * N); int* a4 = (int*)malloc(sizeof(int) * N); int* a5 = (int*)malloc(sizeof(int) * N); int* a6 = (int*)malloc(sizeof(int) * N); for (int i = 0; i < N; ++i) { a1[i] = rand(); a2[i] = a1[i]; a3[i] = a1[i]; a4[i] = a1[i]; a5[i] = a1[i]; a6[i] = a1[i]; } int begin1 = clock(); //InsertSort(a1, N); int end1 = clock(); int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); int begin3 = clock(); //SelectSort(a3, N); int end3 = clock(); int begin4 = clock(); HeapSort(a4, N); int end4 = clock(); int begin5 = clock(); QuickSort2(a5, 0, N - 1); int end5 = clock(); int begin6 = clock(); //MergeSort(a6, N); int end6 = clock(); printf("InsertSort:%d\n", end1 - begin1); printf("ShellSort:%d\n", end2 - begin2); printf("SelectSort:%d\n", end3 - begin3); printf("HeapSort:%d\n", end4 - begin4); printf("QuickSort:%d\n", end5 - begin5); printf("MergeSort:%d\n", end6 - begin6); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); }
2.开始测试
这里只测试快速排序：
注意：只是简单的样本采集(甚至不算样本)，不具有统计学意义，仅供参考
似乎单独三数取中法是最好的... ...
我做完之后对这个数据挺诧异的：
为什么三数取中法与小区间调整共用之后更慢了？
有研究过的大佬可以教教我🤣
总结：
(总结)
