常见排序算法总结 (四) - 快速排序与随机选择

快速排序

算法思想

每一轮在数组相应的范围上随机找一个元素进行划分，将不大于它的所有元素都放到左边，将大于它的元素都放到右边。在左右两个子数组上不断地递归，直到整个数组上有序。
注意：实现时选择的时参考荷兰国旗问题优化后的快排算法，它会在一次划分中维护一个包含所有等于划分标准元素的区间，保证小于该数的都在区间左侧，大于该数的都在区间右侧。这样的做法，在一定程度上能够减少划分次数。

稳定性分析

快速排序是不稳定的，它涉及到拆分区间，无法保证相等的数一定在同一个区间上被处理完成，也就无法保证它们的相对次序不发生变化。

具体实现

// 交换数组中的两个元素
private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}// 全局变量 first 表示等于当前元素的第一个下标位置，last 表示最后一个
public static int first, last;private void quickSort(int[] arr, int left, int right) {// 无法构成区间，直接返回if (left >= right) {return;}// 在合法范围内随机一个元素作为划分标准int pivot = arr[left + (int) (Math.random() * (right - left + 1))];// 划分并递归处理左右子数组partition(arr, left, right, pivot);quickSort(arr, left, first - 1);quickSort(arr, last + 1, right);
}public void partition(int[] arr, int left, int right, int pivot) {first = left;last = right;int cur = left;while (cur <= last) {if (arr[cur] == pivot) {cur++; // 当前元素等于划分标准，不作处理并后移指针} else if (arr[cur] < pivot) {swap(arr, first++, cur++); // 小于划分标准，交换且分别后移两个指针} else {swap(arr, cur, last--); // 大于划分标准，交换并前移记录最后一个当前元素的指针}}
}

随机选择

算法思想

随机选择是基于快排的划分操作，能够快速地确定一个数在数组中排序后的理论位置。这部分内容其实和排序关系不大，但是与快排有很大的关联，可以放在一起整理。

实践案例：Leetcode 215. 数组中的第K个最大元素

class Solution {public int findKthLargest(int[] nums, int k) {return randomizedSelect(nums, nums.length - k);}// 全局变量 first 表示等于当前元素的第一个下标位置，last 表示最后一个public static int first, last;public int randomizedSelect(int[] arr, int cur) {int res = 0;for (int left = 0, right = arr.length - 1; left <= right;) {partition(arr, left, right, arr[left + (int) (Math.random() * (right - left + 1))]);if (cur < first) {right = first - 1;  // 当前下标小于维护的第一个下标，到左边区间中找} else if (cur > last) {left = last + 1; // 当前下标大于维护的最后一个下标，到右边区间中找} else {res = arr[cur]; // 当前下标在维护的范围内，记录结果break;}}return res;}// 交换数组中的两个元素private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public void partition(int[] arr, int left, int right, int pivot) {first = left;last = right;int cur = left;while (cur <= last) {if (arr[cur] == pivot) {cur++; // 当前元素等于划分标准，不作处理并后移指针} else if (arr[cur] < pivot) {swap(arr, first++, cur++); // 小于划分标准，交换且分别后移两个指针} else {swap(arr, cur, last--); // 大于划分标准，交换并前移记录最后一个当前元素的指针}}}
}

梳理总结

快速排序的理论复杂度是 $O(NlogN)$，它通过划分来不断减小问题规模从而快速解决问题。但是实践中存在能使快排退化到 $O(N^2)$ 的阴间待排序列，因此需要通过随机划分标准这个手段来让时间复杂度尽可能地稳定在 $O(NlogN)$。
随机选择算法，本质上是根据不同的标准，维护相应的数值区间。它能够在理论实践复杂度 $O(N)$ 且不需要额外空间的情况下找出数组中第 $K$ 大的数。

后记

使用 Leetcode 912. 排序数组 进行测试，随机快速排序能够比较高效地完成任务。
实际运行下来和归并排序之间都有一些差距，猜测原因是随机操作的耗时很大，并且 Leetcode 平台上专门设置了卡快排的用例。