小探险家学算法

Appearance

16. 快刀排序（快速排序） ​

知识点：快速排序 —— 选基准，小的站左边，大的站右边（平均 O(n log n)）

项目：给全校成绩单"秒排"

故事开场：三兄弟太慢了 ​

前几章，你学会了排序三兄弟——冒泡、选择、插入。它们都是 O(n²)。

老师把难题升级了："三兄弟排 50 人的成绩没问题。可全校 5000 人 的成绩单，三兄弟要比较约 1250 万次——能排，但总感觉笨笨的。 还有没有更快的办法？"

你盯着成绩单想了半天。突然，你想起第 15 章的递归：

"排 5000 人的成绩，能不能拆成两个小问题：先排左边一半，再排右边一半？"

老师眼睛一亮："好想法！那怎么拆？"

"嗯……"你挠挠头，"随便从中间劈开？可是劈开的两半还是乱的， 合起来也没用啊……"

笨办法先行：拆了，但没拆对 ​

你试着"从中间劈开"，然后对两半各自用第 12 章的冒泡排序排好：

ts
const scores = [78, 92, 65, 88, 70, 95, 60, 82]

const half1 = scores.slice(0, 4)   // 切出前 4 个：[78, 92, 65, 88]
const half2 = scores.slice(4)      // 切出后 4 个：[70, 95, 60, 82]

// 两半各自排好（用第 12 章的冒泡排序）
bubbleSort(half1)
bubbleSort(half2)

// 拼回去……
const whole = half1.concat(half2)
console.log(whole)

输出：

[65, 78, 88, 92, 60, 70, 82, 95]

还是乱的！ 左边半是排好了，可左边最小的 92 也比右边最大的 60 大—— 两半之间"谁也不服谁"。

你发现问题了："拆"的时候，没有把"大小"也拆开。 左边一半和右边一半没有分界线——左边有 92，右边有 60， 两边拼起来就乱。

那怎么办？拆的时候就要保证：左边全是小的，右边全是大的。

引出知识点：快排——"基准"当裁判 ​

快速排序（quick sort）的办法，就像老师排座位：

从队伍里随便叫一个人出来当"基准"（裁判），然后命令： "比我矮的，站我左边！比我高的，站我右边！"

于是队伍以基准为分界线，分成两堆。基准站的位置，就是它最终的位置—— 以后它再也不用动了！（左边都比它小，右边都比它大，它还能去哪？）

然后，左边一堆、右边一堆，各自再来一次：各叫一个基准， 再分两堆……直到每堆只剩一个人（或没人）——排好了！

看，"再来一次"——这就是递归！拆一次分一次，拆到最小为止。

动手实现：快速排序 ​

写成代码，一共三件事：选基准、分两堆、递归排两堆：

ts
// 快速排序：返回排好序的新数组
function quickSort(list: number[]): number[] {
  if (list.length <= 1) {
    return list                    // 出口：0 个或 1 个数，不用排
  }

  const pivot = list[list.length - 1]   // 选最后一个当基准
  const smaller: number[] = []          // 比基准小的站左边
  const bigger: number[] = []           // 比基准大的站右边

  for (let i = 0; i < list.length - 1; i++) {
    if (list[i] <= pivot) {
      smaller.push(list[i])
    } else {
      bigger.push(list[i])
    }
  }

  // 递归排两边，然后接起来：小的 + 基准 + 大的
  return quickSort(smaller).concat(pivot, quickSort(bigger))
}

const scores = [78, 92, 65, 88, 70]
console.log(quickSort(scores))

输出：

[65, 70, 78, 88, 92]

（concat 是数组的"拼接"：[1,2].concat(3, [4,5]) 得到 [1,2,3,4,5]。）

看 quickSort 的递归结构，和汉诺塔一样是"套娃"： 每次把问题切成两半（比基准小的、大的），再各自套娃。

跑起来：快排到底有多快？ ​

全校 5000 人的成绩单，让三兄弟（冒泡）和快排比一比：

ts
// 造 2 万个随机成绩
const bigList: number[] = []
for (let i = 0; i < 20000; i++) {
  bigList.push(Math.floor(Math.random() * 100))
}

// 冒泡排序（把第 12 章的搬过来）
function bubbleSort(list: number[]): void {
  for (let round = 0; round < list.length - 1; round++) {
    for (let i = 0; i < list.length - 1 - round; i++) {
      if (list[i] > list[i + 1]) {
        const temp = list[i]
        list[i] = list[i + 1]
        list[i + 1] = temp
      }
    }
  }
}

// 复制一份，分别计时（bubbleSort 会改原数组，所以要复制）
const list1 = bigList.slice()
const list2 = bigList.slice()

