选择一个基准，一般以第一个为基准，找到它的位置（把比他大的放到右边，比他小的放到左边），这时数据就被分为了两半，再对两边执行重复的操作（递归），直到只剩一个元素。
时间复杂度：
最佳Ω(NlogN) ： 最佳情况下， 每轮划分操作将数组划分为等长度的两个子数组；哨兵划分操作为线性时间复杂度 O(N) ；递归轮数共 O(logN) 。
平均 Θ(NlogN) ： 对于随机输入数组，哨兵划分操作的递归轮数也为O(logN) 。
最差 O(N^2)：对于某些特殊输入数组，每轮哨兵划分操作都将长度为 N 的数组划分为长度为 1和 N - 1的两个子数组，此时递归轮数达到 N 。
空间复杂度 O(N) ：
快速排序的递归深度最好与平均皆为 NlogN ；
输入数组完全倒序下，达到最差递归深度 N 。
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;
}
@Test
public void main() {
// 调用
int[] nums = {4, 1, 3, 2, 5};
quickSort(nums, 0, nums.length - 1);
for (int num : nums) {
System.out.println(num);
}
}
优化1：随机基准数
由于快速排序每轮选取「子数组最左元素」作为「基准数」，因此在输入数组 完全有序 或 完全倒序 时， partition() 每轮只划分一个元素，达到最差时间复杂度 O(N^2)
因此，可使用 随机函数 ，每轮在子数组中随机选择一个元素作为基准数，这样就可以极大概率避免以上劣化情况。
值得注意的是，由于仍然可能出现最差情况，因此快速排序的最差时间复杂度仍为 O(N^2)。
仅需修改partition()方法:
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;
}
优化2：
Tail Call 由于普通快速排序每轮选取「子数组最左元素」作为「基准数」，因此在输入数组 完全倒序 时， partition() 的递归深度会达到 N ，即 最差空间复杂度 为 O(N)。
每轮递归时，仅对 较短的子数组 执行哨兵划分 partition() ，就可将最差的递归深度控制在 O(logN) （每轮递归的子数组长度都≤ 当前数组长度 1/2 ），即实现最差空间复杂度 O(logN) 。
仅需修改quickSort（）函数即可：
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;
}
}
}
推荐阅读
发表评论