quick_sort/Netherland Flag

¶开始 Starting

Quick Sort Memory Sheet

¶题目 Question

https://leetcode-cn.com/problems/sort-colors/ 荷兰国旗

¶想法 Thinking

¶算法 Algorithm

¶One Pointer：Divide into two

初始化小于等于区（下称 区） 等于 -1 ， 遍历数组：

1. 如果当前数字<= 区分值：当前数和区下一个做交换， 区右扩一个位置，当前数跳下一个
2. 如果当前数字> 区分值，区不扩，当前数跳下一个

¶Netherland Flag

初始化小于区等于-1和大于区len(array)，遍历数组：

1. 当前数< 区分值：

   当前数和小区下一个交换，小区右扩，当前数跳下一个

2. 当前数== 区分值

   当前数跳下一个

3. 当前数> 区分值

   当前数和大区前一个交换，大区左扩，当前数，当前数不动（因为当前数还没有被partition）

三个区域都是为闭区间：等于区可以表示为 [less+1, more-1]，如果 less+1 > more-1 即表明没有等于区

¶Quick Sort

¶运行时间 Run-time

¶反思 Introspection