快速排序的框架

912. 排序數(shù)組

給你一個整數(shù)數(shù)組 nums，請你將該數(shù)組升序排列。

輸入：nums = [5,2,3,1]
輸出：[1,2,3,5]

partition函數(shù)

• 在arr[left, right]選擇中樞點arr[mid]，雙指針相向移動，進行交換排序
• 當left > right時停止，此時有兩種可能：
  • arr = [1, 2, 3, 4, 5], pivot = 3，left和right都指向3，那么移動后left指向4，right指向2。兩個指針隔一個數(shù)，且中間那個數(shù)就是pivot。
  • arr = [1, 3, 3', 5], pivot = 3，left和right分別指向3和3'，那么swap后arr = [1, 3', 3, 5]，left指向3， right指向3'。兩個指針相鄰。
• 所以，令index1 = right，index2 = left，返回

quickSort函數(shù)

• arr[left, index1]都是小于等于pivot，arr[index2, right]都是大于等于pivot。在這兩個區(qū)間分別quickSort。

注意

• 如果只返回一個index，可能會死循環(huán)...
• 兩個函數(shù)可以合并寫
• 也可以選擇arr[left]或arr[right]為pivot，就有另一種寫法，似乎是同向雙指針，沒仔細研究。

時間復雜度

畫出遞歸樹

           n                       1 * n
        /     \
    n/2         n/2               2 * n/2
  /     \      /    \
n/4   n/4     n/4  n/4            4 * n/4

1 * n + 2 * n/2 + ... + 2^i * n/2^i = n * i = nlog(n)

代碼

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        # 面試中可能不允許修改原數(shù)組，所以把nums拷貝成arr
        arr = [0] * len(nums)
        for i in range(len(nums)):
            arr[i] = nums[i]
        # 進行快速排序
        self.quickSort(arr, 0, len(nums) - 1)
        return arr

    # 歸并排序函數(shù)：將nums[left...right]排序
    def quickSort(self, arr: List[int], left: int, right: int):
        if left >= right:
            return 
        # 找到兩個中樞點
        index1, index2 = self.partition(arr, left, right)
        # 左邊排序
        self.quickSort(arr, left, index1)
        # 右邊排序
        self.quickSort(arr, index2, right)
    
    def partition(self, arr: List[int], left: int, right: int):
        pivot = arr[left + (right- left) // 2]
        # 當left == right時也要做處理
        while left <= right:
            # 找到左邊第一個大于等于pivot的數(shù)
            while left <= right and arr[left] < pivot:
                left += 1
            # 找到右邊第一個小于等于pivot的數(shù)
            while left <= right and arr[right] > pivot:
                right -= 1
            # 交換
            if left <= right:
                arr[left], arr[right] = arr[right], arr[left]
                left += 1
                right -= 1
        # [..., right]都是小于等于pivot的
        # [left, ...]都是大于等于pivot的
        # 有兩種可能：right + 1 == left or right + 2 == left
        return right, left

快速選擇的框架

215. 數(shù)組中的第K個最大元素

在未排序的數(shù)組中找到第 k 個最大的元素。請注意，你需要找的是數(shù)組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。

輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5

partition函數(shù)

和快排一樣。

quickSelect函數(shù)

• 快排是：1. 找中樞點 2. 快排左和右
• 快選是：1. 找中樞點 2. 快選左或右

時間復雜度

• 平均: n + n/2 + n/4 +... = O(n)
• 最差: n + n-1 + n-2 + ... + 1 = O(n^2)

代碼

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # 面試中可能不允許修改原數(shù)組，所以把nums拷貝成arr
        arr = [0] * len(nums)
        for i in range(len(nums)):
            arr[i] = nums[i]
        # 進行快速排序
        self.quickSelect(arr, 0, len(nums) - 1, len(nums) - k)
        return arr[len(nums) - k]

    # 歸并排序函數(shù)：將nums[left...right]排序
    def quickSelect(self, arr: List[int], left: int, right: int, k: int):
        # 也可以寫 if left == right
        if left >= right:
            return 
        # 找到兩個中樞點
        index1, index2 = self.partition(arr, left, right)
        # 左邊排序
        if k <= index1:
            self.quickSelect(arr, left, index1, k)
        # 右邊排序
        elif k >= index2:
            self.quickSelect(arr, index2, right, k)
        else:
            return
    
    def partition(self, arr: List[int], left: int, right: int):
        pivot = arr[left + (right- left) // 2]
        # 當left == right時也要做處理
        while left <= right:
            # 找到左邊第一個大于等于pivot的數(shù)
            while left <= right and arr[left] < pivot:
                left += 1
            # 找到右邊第一個小于等于pivot的數(shù)
            while left <= right and arr[right] > pivot:
                right -= 1
            # 交換
            if left <= right:
                arr[left], arr[right] = arr[right], arr[left]
                left += 1
                right -= 1
        # [..., right]都是小于等于pivot的
        # [left, ...]都是大于等于pivot的
        # 有兩種可能：right + 1 == left or right + 2 == left
        return right, left