小探险家学算法

Appearance

13. 挑最小的（选择排序） ​

知识点：选择排序 —— 每趟挑出最小的放前面（O(n²)，但交换少）

项目：体育课排队挑人

故事开场：体育老师的方法 ​

体育课要排队做操，老师看了一眼乱糟糟的队伍，说：

"都别动！听我口令——"

老师走到队伍里，左看看右看看，挑出最矮的同学，让他站到第 1 位。

"好了，第 1 位定下来了。"老师继续，"剩下的同学里，再挑最矮的， 站到第 2 位！"

一遍又一遍：从剩下的队伍里挑最矮的，放到前面。一会儿功夫， 队伍就整整齐齐从矮到高排好了。

你看着这一幕，心想：这办法比冒泡排序聪明啊！

冒泡排序是一趟一趟"冒泡"，一边比较一边换，换位特别多； 而老师的办法，每趟只挑一个人——挑出来的那个人，直接放到 它该去的位置，一趟只交换一次。

笨办法先行：挑出来，放哪？ ​

你兴冲冲地写代码，可马上就卡住了："挑出最小的……然后放哪？"

你想了想："放到最前面呗！"于是你写了：

ts
const heights = [162, 150, 175, 158, 169]

// 找到最小的身高（第 0 个开始）
let bestIndex = 0
for (let i = 1; i < heights.length; i++) {
  if (heights[i] < heights[bestIndex]) {
    bestIndex = i
  }
}
console.log("最矮的是：" + heights[bestIndex] + "cm")   // 150

// 放到最前面！？
heights[0] = heights[bestIndex]
console.log(heights)

输出：

最矮的是：150cm
[150, 150, 175, 158, 169]

坏了！ 把 150 放到第 0 位，原来的第 0 位（162）被覆盖了—— 现在有两个 150，162 神秘失踪！

你发现问题了："放到最前面"不是把前面的数据扔了， 是交换：把第 0 位的人和最矮的人换一下位置。 换，而不是覆盖——就像体育老师让两个同学互换位置一样。

引出知识点：选择排序——挑一个，换一次 ​

正确的写法是：挑出最矮的 → 和"最前面那个还没排好的位置"交换。

我们拆成两个函数：

ts
// 从 list 的第 start 位开始（包括 start），找到最小的那个的下标
function findSmallest(list: number[], start: number): number {
  let best = start                       // 先假设 start 位就是最小的
  for (let i = start + 1; i < list.length; i++) {
    if (list[i] < list[best]) {
      best = i                           // 找到更小的，更新
    }
  }
  return best
}

// 交换第 a 位和第 b 位的两个数
function swap(list: number[], a: number, b: number): void {
  const temp = list[a]
  list[a] = list[b]
  list[b] = temp
}

然后，像体育老师一样一趟趟挑人：

ts
function selectionSort(list: number[]): void {
  // 第 0 位到倒数第 2 位，一个一个定下来
  for (let pos = 0; pos < list.length - 1; pos++) {
    const smallest = findSmallest(list, pos)   // 从剩下的里挑最矮的
    swap(list, pos, smallest)                  // 和最前面的换一下
  }
}

const heights = [162, 150, 175, 158, 169]
selectionSort(heights)
console.log(heights)

输出：

[150, 158, 162, 169, 175]

看，从矮到高，整整齐齐！注意 findSmallest(list, pos) 里的 pos： 每趟挑人的范围是"从第 pos 位开始"——因为第 0~pos-1 位已经排好了， 不用再管。这就像老师说的"剩下的队伍"。

跑起来：选择排序的每一步 ​

我们让程序"慢动作"播放每一趟，看看它到底做了什么：

ts
const test = [162, 150, 175, 158, 169]

for (let pos = 0; pos < test.length - 1; pos++) {
  const smallest = findSmallest(test, pos)
  console.log(
    "第 " + (pos + 1) + " 趟：从第 " + pos + " 位开始挑，挑中了 " +
    test[smallest] + "（第 " + smallest + " 位），和第 " + pos + " 位交换"
  )
  swap(test, pos, smallest)
  console.log("现在数组：" + test.join("、"))
}

输出：

