快速排序 ​

快速排序算法有两个核心点，分别为 哨兵划分 和 递归 。

哨兵划分：以数组某个元素（一般选取首元素）为 基准数 ，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。

下图展示了哨兵划分操作流程。经过一轮 哨兵划分 ，可将数组排序问题拆分为 两个较短数组的排序问题 （本文称之为左（右）子数组）。

<,,,,,,,,>

递归：对 左子数组 和 右子数组 分别递归执行 哨兵划分，直至子数组长度为 1 时终止递归，即可完成对整个数组的排序。

下图展示了数组 [2,4,1,0,3,5] 的快速排序流程。观察发现，快速排序和 二分法 的原理类似，都是以 $\log$ 时间复杂度实现搜索区间缩小。

代码 ​

def quick_sort(nums, l, r):
    # 子数组长度为 1 时终止递归
    if l >= r: return
    # 哨兵划分操作
    i = partition(nums, l, r)
    # 递归左（右）子数组执行哨兵划分
    quick_sort(nums, l, i - 1)
    quick_sort(nums, i + 1, r)
    
def partition(nums, l, r):
    # 以 nums[l] 作为基准数
    i, j = l, r
    while i < j:
        while i < j and nums[j] >= nums[l]: j -= 1
        while i < j and nums[i] <= nums[l]: i += 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[l], nums[i] = nums[i], nums[l]
    return i

# 调用
nums = [3, 4, 1, 5, 2]
quick_sort(nums, 0, len(nums) - 1)

void quickSort(int[] nums, int l, int r) {
    // 子数组长度为 1 时终止递归
    if (l >= r) return;
    // 哨兵划分操作
    int i = partition(nums, l, r);
    // 递归左（右）子数组执行哨兵划分
    quickSort(nums, l, i - 1);
    quickSort(nums, i + 1, r);
}

int partition(int[] nums, int l, int r) {
    // 以 nums[l] 作为基准数
    int i = l, j = r;
    while (i < j) {
        while (i < j && nums[j] >= nums[l]) j--;
        while (i < j && nums[i] <= nums[l]) i++;
        swap(nums, i, j);
    }
    swap(nums, i, l);
    return i;
}

