比较
交换
分区

  • 正在分区的部分
  • 基准
  • 比较中
  • 已交换
  • 已就位

更多关于快速排序

快速排序

快速排序选一个基准,把所有较小的值移到它前面,其余的值移到它后面,再用同样的方法对两侧排序。每次分区后,基准都会落在最终位置。选择基准的选取方式,以任意速度播放排序,或逐次比较地单步执行,看看为什么在已排序的列表上选错基准会让快速排序变慢。 按“播放”观看排序过程,或用“单步”和“后退”逐次比较。拖动步骤滑块可跳到任意位置。卡片统计比较次数、交换次数和分区次数。可选择柱子数量、初始顺序,或输入自己的数字,还可选择基准的选取方式。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 键跳到开头和结尾。

它是如何运作的

  1. 选择柱子数量和初始顺序:随机、基本有序、倒序或少量不同值。也可以输入自己的数字。
  2. 按“播放”,或用“单步”和“后退”逐次比较。拖动步骤滑块可跳到排序的任意位置。
  3. 选择基准规则:最后一个值、中间值、随机值或三数取中。在已排序的列表上逐一试试。

快速排序的原理

从待排序的部分中选一个值作为基准,并把它移到末尾。从左到右检查其他值;每个比基准小的值都交换到从开头开始增长的左侧部分。然后把基准交换到左侧部分之后。它前面的值现在都比它小,后面没有比它小的值,所以基准已在最终位置。再用同样的方法对它前面和后面的部分排序,直到每个部分只剩一个值。

为什么基准很重要

当基准落在中间附近时,每次分区都把问题减半,比较次数按 n log n 增长:40 个随机值约需 190 次。当基准是最小值或最大值时,一侧为空,另一侧包含其余所有值。以最后一个值为基准时,已排序或倒序的列表每一步都会这样,排序需要 n(n − 1)/2 次比较,40 个值就是 780 次。随机基准或首、中、尾三个值的中位数在实践中可以避免这种情况。

常见问题

快速排序是如何工作的?

它选一个基准,对列表分区,使较小的值在基准前面、其余的值在后面,然后用快速排序对两侧排序。每次分区后,基准都在最终位置。

为什么快速排序在已排序的列表上很慢?

以第一个或最后一个值为基准时,已排序的列表总会选出最小值或最大值作为基准。分区的一侧为空,每次分区只去掉一个值,排序需要 n(n − 1)/2 次比较。随机基准或三数取中在实践中可以解决这个问题。

快速排序比归并排序快吗?

在实践中通常如此:它原地排序,不需要缓冲区,内层循环也很简单。平均而言,它的比较次数比归并排序多一些,最坏情况是 n²,而归并排序始终是 n log n。introsort 等库排序先用快速排序,分得太不均匀时就改用堆排序。

快速排序稳定吗?

不稳定。分区会把值远距离交换,相等的值可能改变顺序。

我的数字会被发送到别处吗?

不会。排序在你的浏览器中运行,上次的设置保存在此浏览器的本地存储中。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

前往编辑器