第 1 趟：从第 0 位开始挑，挑中了 150（第 1 位），和第 0 位交换
现在数组：150、162、175、158、169
第 2 趟：从第 1 位开始挑，挑中了 158（第 3 位），和第 1 位交换
现在数组：150、158、175、162、169
第 3 趟：从第 2 位开始挑，挑中了 162（第 3 位），和第 2 位交换
现在数组：150、158、162、175、169
第 4 趟：从第 3 位开始挑，挑中了 169（第 4 位），和第 3 位交换
现在数组：150、158、162、169、175

每一趟，一个数永久归位：150 → 158 → 162 → 169 → 175。 第 4 趟结束，5 个数全排好了。

（join("、") 是数组的新玩法：把元素用"、"连成一句话打印出来， 比手写循环省事。）

选择排序 vs 冒泡排序 ​

冒泡排序选择排序
核心动作相邻两个比较，小的往后换挑出最小的，和最前面的换
比较次数约 n² ÷ 2 次约 n² ÷ 2 次（一样）
交换次数约 n² ÷ 2 次（非常多）最多 n 次（每趟一次）
数据大时比较+交换都多比较多，但交换很少

两个都是 O(n²)——比较的次数一样多。但选择排序的交换少得多： 冒泡排序动不动就换位，选择排序每趟只换一次。

交换看起来小事一桩，但"交换"意味着搬动数据。在真正的程序里， 数据可能是几兆字节的大文件、数据库里的一整行记录—— 搬一次很贵。所以要排序的数据"搬起来很贵"时，选择排序比冒泡划算。

一句话记住两个兄弟： 冒泡——"一路比，一路换，一趟沉一个"； 选择——"每趟挑最小的，和最前面的换"。

小挑战 ​

  1. 倒过来：改成从高到低排（提示：改 findSmallest 里的一个符号， 让它挑最大的）。
  2. 找最大的：写一个 findLargest(list, start)，把 selectionSort 改成每趟挑最大的放到最后面（提示：像冒泡一样，每趟范围少一个）。
  3. 记录：用第 12 章的"计数器"方法，分别数一数选择排序在 排 50 个数时比较了多少次、交换了多少次。比较次数大约 是多少？交换次数呢？是不是"比较多、交换少"？

课后练习 ​

第 1 题（动手题）：排队做操 ​

用 selectionSort 给班级身高排队：[148, 155, 152, 160, 149, 158]， 从矮到高排，输出结果，并说出手动验证一下结果对不对。

参考答案（点开查看）
ts
const classHeights = [148, 155, 152, 160, 149, 158]
selectionSort(classHeights)
console.log(classHeights)
// [148, 149, 152, 155, 158, 160]

验证方法：把原数组抄下来，自己按"每趟挑最小的"走一遍， 和程序输出对比。走完 5 趟（6 个数排 5 趟），数组应该完全有序。

第 2 题（思考题）：为什么第 0 位"不见了"？ ​

在"笨办法先行"里，heights[0] = heights[bestIndex] 把 162 弄丢了。 用一句话解释：为什么"覆盖"会丢数据，而"交换"不会？

参考答案（点开查看）

覆盖是"把新值写进格子里"，旧值直接被抹掉——162 被 150 盖住，没人记得了。

交换是"两个格子里的值互相换"，用 temp 先端住一个，再挪另一个， 一个值都不丢。

所以往数组的某个位置"放东西"时，先想想：那个位置原来的东西 还要不要？要，就交换；不要，才覆盖。

第 3 题（思考题）：选择排序是 O(n²) 吗？ ​

选择排序每趟都要"从头找到尾"找最小的——那它一共要比较多少次？ 用 n 表示，它是 O(几)？

参考答案（点开查看）

第 1 趟比较 n−1 次，第 2 趟 n−2 次……最后一趟 1 次， 一共 (n−1) + (n−2) + … + 1 ≈ n × n ÷ 2 次，是 O(n²)。

和冒泡一样，比较次数随数据"平方"增长——数据翻 10 倍，比较翻 100 倍。 但交换只有 n 次左右（每趟一次），这是它比冒泡强的地方。

下一课预告：体育老师挑人是"从剩下的人里挑最矮的"。 可还有一种完全不同的思路：摸牌理牌——新摸到一张牌， 插到手里已经排好的牌堆的正确位置。它叫插入排序， 而且它对"差不多已经排好"的数据特别快，你知道吗？