REST

归并排序

1. 归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，
2. 该算法采用经典的分治（divide-and-conquer）策略
   1. 分治法将问题分(divide)成一些小的问题然后递归求解，
   2. 而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之。
3. 图解排序算法(四)之归并排序
4. 

快速排序

1. 荷兰国旗1.0
   1. 给定一个数组arr，和一个数num。把<=num的数放在数组的左边, >num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(1)。
   2. 思路：单指针记录<=num的范围 (start from -1)。
      1. 若arr[i] <= num，则arr[i]和<=区域的下一个数字作交换，<=区右扩，i++。
      2. 若arr[i]>num，则直接i++。
2. 荷兰国旗2.0
   1. 给定一个数组arr，和一个数num。把<num的数放在数组的左边, =num的数放在数组中间，>num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(1)。
   2. 思路：双指针，一个记录<num的范围 (start from -1)，另一个记录>num的范围 (start from arr.length)。
      1. 若arr[i]<num，则arr[i]和<区域的下一个数字作交换，<区右扩，i++。
      2. 若arr[i]=num，直接i++ (即扩充=区)。
      3. 若arr[i]>num，arr[i]和>区域的前一个数字作交换，>区左扩，i不变 (因为换上来的数字还没有被检查过)。
3. 和快排有什么关系
   1. (已学习)快排1.0:
      1. 将arr最后一个数视为num，对arr进行荷兰国旗1.0操作，即分区。再对于分区后的两个子数组进行重复操作（递归），直至子数组的长度不超过 1 时，不需要继续分区。
   2. (已学习)快排2.0:
      1. 对arr进行荷兰国旗2.0操作。快排2.0会稍快于快排1.0，因为中间==num的部分已经确定了位置不用再动了。
   3. (未学习)快排3.0 (随机快速排序)
      1. 快排3.0中每次随机选一个数作划分值，好情况、坏情况是等概率的，时间复杂度为O(NlogN) (用数学期望等知识证明)

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以邮件至 963614756@qq.com。