給定一個(gè)包含紅色、白色和藍(lán)色，一共n 個(gè)元素的數(shù)組，原地對(duì)它們進(jìn)行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍(lán)色順序排列。
此題中，我們使用整數(shù) 0、?1 和 2 分別表示紅色、白色和藍(lán)色。
注意:
不能使用代碼庫(kù)中的排序函數(shù)來解決這道題。
示例:
輸入:[2,0,2,1,1,0]輸出:[0,0,1,1,2,2]
打眼一看就是個(gè)排序的題，因?yàn)榍瓣囎幼鰝€(gè)冒泡，這次寫個(gè)快排。很久沒寫了，雖然快排的邏輯自己清楚，但是怎么用代碼實(shí)現(xiàn)出來還是廢了很大的功夫。
快速排序的原理是二分法，找一個(gè)基準(zhǔn)數(shù)，先從右到左找比它小的，再?gòu)淖蟮接艺冶人蟮?，然后這兩個(gè)數(shù)交換位置，一直找到兩邊相遇。然后吧基準(zhǔn)數(shù)置換到相遇位置。然后，從相遇的位置把列表分成兩個(gè)列表，遞歸上面的操作，直到結(jié)束。
代碼如下：
class Solution:
? ? def sortColors(self, nums: List[int]) -> None:
? ? ? ? """
? ? ? ? Do not return anything, modify nums in-place instead.
? ? ? ? """
? ? ? ? start = 0
? ? ? ? end = len(nums)-1
? ? ? ? self.QuickSort(nums, start, end)
? ? def QuickSort(self,myList, start, end):
? ? ? ? # 判斷l(xiāng)ow是否小于high,如果為false,直接返回
? ? ? ? if start < end:
? ? ? ? ? ? i, j = start, end
? ? ? ? ? ? # 設(shè)置基準(zhǔn)數(shù)
? ? ? ? ? ? base = myList[i]
? ? ? ? ? ? while i < j:
? ? ? ? ? ? ? ? # 如果列表后邊的數(shù),比基準(zhǔn)數(shù)大或相等,則前移一位直到有比基準(zhǔn)數(shù)小的數(shù)出現(xiàn)
? ? ? ? ? ? ? ? while (i < j) and (myList[j] >= base):
? ? ? ? ? ? ? ? ? ? j = j - 1
? ? ? ? ? ? ? ? # 如找到,則把第j個(gè)元素賦值給第個(gè)元素i,此時(shí)表中i,j個(gè)元素相等
? ? ? ? ? ? ? ? myList[i] = myList[j]
? ? ? ? ? ? ? ? # 同樣的方式比較前半?yún)^(qū)
? ? ? ? ? ? ? ? while (i < j) and (myList[i] <= base):
? ? ? ? ? ? ? ? ? ? i = i + 1
? ? ? ? ? ? ? ? myList[j] = myList[i]
? ? ? ? ? ? # 做完第一輪比較之后,列表被分成了兩個(gè)半?yún)^(qū),并且i=j,需要將這個(gè)數(shù)設(shè)置回base
? ? ? ? ? ? myList[i] = base
? ? ? ? ? ? # 遞歸前后半?yún)^(qū)
? ? ? ? ? ? self.QuickSort(myList, start, i - 1)
? ? ? ? ? ? self.QuickSort(myList, j + 1, end)
