# 快速排序通俗讲解

演示快速排序如何选基准、把积木分成两队并让基准归位，再逐层排好整排八块数字。

By quiet\-comet\-b3e973fd

Topic: Computing, AI & Electronics

[Open the interactive Jig](https://ask.jig.com/j/fVKAJZtQzGfm)

## Transcript

### 1. 一排乱序的积木

桌上有八块积木，分别写着 1 到 8，可是顺序全乱了。我们要把它们从小到大排好。快速排序就是一种又快又聪明的排队方法，电脑每天都用它整理大量数据。拖动画面可以转着看。

快速排序是英国科学家托尼·霍尔在 1959 年想出来的，1961 年正式发表。

### 2. 先选一个“基准”

第一步，挑一块积木当“基准”，也就是拿来比较的标杆。这里我们挑最左边的 5 号，它变成金色并微微抬起。接下来，每块积木只需要和它比一比。

基准挑哪一块都可以。挑得好，后面就排得更快。

### 3. 比一比，分两队

每块积木都和 5 比大小：比 5 小的变成蓝色，站到左边；比 5 大的变成珊瑚红色，站到右边。这一步叫“分区”。点按钮，看它们怎么分队。

分区时，每块积木只和基准比一次。8 块积木只要比 7 次。

### 4. 基准站到了最终位置

分完队后，5 的左边全比它小，右边全比它大。所以 5 已经站在它最后该在的位置，以后再也不用动，它变成了绿色。不过左右两队里面还是乱的。

一次分区不会把所有积木排好，它只保证基准归位。

### 5. 分而治之

接下来，对左队和右队做同样的事：各自选基准、分两队、基准归位。队伍越分越小，只剩一块时，它自然就排好了。点按钮，看整排积木一块块变绿。

把大问题拆成同样的小问题来解决，叫做“分而治之”。

### 6. 电脑的做法：原地交换

电脑不会另找地方排队，而是在原来的位置上交换积木。蓝色和红色两个指针从两头往中间走：蓝指针找比基准大的，红指针找比基准小的，找到就让这两块换位置。两个指针相遇后，再把基准换到中间。

这样几乎不需要额外的空间，叫做“原地排序”。

### 7. 为什么这么快

每一轮分区，每块积木大约只比一次。如果每次都分成差不多的两半，8 块积木分 3 层就排好了。1000 个数大约只要 10 层，一共一万多次比较；如果每两个数都比一遍，要将近 50 万次。

数据每多一倍，只多出一层。100 万个数也只要大约 20 层。

### 8. 运气不好的时候

如果积木本来就排好了，又总挑最左边的当基准，每次只能分出一块，剩下的队伍几乎没变小。8 块积木要分 7 层，比较 28 次。换成 1000 个数，要比较将近 50 万次。

这是快速排序最慢的情况：名字里有“快”，也不保证每次都快。

### 9. 聪明选基准，你来试试

所以真正的程序常常随机挑基准，或者在开头、中间、结尾三块里取大小居中的那块，避开坏运气。现在轮到你：点一块还没变绿的积木，让它当基准。全部变绿就成功了！

许多编程语言自带的排序工具，都用到了快速排序的思想。