快速排序

今天我们来学习一种非常经典和高效的排序算法——快速排序。

可能大家都已经会快速排序了。

如果你平时在写快速排序的时候出现过这些问题,或者在面试中被问到过,还是希望你能耐心看完文章,相信你一定会有所收获。

在写快速排序的时候经常出现数组下标越界?

快速排序在什么情况下时间复杂度会退化成 **{O(N^2)}?**

排序数组有大量重复元素应如何优化?

快速排序思想介绍

快速排序和我们之前所学习的归并排序一样,也是基于 分治 的思想实现的。

快速排序的核心思想是通过选取一个基准值,通过交换元素的位置,将比基准值小的元素放在基准值的左边,比基准值大的元素放在基准值的右边。

这样基准值就被放到了整个数组有序时它所应该在的位置

然后只需要递归地对剩下的左右两部分子数组进行排序,最终得到一个有序数组。

如何切分数组

快速排序的思路还是比较好懂的,接下来我们分析的重点在于怎么切分数组。

首先我们可以先选择待排序区间 [l, r] 的第一个元素 nums[l] 作为切分元素 v,然后对数组进行遍历。

在遍历的过程中维护区间 [l + 1, lt),这个区间里的元素是 **小于切分元素 ****v** 的。

初始状态如下图:

开始比较,发现 nums[i] < v, 所以交换 nums[i]nums[lt],并移动指针 ilt (指针 lt 也要移动是因为我们维护的小于切分元素的区间 扩张 了),得到下图:

继续比较,发现 nums[i] > v, 移动指针 i (注意此时指针 ****lt** 没有移动**),得到下图:

继续比较,发现 nums[i] < v, 所以交换 nums[i]nums[lt],并移动指针 ilt ,得到下图:

继续比较,发现 nums[i] < v, 所以交换 nums[i]nums[lt],并移动指针 ilt ,得到下图:

继续比较,发现 nums[i] > v, 移动指针 i,得到下图:

继续比较,发现 nums[i] > v, 移动指针 i,得到下图:

继续比较,发现 nums[i] < v, 所以交换 nums[i]nums[lt],并移动指针 ilt ,得到下图:

至此,我们的遍历过程结束,不过还要将 nums[l] 放到正确的位置上,只需要将 nums[l]nums[lt - 1] 进行交换即可,得到下图:

快速排序代码实现

public class Solution {

    Random random = new Random();

    public int[] MySort (int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    public void quickSort (int[] nums, int l, int r) {
        // 当数组只有一个元素,递归结束
        if (l >= r) {
            return;
        }
        int k = random.nextInt(r - l + 1) + l;
        swap(nums, l, k);
        int v = nums[l];
        int i = l + 1;
        int lt = l + 1;
        while (i <= r) {
            if (nums[i] < v) {
                swap(nums, i++, lt++);
            } else {
                i++;
            }
        }
        swap(nums, l, lt - 1);
        quickSort(nums, l, lt - 2);
        quickSort(nums, lt, r);
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

在上面的代码中,我们发现,在选择切分元素 v 的时候,我们进行了 随机选取

这是由于当数组有序时,会导致我们的切分效果很差,甚至 导致快速排序的时间复杂度退化\ce{O(N^2)},所以这一点要格外注意。

存在大量重复元素的优化

在上面的例子中,我们在切分数组时将元素分成了小于切分元素的和大于切分元素的。

没有刻意去讨论如何处理等于切分元素的,因为对于这种情况,你将其放在哪里都合适。无非就是将 if (nums[i] < v) 这个 < 的判断变成 <=

虽然上面这种切分效率也不错,但针对存在大量重复元素的,有更好的切分方式。

其实就是在切分的过程中,我们维护三个区间:

  • [l + 1, lt),这个区间里的元素是 **小于切分元素 ****v** 的。
  • [lt, i),这个区间里的元素是 **等于切分元素 ****v** 的。
  • (gt, r],这个区间里的元素是 **大于切分元素 ****v** 的。
    初始状态如下图:

开始比较,发现 nums[i] < v, 所以交换 nums[i]nums[lt],并移动指针 ilt (指针 lt 也要移动是因为我们维护的小于切分元素的区间 扩张 了),得到下图:

继续比较,发现 nums[i] > v, 所以交换 nums[i]nums[gt],并移动指针 gt

注意:指针 lt 也要移动是因为我们维护的大于切分元素的区间 扩张 了),

指针 i 没有移动是因为我们维护的大于切分元素的区间是 左开右闭,所以从右边交换过来的元素的情况我们是不清楚的,需要在下一轮继续比较

这应该是最容易犯错的地方,大家注意。

得到下图:

继续比较,发现 nums[i] > v, 所以交换 nums[i]nums[gt],并移动指针 gt ,得到下图:

继续比较,发现 nums[i] = v, 只需要移动指针 i ,得到下图:

继续比较,发现 nums[i] = v, 只需要移动指针 i ,得到下图:

继续比较,发现 nums[i] < v, 所以交换 nums[i]nums[lt],并移动指针 ilt,得到下图:

继续比较,发现 nums[i] > v, 所以交换 nums[i]nums[gt],并移动指针 gt ,得到下图:

最后发现 i > gt,退出比较,处理开头的切分元素的位置,得到下图:

此时,我们下一次递归的时候,需要处理的两个区间就是 [l, lt - 2][gt + 1, r]

显然,我们这个算法的效率能提升多大,取决于数组中重复元素的数量。

如果大家能耐心的掌握我们上面的图解,相信你也能很快写出没有 bug 效率又高的快速排序。

代码实现

public class Solution {

    Random random = new Random();

    public int[] MySort (int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    public void quickSort (int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        int k = random.nextInt(r - l + 1) + l;
        swap(nums, l, k);
        int v = nums[l];
        int i = l + 1;
        int lt = l + 1;
        int gt = r;
        while (i <= gt) {
            if (nums[i] < v) {
                swap(nums, i++, lt++);
            } else if (nums[i] > v) {
                swap(nums, i, gt--);
            } else {
                i++;
            }
        }
        swap(nums, l, lt - 1);
        quickSort(nums, l, lt - 2);
        quickSort(nums, gt + 1, r);
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

时间复杂度

快速排序的时间复杂度是 {O(NlogN)},其中 N 为待排序序列的长度。

因为归并排序是将序列分成两个长度相等或相差 1 的子序列,然后递归排序这两个子序列,最后再合并这两个子序列,整个过程需要 logN 次递归,每次递归需要 {O(N)} 的时间复杂度,所以总的时间复杂度是 {O(NlogN)}

另外,快速排序的时间复杂度也是 O(nlogn),与归并排序相同,但是在实际应用中,快速排序的性能通常优于归并排序。因为快速排序在每一次划分子序列的过程中,可以同时处理左右两个子序列,而归并排序只能一个一个处理子序列。这使得快速排序的平均时间复杂度比归并排序更小。

空间复杂度

与归并排序相比,快速排序 不需要额外的辅助数组 来存储排好序的子数组,只需要通过交换元素的位置实现排序。

而在归并排序中,需要额外的内存空间来存储子数组的结果,这就导致了归并排序的空间复杂度比快速排序高。

稳定性

快速排序不是一种稳定的排序算法,毕竟在切分元素的时候没办法保证相等元素的相对位置。

写在最后

总的来说,快速排序应该是应用最为广泛的排序算法了,当然前提是我们在解决某个实际问题的时候不需要考虑稳定性。

相信看完这篇文章的你,能够很轻松的回答出我们在文章开头提出的问题,在之后的面试中也能无往而不利!

发表回复

后才能评论