console.time("冒泡排序")
bubbleSort(list1)
console.timeEnd("冒泡排序")

console.time("快速排序")
quickSort(list2)
console.timeEnd("快速排序")

在我这台电脑上，输出（数字可能不一样，但差距会吓你一跳）：

冒泡排序: 约 700ms
快速排序: 约 40ms

2 万个成绩，冒泡要 700 多毫秒，快排只要 40 毫秒左右——快了近 20 倍！ 而且数据越大，差距越离谱（快排平均 O(n log n)，冒泡是 O(n²)； 10 万个数时，冒泡要好几十秒，快排还是几十毫秒）。

为什么快？ 因为快排每次"拆一半"：数据 100 万，冒泡要比较 5000 亿次，快排大约只要 2000 万次——它把 O(n²) 变成了 O(n log n)。 "拆成两半"的魔法，正是第 1 章 O(log n) 的亲戚：分多少层， 就能少做多少事。

小提醒：快排也有"运气差"的时候——如果每次都挑到最极端 的基准（比如排好的数组挑最后一个当基准），它就退化成 O(n²)。 但平均来说，它是最快的比较排序之一，所以叫"快"排！ 下一章还有个"稳"的：不管运气好不好，都是 O(n log n)。

小挑战 ​

  1. 换基准：把基准从"最后一个"改成"最中间那个"，再跑一遍， 看看结果还对不对（提示：list[Math.floor(list.length / 2)]—— 但选完之后记得把它从数组里"拿走"，别让它自己和自己比）。
  2. 找第 3 名：快排每次分区后，基准的位置就"永久定死"了。 利用这个特点：只关心"第 3 名"，可以不用把整队都排完—— 想想怎么省事（提示：分区后数一数左边有几个，就知道基准是第几名）。
  3. 字符串版：把 quickSort 改成能排字符串数组（把类型 number[] 改成 string[] 即可，字符串也能比较）， 用第 11 章的名单试试。

课后练习 ​

第 1 题（动手题）：手动分区 ​

纸上手动走一遍 quickSort([5, 3, 8, 1])：选基准、分两堆、递归， 画出每一步的 smaller、pivot、bigger，最后用程序验证结果。

参考答案（点开查看）
  • 选基准 1（最后一个）。smaller=[], bigger=[5,3,8]。 递归排 smaller=[]，pivot=1，递归排 bigger=[5,3,8]
  • 排 [5,3,8]：选基准 8。smaller=[5,3], bigger=[]。 排 [5,3]：选基准 3。smaller=[], bigger=[5]。 拼接：[] + 3 + [5] = [3,5] 拼接：[3,5] + 8 + [] = [3,5,8]
  • 最后拼接：[] + 1 + [3,5,8] = [1,3,5,8] ✅

程序输出也应该是 [1, 3, 5, 8]。

第 2 题（思考题）：快排为什么平均是 O(n log n)？ ​

快排每次分区，都把数组"大致分成两半"。想一想：分成两半这件事 一共要做多少次，才能把 n 个数拆到"每堆只有一个"？ 这和第几章学过的什么很像？

参考答案（点开查看）

每次都分成两半：n → n/2 → n/4 → … → 1，一共大约 log n 层 （还记得第 1 章的"能被除以 2 多少次"吗？）。

每一层，所有数加起来要处理大约 n 次（每层都在比较/搬运 n 个数）。 所以总共是 n × log n，写做 O(n log n)。

数据 100 万：O(n²) 是 1 万亿，O(n log n) 是 2000 万—— 差了 50 万倍。这就是"拆两半"的威力，也是二分查找、归并排序 （下一章！）、二叉搜索树（下下章！）共同的秘密。

第 3 题（思考题）：快排的坏运气 ​

如果数组本来就是排好序的（[1, 2, 3, 4, 5]），快排每次都挑 最后一个当基准——会发生什么？它还是 O(n log n) 吗？

参考答案（点开查看）

会退化！挑最后一个（5）当基准：比 5 小的全在左边，右边是空的—— 根本没分成两半！下次在左边继续挑最后一个……每次都只排掉一个数。

这样"拆"了 n 层，每层处理 n 个数，变成 O(n²)——快排最倒霉的时候， 和冒泡一样慢。

所以真正的快排会"随机"挑基准（或者挑前中后三个数里不大不小的）， 让"分两半"大概率成立。好算法，也要防坏运气。

下一课预告：合唱比赛，两个班各排好一支队伍，要合成一支大队伍。 有人提议："直接倒一起重新排！"——可两队的队首明明就是全场 最小的两个啊！看队首、比大小、谁小谁进——这办法叫什么？