快速排序为什么这么快?

alt
alt

快速排序

首先选一个基准 pivot,然后过一遍数组,

  • 把小于 pivot 的都挪到 pivot 的左边,
  • 把大于 pivot 的都挪到 pivot 的右边。

这样一来,这个 pivot 的位置就确定了,也就是排好了 1 个元素。

然后对 pivot 左边 👈 的数排序,
对 pivot 右边 👉 的数排序,
就完成了。

那怎么排左边和右边?

答:同样的方法。

所以快排也是用的分治法的思想。

「分」

选择一个 pivot,就把问题分成了

  • pivot 左边
  • pivot 右边

这两个问题。

「治」

就是最开始描述的方法,直到每个区间内没有元素或者只剩一个元素就可以返回了。

「合」

放在一起自然就是。

但是如何选择这个 pivot?

取中间的?

取第一个?

取最后一个?

举个例子:{5, 2, 1, 0, 3}.

比如选最后一个,就是 3.

然后我们就需要把除了 3 之外的数分成「比 3 大」和「比 3 小」的两部分,这个过程叫做 partition(划分)

这里我们仍然使用「挡板法」的思想,不用真的弄两个数组来存这两部分,而是用两个挡板,把区间划分好了。

我们用「两个指针」(就是挡板)把数组分成「三个区间」,那么

  • 左边的区间用来放小于 pivot 的元素;
  • 右边的区间用来放大于 pivot 的元素;
  • 中间是未排序区间。
alt

那么初始化时,我们要保证「未排序区间」能够包含除了 3 之外的所有元素,所以

  • 未排序区间 = [i, j]

这样左边和右边的区间就成了:

  • [0, i):放比 3 小的数;
  • (j, array.length -2]:放比 3 大的数

注意 ⚠️ i, j 是不包含在左右区间里的呢。

那我们的目的是 check 未排序区间里的每一个数,然后把它归到正确的区间里,以此来缩小未排序区间,直到没有未排序的元素。

从左到右来 check:

Step1.

5 > 3, 所以 5 要放在右区间里,所以 5 和 j 指向的 0 交换一下:

alt

这样 5 就排好了,指针 j --,这样我们的未排序区间就少了一个数;

Step2.

0 < 3,所以就应该在左边的区间,直接 i++;

alt

Step3.

2 < 3,同理,i++;

alt

Step4.

1 < 3,同理,i++;

alt

所以当两个指针错位的时候,我们结束循环。

但是还差了一步,3 并不在正确的位置上呀。所以还要把它插入到两个区间中间,也就是和指针 i 交换一下。

alt
alt

齐姐声明:这里并不鼓励大家把 pivot 放最左边。

基本所有的书上都是放右边,既然放左右都是一样的,我们就按照大家默认的、达成共识的来,没必要去“标新立异”。

就比如围棋的四个星位,但是讲究棋道的就是先落自己这边的星位,而不是伸着胳膊去够对手那边的。

那当我们把 pivot 换回到正确的位置上来之后,整个 partition 就结束了。

之后就用递归的写法,对左右两边排序就好了。

最后还有两个问题想和大家讨论一下:

  1. 回到我们最初 选择 pivot的问题,每次都取最后一个,这样做好不好?

答:并不好。

因为我们是想把数组分割的更均匀均匀的时间复杂度更低;但是如果这是一个有序的数组,那么总是取最后一个是最不均匀的取法。

所以应该随机取 pivot,这样就避免了因为数组本身的特点总是取到最值的情况。

  1. pivot 放在哪

随机选取之后,我们还是要把这个 pivot 放到整个数组的最右边,这样我们的未排序区间才是连续的,否则每次走到 pivot 这里还要想着跳过它,心好累哦。

class Solution {
  public void quickSort(int[] array) {
    if (array == null || array.length <= 1) {
      return;
    }
    quickSort(array, 0, array.length - 1);
  }
  private void quickSort(int[] array, int left, int right) {
    // base case
    if (left >= right) {
      return;
    }

    // partition
    Random random = new Random(); // java.util 中的随机数生成器
    int pivotIndex = left + random.nextInt(right - left + 1);
    swap(array, pivotIndex, right);

    int i = left;
    int j = right-1;
    while (i <= j) {
      if (array[i] <= array[right]) {
        i++;
      } else {
        swap(array, i, j);
        j--;
      }
    }
    swap(array, i, right);

    //「分」
    quickSort(array, left, i-1);
    quickSort(array, i+1, right);
  }
  private void swap(int[] array, int x, int y) {
    int tmp = array[x];
    array[x] = array[y];
    array[y] = tmp;
  }
}

这里的时空复杂度和分的是否均匀有很大关系,所以我们分情况来说:

1. 均分

时间复杂度

如果每次都能差不多均匀分,那么

  • 每次循环的耗时主要就在这个 while 循环里,也就是 O(right - left);
  • 均分的话那就是 logn 层;
  • 所以总的时间是 O(nlogn).
alt

空间复杂度

  • 递归树的高度是 logn,
  • 每层的空间复杂度是 O(1),
  • 所以总共的空间复杂度是 O(logn).

2. 最不均匀

如果每次都能取到最大/最小值,那么递归树就变成了这个样子:

