【算法】快速排序
用例
数据序列或记录：【1, 7, 3, 5, 2, 0, 6, 4】
思路
快速排序思路分两部分：部分排序 + 逐层分治
- 部分排序
- 在数据序列【1, 7, 3, 5, 2, 0, 6, 4】中选取一个值作为中轴值，如：3。
- 对数列进行排序，使得数列调整为小，中，大三部分的结构，如【1, 2, 0, 3, 7, 5, 6, 4】。
- 小：小于中轴值的无序集合，即【1, 2, 0】。
- 中：仅含中轴值的集合，即【3】。
- 大：大于中轴值的无序集合，即【7, 5, 6, 4】。
注：中轴值的选择，可以是随机的，也可以是固定的，一般会选择头部（如：1）或尾部（如：4）的值。
- 逐层分治
- 当完成“部分排序”后，数列分成了小，中，大三个子集合。
- 此时如果对小【1, 2, 0】、大【7, 5, 6, 4】两个子集合分别套用“部分排序”的方法进行排序，则每个子集合也可分为小，中，大的子子集合。
- 重复上述操作直到一个元素的集合为止，则可实现整个数列的排序。
上述对数列进行拆分重复处理的思路即为逐层分治的思想。
一般实现方式为递归调用，如果采用迭代方法需要结合栈结构来实现。
实现方法
-
部分排序
部分排序的实现可采用左右指针法，挖坑填坑法、前后指针法。
左右指针法
1、选取中轴值axis=4，此处从尾部选取，即为4。
2、设置左右指针L，R
3、向右移动L，直到发现>=axis的为止，向左移动R，直到发现<axis为止，交换L、R对应的值。
4、重复步骤3，直到L>=R为止，然后交换L与axis对应的值。
//左右指针法挖坑填坑法
1、选取中轴值axis=4（尾部选取），另开空间存储（也可不开空间，但是R指针必须不能与当前位一致），即挖坑。
2、设置左右指针L，R（另开空间情况下R为与axis的位置一致）。
3、从远离坑的一侧进行缩进，即L右移动，直到L>=axis停止。将当前值填入坑中（此时的坑为R所在位置），之后产生新的坑（即L所在的位置）。
4、反向移动非坑指针，即R左移，直到R<axis停止。将该位置数据填入L的坑中，产生新的坑R。
5、继续3-4的操作，直到L>=R停止，将中轴值axis填入L坑中，即完成了此次排序。
//挖坑填坑法前后指针法
1、选取中轴值axis=4（尾部选取）。
2、初始化前(F)、后(B)指针位于头部。F用来指示<axis的位置，B用来指示>=axis的位置。
3、判断是否满足F<axis，同时B>=axis的条件，若满足，交换F、B的值。
4、F指针后移，若B指针的值<axis，也后移。然后执行第3步，直到F到达尾部。
5、交换B与尾部（中轴值）。
//前后指针法注：左右指针法，挖坑填坑法，实际都是利用了存储结构（数组、双向链表等）可双向遍历的特性（首尾双指针双向遍历），当数据结构仅支持单向遍历时（如：单向链表）上述方法即失效。而前后指针法则采用了双指针同向遍历的方式实现的，因此更具有普适性。
- 逐层分治
逐层分治可采用递归函数、迭代+栈存储的方式实现。
方法优化
以上方法中存在两个问题：
1、中轴值的选取：如何选取中轴值使得大、小集合的划分更均匀？
解决方法：三值取中，选数列的头、中、尾三个位置的值进行排序，然后取中间值作为中轴值。
2、当序列较短时上述递归方法会导致不必要的堆栈开销，能否优化？
解决方法：当子集合较短时（如：<5个元素）可考虑使用插入法排序，等空间开销、时间开销都适中的方法。