三路快排

使用快速排序的思想給帶有大量的重復鍵值的陣列進行排序，一種經典的實作方式就是三路快排（Quick Sort 3 Ways），

主要思想

將整個陣列分成三部分，即小于 v、等于 v 和大于 v，分割后在遞回的程序中，只需要遞回地對小于 v 和大于 v 的部分進行快速排序，不關心等于 v 的部分，如下圖示，

1、將陣列分為三部分，索引 lt 指向小于 v 的最后一個元素的位置，所以 nums[l+1...lt] < v，即區間 [l+1, lt] 中的元素均小于 v，同理索引 gt 指向大于 v 的第一個元素的位置，所以 nums[gt...r] > v，lt 和 gt 分別是 less than 和 greater than 的縮寫，

2、當前需要處理的元素為 i 位置的元素 k，保證 nums[lt+1...i-1] == v，如果 k == v，將 k 納入等于 v 的部分，i 右移繼續遍歷，

3、如果 k < v，只需要將該元素與等于 v 的第一個元素交換位置，此時元素 k 處于小于 v 的最后一個元素，相應地 lt 向右移動一位，i 繼續右移，查看下一個元素，

4、如果此時 k > v，只需要將該元素與 gt - 1 對應的元素交換位置，此時元素 k 處于陣列大于 v 的第一個元素，相應地 gt 向左移動一位，指向大于 v 的第一個位置，

5、排序完成之后，陣列如下圖示意，lt 和 gt 分別指向小于 v 的最后一個位置和大于 v 的第一個位置，最后交換 l 位置的元素跟 lt 位置的元素，之后只需要對小于 v 和大于 v 的部分進行遞回快速排序，等于 v 的部分已經放在陣列中合適的位置，

優點：不需要對大量等于 v 的元素進行重復操作，可以少考慮很多元素，特別是對于等于 v 的元素特別多的話，這一步優化變得非常明顯，

75. 顏色分類

給定一個包含紅色、白色和藍色，一共 n 個元素的陣列，原地對它們進行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍色順序排列，

此題中，我們使用整數 0、 1 和 2 分別表示紅色、白色和藍色，

示例 1：

輸入：nums = [2,0,2,1,1,0]

輸出：[0,0,1,1,2,2]

示例 2：

輸入：nums = [2,0,1]

輸出：[0,1,2]

解題思路

由于排序后的陣列主要依次分成三部分，即等于 0 的部分、等于 1 的部分和等于 2 的部分，這不是很像上面講的三路快速排序嗎？
每次選取一個標定點，由于陣列中有很多個與標定點相等的元素，所以將陣列分成三部分，即小于 v、等于 v 和大于 v，然后遞回地對小于 v 和大于 v 的地方進行三路快排，

由于當前陣列只有三個元素，所以只需要對整個陣列執行一次三路快排即可，如下圖示，

保證在遍歷整個陣列的程序中，0 處在整個陣列的開始位置、1 處在緊接著 0 后面的位置，2 處在整個陣列的末尾位置，

1、設定索引 zero 和 two，使得陣列 nums[0...zero] == 0 和 nums[two...n-1] == 2，設定遍歷索引 i 用于遍歷陣列元素，保證了 nums[zero+1...i-1] == 1，

2、當遍歷到元素 m 時，如果 m == 1，此時只需將 m 納入到屬于 1 的部分，同時 i 右移，

3、如果 m == 2，只要取出索引 two 指向的元素的前一個元素 k（當前不等于 2 的第一個元素），與 m 進行交換位置，并將索引 two 左移一位，相當于將此時的 m 納入到屬于 2 的部分，3、如果 m == 2，只要取出索引 two 指向的元素的前一個元素 k（當前不等于 2 的第一個元素），與 m 進行交換位置，并將索引 two 左移一位，相當于將此時的 m 納入到屬于 2 的部分，

4、如果 m == 0，只需要找到索引 zero + 1 對應的元素（當前值為 1的第一個元素），將其與當前的 m 交換位置，并將 zero 右移，相當于將此時的 m 納入到屬于 0 的部分，將索引 i 右移查看下一元素的值，

Show me the Code

 1 // c++
 2 void sortColors(vector<int>& nums) {
 3   int zero = -1; // 保證下標0到zero對應的元素都為0
 4   int two = nums.size(); // 保證下標two到numsSize-1對應的元素都為 2
 5   for (int i = 0; i < two;) {
 6     // 直接將遍歷到的元素1納入到屬于1的部分，i右移繼續遍歷
 7     if (nums[i] == 1) {
 8       i++;
 9     }
10     // 交換下標為two前一下標對應的元素與遍歷到的元素
11     // 并將遍歷到的元素2納入到屬于2的部分，two左移
12     else if (nums[i] == 2) {
13  
14         swap(nums[i], nums[--two]);
15     }
16     // 交換下標為zero后一下標對應的元素與遍歷到的元素
17     // 并將遍歷到的元素0納入到屬于0的部分，zero和i右移
18     else {
19       swap(nums[++zero], nums[i++]);
20     }
21   }
22 }

View Code

 1 // go
 2 func sortColors(nums []int)  {
 3     zero, two := -1, len(nums)
 4     for i := 0; i < two; {
 5         if nums[i] == 1 {
 6             i++
 7         } else if nums[i] == 2 {
 8             two -= 1
 9             nums[i], nums[two] = nums[two], nums[i]
10         } else {
11                 zero += 1
12                 nums[i], nums[zero] = nums[zero], nums[i]
13                 i++
14         }
15     }
16 }