06.Array-Quick-Sort.md

1. 快速排序算法思想

快速排序（Quick Sort）基本思想：

通过一趟排序将无序序列分为独立的两个序列，第一个序列的值均比第二个序列的值小。然后递归地排列两个子序列，以达到整个序列有序。

2. 快速排序算法步骤

1. 从序列中找到一个基准数 pivot（这里以当前序列第 1 个元素作为基准数，即 pivot = arr[low]）。
2. 使用双指针，将序列中比基准数大的元素移动到基准数右侧，比他小的元素移动到基准数左侧：
   1. 使用指针 i，指向当前需要处理的元素位置，需要保证位置 i 之前的元素都小于基准数。初始时，i 指向当前序列的第 2 个元素位置。
   2. 使用指针 j 遍历当前序列，如果遇到 arr[j] 小于基准数 pivot，则将 arr[j] 与当前需要处理的元素 arr[i] 交换，并将 i 向右移动 1 位，保证位置 i 之前的元素都小于基准数。
   3. 最后遍历完，此时位置 i 之前的元素都小于基准数，第 i - 1 位置上的元素是最后一个小于基准数 pivot 的元素，此位置为基准数最终的正确位置。将基准数与该位置上的元素进行交换。此时，基准数左侧都是小于基准数的元素，右侧都是大于等于基准数的元素。
   4. 然后将序列拆分为左右两个子序列。
3. 对左右两个子序列分别重复第 2 步，直到各个子序列只有 1 个元素，则排序结束。

3. 快速排序动画演示

1. 初始序列为：[6, 2, 3, 5, 1, 4]。
2. 第 1 趟排序：
   1. 选择当前序列第 1 个元素 6 作为基准数。
   2. 从左到右遍历序列：
      1. 遇到 2 < 6，此时 i 与 j 相同，指针 i 向右移动 1 位。
      2. 遇到 3 < 6，此时 i 与 j 相同，指针 i 向右移动 1 位。
      3. 遇到 5 < 6，此时 i 与 j 相同，指针 i 向右移动 1 位。
      4. 遇到 1 < 6，此时 i 与 j 相同，指针 i 向右移动 1 位。
      5. 遇到 4 < 6，此时 i 与 j 相同，指针 i 向右移动 1 位，i 到达数组末尾。
   3. 最终将基准值 6 与最后 1 位交换位置，则序列变为 [4, 2, 3, 5, 1, 6]。
   4. 将序列分为左子序列 [4, 2, 3, 5, 1] 和右子序列 []。
3. 第 2 趟排序：
   1. 左子序列 [4, 2, 3, 5, 1] 中选择当前序列第 1 个元素 4 作为基准数。
   2. 从到右遍历左子序列：
      1. 遇到 2 < 4，此时 i 与 j 相同，指针 i 向右移动 1 位。
      2. 遇到 3 < 4，此时 i 与 j 相同，指针 i 向右移动 1 位。
      3. 遇到 5 > 4，不进行操作；
      4. 遇到 1 < 4，此时 i 指向 5，j 指向 1。则将 5 与 1 进行交换，指针 i 向右移动 1 位，i 到达数组末尾。
   3. 最终将基准值 4 与 1 交换位置，则序列变为 [1, 2, 3, 4, 5, 6]。
4. 依次类推，重复选定基准数，并将序列中比基准数大的元素移动到基准数右侧，比他小的元素移动到基准数左侧。直到各个子序列只有 1 个元素，则排序结束。此时序列变为 [1, 2, 3, 4, 5, 6]。

4. 快速排序算法分析

快速排序算法的时间复杂度主要跟基准数的选择有关。本文中是将当前序列中第 1 个元素作为基准值。

在这种选择下，如果参加排序的元素初始时已经有序的情况下，快速排序方法花费的时间最长。也就是会得到最坏时间复杂度。

在这种情况下，第 1 趟排序经过 n - 1 次比较以后，将第 1 个元素仍然确定在原来的位置上，并得到 1 个长度为 n - 1 的子序列。第 2 趟排序进过 n - 2 次比较以后，将第 2 个元素确定在它原来的位置上，又得到 1 个长度为 n - 2 的子序列。