alt

时间复杂度

如上图所示:O(n^2)

空间复杂度

这棵递归树的高度就变成了 O(n).

3. 总结

实际呢,大多数情况都会接近于均匀的情况,所以均匀的情况是一个 average case.

为什么看起来最好的情况实际上是一个平均的情况呢?

因为即使如果没有取到最中间的那个点,比如分成了 10% 和 90% 两边的数,那其实每层的时间还是 O(n),只不过层数变成了以 9 为底的 log,那总的时间还是 O(nlogn).

所以快排的平均时间复杂度是 O(nlogn)。

稳定性

那你应该能看出来了,在 swap 的时候,已经破坏了元素之间的相对顺序,所以快排并不具有稳定性。

这也回答了我们开头提出的问题,就是

  • 为什么对于 primitive type 使用快排

    • 因为它速度最快;
  • 为什么对于 object 使用归并

    • 因为它具有稳定性且快。

以上就是快排的所有内容了,也是很常考的内容哦!那下一篇文章我会讲几道从快排引申出来的题目,猜猜是什么?😉

如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666/NYCSDE

alt
版权声明:本文为SheIsSDEatNYC原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/SheIsSDEatNYC/article/details/109503630

智能推荐

LeetCode(7 整数反转)

如题 这就不用分析了,直接依次取每位即可,难点就是个越界判断...

Caused by: java.rmi.ConnectIOException: error during JRMP connection establishment; nested exception

启动RMI报如下错误: 最后发现是端口冲突造成的,当时用的5003端口启动服务端的RMI刚好和本地的一个服务端口冲突。 输入netstat -aon|findstr "5003"查询它的pid为3056 继续输入tasklist|findstr "3056",查看是哪个进程或者程序占用了5003端口,结果是:magentproc.exe 找到PID后可以直接...

【LeetCode(Java) - 322】零钱兑换

文章目录 1、题目描述 2、解题思路 3、解题代码 1、题目描述 2、解题思路   定义 dp[i] 表示对于组成金额 i 的最少硬币个数。   如果方案存在,那么至少有一个硬币至少出现了一次:   如果是第 0 个硬币出现了一次,则:dp[i] = dp[i-coins[0]] + 1   如果是第 1 个硬币出现了...

在Visual Studio 2013中配置Entity Framework使用MySQL

环境 使用的软件及版本 - Microsoft Visual Studio Ultimate 2013 (版本 12.0.40629.00 Update 5) - Microsoft.Net Framework 版本 4.6.01055 - MySQL版本: 5.6.17 步骤 1. 创建空的MVC项目 2. 安装扩展 3. 在数据库中建立对应的表 必须在数据库内先新建表,否则asp.net mv...

Python才是世界上最好的言语,php,java靠边站

伟大的入门编程语言有什么特征呢?或者换一种方式问,“当我们教他们编程时,应该给予他们什么?”对于成年人和青少年学生,我认为以下五点非常重要。 学生从入门语言获得的五样东西 非常棒的首次体验,就像一本书的第一页,首先需要“入迷”,学习新知识不可避免的会遇到挫折,但要有持续的热情和好奇心,这对于那些从未接触过编码的年轻人来说是至关重要的; Web编程的能...

猜你喜欢

动态调整docker容器cpu资源

目的:动态调整系统cpu核数后,如何在不停止容器服务的情况下,docker动态使用最新的CPU资源 事件由来:     1、在ucloud上购买了一台可以热升级的机器,热升级指的是动态更改系统cpu和内存资源     2、随着业务的扩展,发现cpu、内存负载过高,需要在不停止业务的情况下动态扩容,因此使用了ucloud提供的热升级服务,从4核12G扩容为8核...

用python itchat包 爬取微信好友头像形成矩形头像集

原创作品,转载请注明作者 abysscarry-袁杰丶 初学python,我们必须干点有意思的事!从微信下手吧! 头像集样例如下: 大家可以发朋友圈开启辨认大赛哈哈~ 话不多说,直接上代码,注释我写了比较多,大家应该能看懂 运行结果: ok!!!...

impala实现拉链表

1.文档目的         拉链表是针对数据仓库设计中表存储数据的方式而定义的,即是记录历史。记录一个事物从开始,一直到当前状态的所有变化的信息。传统数据仓库一般采用拉链的方式保留主数据(例如客户信息)的变化数据,采用这种设计方式的主要原因是减少数据冗余。这个需求在Hadoop中主要是有以下两种实现方式选择: 每天保留一份全量的切片数据。Hadoop平台由...

Codeforce 975E

E. Hag's Khashba time limit per test3 seconds memory limit per test256 megabytes inputstandard input outputstandard output Hag is a very talented person. He has always had an artist inside him but his...

Gradle基础知识

Gradle基础知识 Gradle是一个非常先进的项目构建工具,它使用了一种基于Groovy的领域特定语言(DSL)来声明项目配置,摒弃了传统基于XML(Ant和Maven)的各种繁琐配置。 Gradle作为Android的构建系统,主要作用是编译应用资源和源代码,将其打包成可供测试、部署、签署和分发的APK。 Android Studio使用Gradle这个高级构建工具包来自动化执行和管理构建流...