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