上篇我们介绍了hoare基础版，但是这种代码存在缺陷，所以我们提出了两种解决方案。主流的解决方案就是【三数取中选key】
GitMidi三数取中
在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。在此我们采用三数取中法，也就是取左端、中间、右端三个数的下标，然后进行排序，将中间数作为枢纽值。
- 取的三个数的中位数的下标
- 取的是下标❗
- 数值两两比较
- 对快速排序的单趟的优化，三数取中是走快速排序逻辑（每趟的优化）
- 三数取中：取三个数中的中位数下标，选到合适的数，避免选取到最小的最大的数，对顺序结构的效率优化很好。
整体思想
- 设置三个值下标：begin // end // midi
- 两个两个比较
- 得到中位数的下标
图解分析
【顺序序列优化前：等差数列O（N^2)】
【顺序序列优化后：类似二叉树等比数列O（N*logN)】 
代码实现
//三数取中 int GetMidi(int* a, int begin, int end) { int midi = (begin + end) / 2; if (a[begin] < a[end]) { if (a[begin] > a[midi]) { return begin; } else if(a[end]<a[midi]) { return end; } else { return midi; } } else//begin>=end { if (a[midi] < a[end]) { return end; } else if (a[midi] > a[begin]) { return begin; } else { return midi; } } }
小区间优化
除了三数取中对顺序序列的快速排序起到了优化效果。如果数据量过大会造成
- 快速排序递归层数太多，在debug版本底下会栈溢出。
- 对于数据量过小用快速排序/希尔排序/堆排，效率反而没有直接插入排序高。（杀鸡用牛刀）直接插入排序对局部有序序列很友好。
- 小区间优化走的直接插入的逻辑（整体的优化）
- 注意❗❗❗❗小区间优化 优化的是递归的层数。
综上所诉，我们在用递归实现快速排序的基础上，如果数据量递归到一定程度过小，可以采用直接插入排序。这就是小区间优化。
整体思想
那么主要是优化那几层递归呢？
- 主要优化递归层数的最后3~4层
- 最后3~4层的递归层数占据了总的递归层数的80%（根据二叉树的性质）
- 当数据量end-begin+1<=10的时候，让序列执行直接插入排序
- 注意❗❗❗❗每段数据序列被分割了起始位置不一样不都是a，要用a+begin表示
- 区间是[begin，end] ，此区间的数据量是end-begin+1
所以：小区间优化=数据量大（递归）+数据量小&递归层数多&最后3~4层（用插入排序）
图解分析
代码实现
void QuickSort(int* a, int begin,int end) { if (begin >= end)//只有1个元素 没有区间 { return; } //<10个数字走插入逻辑 if (end - begin + 1 <= 10) { InsertSort(a + begin, end - begin + 1); } //>10个数走快排逻辑 else { int keyi = PartSort1(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); } }
Hoare优化总代码
void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } //直接插入 void InsertSort(int* a, int n) { // [0, end] 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]; --end; } else { break; } } a[end + 1] = tmp; } } //三数取中 int GetMidi(int* a, int begin, int end) { int midi = (begin + end) / 2; if (a[begin] < a[end]) { if (a[begin] > a[midi]) { return begin; } else if(a[end]<a[midi]) { return end; } else { return midi; } } else//begin>=end { if (a[midi] < a[end]) { return end; } else if (a[midi] > a[begin]) { return begin; } else { return midi; } } } //hoare版本&三数取中&每趟的优化 int PartSort1(int* a, int begin, int end)//返回分割线 { int left = begin; int right = end; int keyi = begin; //三数取中 int midi = GetMidi(a, begin, end); Swap(&a[keyi], &a[midi]); while (left < right) { //找小 while (left < right && a[right] >= a[keyi]) { right--; } //找大 while (left < right && a[left] <= a[keyi]) { left++; } //找到了 Swap(&a[right], &a[left]); } Swap(&a[left], &a[keyi]); keyi = left; return keyi; //分割 [begin,keyi-1] keyi [keyi+1,end] } //小区间优化&整体的优化 void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; } //<10个数字走插入逻辑 if (end - begin + 1 <= 10) { InsertSort(a + begin, end - begin + 1); } //>10个数走快排逻辑 else { int keyi = PartSort1(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); } }
🙂感谢大家的阅读，若有错误和不足，欢迎指正。