void swap(int[] nums, int i, int j) {
    // 交换 nums[i] 和 nums[j]
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

// 调用
int[] nums = { 4, 1, 3, 2, 5 };
quickSort(nums, 0, nums.length - 1);

int partition(vector<int>& nums, int l, int r) {
    // 以 nums[l] 作为基准数
    int i = l, j = r;
    while (i < j) {
        while (i < j && nums[j] >= nums[l]) j--;
        while (i < j && nums[i] <= nums[l]) i++;
        swap(nums[i], nums[j]);
    }
    swap(nums[i], nums[l]);
    return i;
}

void quickSort(vector<int>& nums, int l, int r) {
    // 子数组长度为 1 时终止递归
    if (l >= r) return;
    // 哨兵划分操作
    int i = partition(nums, l, r);
    // 递归左（右）子数组执行哨兵划分
    quickSort(nums, l, i - 1);
    quickSort(nums, i + 1, r);
}

// 调用
vector<int> nums = { 4, 1, 3, 2, 5, 1 };
quickSort(nums, 0, nums.size() - 1);

算法特性 ​

• 时间复杂度：
  • 最佳 $\Omega(N \log N )$ ： 最佳情况下， 每轮哨兵划分操作将数组划分为等长度的两个子数组；哨兵划分操作为线性时间复杂度 $O(N)$ ；递归轮数共 $O(\log N)$ 。
  • 平均 $\Theta(N \log N)$ ： 对于随机输入数组，哨兵划分操作的递归轮数也为 $O(\log N)$ 。
  • 最差 $O(N^2)$ ： 对于某些特殊输入数组，每轮哨兵划分操作都将长度为 $N$ 的数组划分为长度为 $1$ 和 $N - 1$ 的两个子数组，此时递归轮数达到 $N$ 。

  通过 「随机选择基准数」优化，可尽可能避免出现最差情况，详情请见下文。

• 空间复杂度 $O(N)$ ： 快速排序的递归深度最好与平均皆为 $\log N$ ；输入数组完全倒序下，达到最差递归深度 $N$ 。

  通过「尾递归」优化，可将最差空间复杂度降低至 $O(\log N)$ ，详情请见下文。

• 虽然平均时间复杂度与「归并排序」和「堆排序」一致，但在实际使用中快速排序 效率更高 ，这是因为：
  • 最差情况稀疏性： 虽然快速排序的最差时间复杂度为 $O(N^2)$ ，差于归并排序和堆排序，但统计意义上看，这种情况出现的机率很低。大部分情况下，快速排序以 $O(N \log N)$ 复杂度运行。
  • 缓存使用效率高： 哨兵划分操作时，将整个子数组加载入缓存中，访问元素效率很高；堆排序需要跳跃式访问元素，因此不具有此特性。
  • 常数系数低： 在提及的三种算法中，快速排序的 比较、赋值、交换 三种操作的综合耗时最低（类似于插入排序快于冒泡排序的原理）。
• 原地： 不用借助辅助数组的额外空间，递归仅使用 $O(\log N)$ 大小的栈帧空间。
• 非稳定： 哨兵划分操作可能改变相等元素的相对顺序。
• 自适应： 对于极少输入数据，每轮哨兵划分操作都将长度为 $N$ 的数组划分为长度 $1$ 和 $N - 1$ 两个子数组，此时时间复杂度劣化至 $O(N^2)$ 。

算法优化 ​

快速排序的常见优化手段有「尾递归」和「随机基准数」两种。

尾递归： ​

由于普通快速排序每轮选取「子数组最左元素」作为「基准数」，因此在输入数组 完全倒序 时， partition() 的递归深度会达到 $N$ ，即 最差空间复杂度 为 $O(N)$ 。

每轮递归时，仅对 较短的子数组 执行哨兵划分 partition() ，就可将最差的递归深度控制在 $O(\log N)$ （每轮递归的子数组长度都 $\leq$ 当前数组长度 $/ 2$ ），即实现最差空间复杂度 $O(\log N)$ 。

代码仅需修改 quick_sort() 方法，其余方法不变，在此省略。

def quick_sort(nums, l, r):
    # 子数组长度为 1 时终止递归
    while l < r:
        # 哨兵划分操作
        i = partition(nums, l, r)
        # 仅递归至较短子数组，控制递归深度
        if i - l < r - i:
            quick_sort(nums, l, i - 1)
            l = i + 1
        else:
            quick_sort(nums, i + 1, r)
            r = i - 1

void quickSort(int[] nums, int l, int r) {
    // 子数组长度为 1 时终止递归
    while (l < r) {
        // 哨兵划分操作
        int i = partition(nums, l, r);
        // 仅递归至较短子数组，控制递归深度
        if (i - l < r - i) {
            quickSort(nums, l, i - 1);
            l = i + 1;
        } else {
            quickSort(nums, i + 1, r);
            r = i - 1;
        }
    }
}

void quickSort(vector<int>& nums, int l, int r) {
    // 子数组长度为 1 时终止递归
    while (l < r) {
        // 哨兵划分操作
        int i = partition(nums, l, r);
        // 仅递归至较短子数组，控制递归深度
        if (i - l < r - i) {
            quickSort(nums, l, i - 1);
            l = i + 1;
        } else {
            quickSort(nums, i + 1, r);
            r = i - 1;
        }
    }
}

随机基准数： ​

同样地，由于快速排序每轮选取「子数组最左元素」作为「基准数」，因此在输入数组 完全有序 或 完全倒序 时， partition() 每轮只划分一个元素，达到最差时间复杂度 $O(N^2)$ 。

因此，可使用 随机函数 ，每轮在子数组中随机选择一个元素作为基准数，这样就可以极大概率避免以上劣化情况。

值得注意的是，由于仍然可能出现最差情况，因此快速排序的最差时间复杂度仍为 $O(N^2)$ 。

代码仅需修改 partition() 方法，其余方法不变，在此省略。

def partition(nums, l, r):
    # 在闭区间 [l, r] 随机选取任意索引，并与 nums[l] 交换
    ra = random.randrange(l, r + 1)
    nums[l], nums[ra] = nums[ra], nums[l]
    # 以 nums[l] 作为基准数
    i, j = l, r
    while i < j:
        while i < j and nums[j] >= nums[l]: j -= 1
        while i < j and nums[i] <= nums[l]: i += 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[l], nums[i] = nums[i], nums[l]
    return i

int partition(int[] nums, int l, int r) {
    // 在闭区间 [l, r] 随机选取任意索引，并与 nums[l] 交换
    int ra = (int)(l + Math.random() * (r - l + 1));
    swap(nums, l, ra);
    // 以 nums[l] 作为基准数
    int i = l, j = r;
    while (i < j) {
        while (i < j && nums[j] >= nums[l]) j--;
        while (i < j && nums[i] <= nums[l]) i++;
        swap(nums, i, j);
    }
    swap(nums, i, l);
    return i;
}

int partition(vector<int>& nums, int l, int r) {
    // 在闭区间 [l, r] 随机选取任意索引，并与 nums[l] 交换
    int ra = l + rand() % (r - l + 1);
    swap(nums[l], nums[ra]);
    // 以 nums[l] 作为基准数
    int i = l, j = r;
    while (i < j) {
        while (i < j && nums[j] >= nums[l]) j--;
        while (i < j && nums[i] <= nums[l]) i++;
        swap(nums[i], nums[j]);
    }
    swap(nums[i], nums[l]);
    return i;
}