最终总的比较次数为 $(n − 1) + (n − 2) + … + 1 = \frac{n(n − 1)}{2}$。因此这种情况下的时间复杂度为 $O(n^2)$，也是最坏时间复杂度。

我们可以改进一下基准数的选择。如果每次我们选中的基准数恰好能将当前序列平分为两份，也就是刚好取到当前序列的中位数。

在这种选择下，每一次都将序列从 $n$ 个元素变为 $\frac{n}{2}$ 个元素。此时的时间复杂度公式为 $T(n) = 2 \times T(\frac{n}{2}) + \Theta(n)$。根据主定理可以得出 $T(n) = O(n \times \log_2n)$，也是最佳时间复杂度。

而在平均情况下，我们可以从当前序列中随机选择一个元素作为基准数。这样，每一次选择的基准数可以看做是等概率随机的。其期望时间复杂度为 $O(n \times \log_2n)$，也就是平均时间复杂度。

下面来总结一下：

• 最佳时间复杂度：$O(n \times \log_2n)$。每一次选择的基准数都是当前序列的中位数，此时算法时间复杂度满足的递推式为 $T(n) = 2 \times T(\frac{n}{2}) + \Theta(n)$，由主定理可得 $T(n) = O(n \times \log_2n)$。
• 最坏时间复杂度：$O(n^2)$。每一次选择的基准数都是序列的最终位置上的值，此时算法时间复杂度满足的递推式为 $T(n) = T(n - 1) + \Theta(n)$，累加可得 $T(n) = O(n^2)$。
• 平均时间复杂度：$O(n \times \log_2n)$。在平均情况下，每一次选择的基准数可以看做是等概率随机的。其期望时间复杂度为 $O(n \times \log_2n)$。
• 空间复杂度：$O(n)$。无论快速排序算法递归与否，排序过程中都需要用到堆栈或其他结构的辅助空间来存放当前待排序序列的首、尾位置。最坏的情况下，空间复杂度为 $O(n)$。如果对算法进行一些改写，在一趟排序之后比较被划分所得到的两个子序列的长度，并且首先对长度较短的子序列进行快速排序，这时候需要的空间复杂度可以达到 $O(log_2 n)$。
• 排序稳定性：快速排序是一种 不稳定排序算法。

5. 快速排序代码实现

import random

class Solution:
    # 从 arr[low: high + 1] 中随机挑选一个基准数，并进行移动排序
    def randomPartition(self, arr: [int], low: int, high: int):
        # 随机挑选一个基准数
        i = random.randint(low, high)
        # 将基准数与最低位互换
        arr[i], arr[low] = arr[low], arr[i]
        # 以最低位为基准数，然后将序列中比基准数大的元素移动到基准数右侧，比他小的元素移动到基准数左侧。最后将基准数放到正确位置上
        return self.partition(arr, low, high)
    
    # 以最低位为基准数，然后将序列中比基准数大的元素移动到基准数右侧，比他小的元素移动到基准数左侧。最后将基准数放到正确位置上
    def partition(self, arr: [int], low: int, high: int):
        pivot = arr[low]            # 以第 1 为为基准数
        i = low + 1                 # 从基准数后 1 位开始遍历，保证位置 i 之前的元素都小于基准数
        
        for j in range(i, high + 1):
            # 发现一个小于基准数的元素
            if arr[j] < pivot:
                # 将小于基准数的元素 arr[j] 与当前 arr[i] 进行换位，保证位置 i 之前的元素都小于基准数
                arr[i], arr[j] = arr[j], arr[i]
                # i 之前的元素都小于基准数，所以 i 向右移动一位
                i += 1
        # 将基准节点放到正确位置上
        arr[i - 1], arr[low] = arr[low], arr[i - 1]
        # 返回基准数位置
        return i - 1

    def quickSort(self, arr, low, high):
        if low < high:
            # 按照基准数的位置，将序列划分为左右两个子序列
            pi = self.randomPartition(arr, low, high)
            # 对左右两个子序列分别进行递归快速排序
            self.quickSort(arr, low, pi - 1)
            self.quickSort(arr, pi + 1, high)

        return arr

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.quickSort(nums, 0, len(nums) - 1)

参考资料

• 【文章】快速排序 - OI Wiki