快速選擇（遞歸實現版）

這里給出以 “leetcode215. 數組中的第K個最大元素”為例的代碼。

class Solution:def findKthLargest(self, nums, k):self.nums = numsn = len(nums)return self.quickSelect(0,n-1,n-k)def quickSelect(self,l,r,k): # 手擼快速選擇if(l == r): return self.nums[k]mid_num = self.nums[l]i = l-1j = r+1while(i < j):i += 1while(self.nums[i] < mid_num): i += 1j -= 1while(self.nums[j] > mid_num): j -= 1if(i < j): self.nums[i],self.nums[j] = self.nums[j],self.nums[i]if(k <= j): return self.quickSelect(l,j,k)return self.quickSelect(j+1,r,k)

代碼的實現參照了官解，非常優雅。

代碼的關鍵是，"while(i < j):"這一步里面的循環。可以證明，經過這個循環，最后出來的j,其位置一定在區間[l,r-1]上，同時[l,j]元素的值均等小于等于[j+1,r]。因此，每次遞歸，都會導致輸入的數組長度減少，遞歸可以退出。由于尋找的是下標為k的排序的元素，因此每次分割，一定可以確定有一邊是不必再排序的，因此進入下一遞歸的區間，就選擇[l,j]或[j+1,r]，直到某個遞歸中l=r，這時代表只有一個元素，沒必要排序，直接返回此時列表的下標k的元素即可得到。

注意代碼實現中的，選擇第一個元素作為基準值的設計很精妙，可以仔細品鑒。

快速選擇（迭代實現）

class Solution:def findKthLargest(self, nums, k):self.nums = numsn = len(nums)return self.quickSelectIter(0,n-1,n-k) def quickSelectIter(self,l,r,k): # 手擼快速選擇while(l != r):mid_num = self.nums[l]i = l-1j = r+1while(i < j):i += 1while(self.nums[i] < mid_num): i += 1j -= 1while(self.nums[j] > mid_num): j -= 1if(i < j): self.nums[i],self.nums[j] = self.nums[j],self.nums[i]if(k <= j):l,r = l,jelse:l,r = j+1,rreturn self.nums[k]

快速排序

上面的快速選擇，每次劃分成兩個區間，然后拋棄另一個區間，繼續劃分留下的區間。
對上面的代碼稍加改進，對每個劃分出的區間繼續劃分，即可得到完全排序的數組。

這里以"leetcode 912. 排序數組"給出代碼

class Solution:def sortArray(self, nums: List[int]) -> List[int]:self.nums = numsself.quickSort(0,len(nums)-1)return numsdef quickSort(self,l,r):if(l == r): returnmid_num = self.nums[l]i = l-1j = r+1while(i < j):i += 1while(self.nums[i] < mid_num): i += 1j -= 1while(self.nums[j] > mid_num): j -= 1if(i < j): self.nums[i],self.nums[j] = self.nums[j],self.nums[i]self.quickSort(l,j)self.quickSort(j+1,r)

隨機快速排序

上面的快速排序，取第一個元素為基準值，會導致在極端情況下，時間開銷大。比如數組已經是有序的情況。

這里做出改進，隨機選取數組中的一個元素作為基準值。但是，前面快速選擇的方法中實現的劃分是精心設計的，其要求基準值是第一個元素。
因此，在隨機選擇基準值并劃分的實現上，只需先隨機選取一個下標，并將下標值和第一個值互換，其它操作和之前一樣即可。

class Solution:def sortArray(self, nums: List[int]) -> List[int]:self.nums = numsself.quickSortRandom(0,len(nums)-1)return nums# 隨機快速排序def quickSortRandom(self,l,r):if(l == r): returnrandom_index = random.randint(l, r)self.nums[l],self.nums[random_index] = self.nums[random_index],self.nums[l]mid_num = self.nums[l]i = l-1j = r+1while(i < j):i += 1while(self.nums[i] < mid_num): i += 1j -= 1while(self.nums[j] > mid_num): j -= 1if(i < j): self.nums[i],self.nums[j] = self.nums[j],self.nums[i]self.quickSortRandom(l,j)self.quickSortRandom(j+1,r)