背景

去年下半年，我在微信书架里加入了许多技术书籍，各种类别的都有，断断续续的读了一部分。

没有计划的阅读，收效甚微。

新年伊始，我准备尝试一下其他方式，比如阅读周。每月抽出1~2个非连续周，完整阅读一本书籍。

这个“玩法”虽然常见且板正，但是有效，已经坚持阅读七个月。

已读完书籍：《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript（上卷）》、《你不知道的JavaScript（中卷）》、《你不知道的JavaScript（下卷）》、《数据结构与算法JavaScript描述》、《WebKit技术内幕》、《前端架构：从入门到微前端》。

当前阅读周书籍：《秒懂算法：用常识解读数据结构与算法》。

用或不用大O来优化代码

大O记法是比较算法以及确定特定情况下最优算法的绝佳工具。不过它并不是唯一途径。事实上，很多时候两个算法的时间复杂度相同，其中一个却运行得更快。

选择排序

选择排序的步骤如下：

(1) 从左向右检查数组的每一个格子，找出最小值。在检查的过程中，使用一个变量记录下至今为止的最小值所在的索引。如果一个索引处的值比变量所表示的值更小，就更新变量中存储的索引。

(2) 一旦确定了最小值所在的索引，就把它的值和最初遍历的值交换位置。在第一次遍历中，最初检查的是索引0，第二次检查的是索引1，以此类推。

(3) 每次遍历都要执行第(1)步和第(2)步。不断遍历，直到某次遍历开始于数组结尾。此时数组已正确排序。

选择排序实战

下面将以[4, 2, 7, 1, 3]这个数组为例，详细说明选择排序的步骤。

从第一次遍历开始。首先检查索引0处的值。根据定义，它就是目前为止检查过的最小值（因为目前只检查了这一个值），因此把它的索引存储在一个变量中。

第1步：把2和目前为止的最小值（也就是4）进行比较。因为2比4还小，所以它就成了新的最小值。

第2步：把下一个值7和最小值做比较。因为7比2大，所以最小值仍然是2。

第3步：把1和最小值做比较。因为1比2小，所以1就成了新的最小值。

第4步：把3和最小值1做比较。因为3已经是数组末尾，所以1就是整个数组的最小值。

第5步：因为1是最小值，所以把它和最初遍历的索引0处的值互换。因为已经把最小值移动到了数组开头，所以最小值的位置现在是正确的。

下面可以开始第二次遍历了。

准备工作：因为第一个格子（也就是索引0）已经正确排序，所以第二次遍历从下一个格子（索引1）开始。索引1处的值是2，而它也是目前为止第二次遍历中的最小值

第6步：把7和最小值做比较。因为2小于7，所以2仍是最小值。

第7步：把4和最小值做比较。因为2小于4，所以2仍是最小值。

第8步：把3和最小值做比较。因为2小于3，所以2仍是最小值。

至此我们又遍历到了数组末尾。因为最小值已经在正确位置，所以无须进行交换。

接下来开始第三次遍历。

准备工作：从索引2的值7开始。7也是目前为止第三次遍历中的最小值。

第9步：把4和7做比较。4现在成了新的最小值。

第10步：3比4还要小。3成了新的最小值。

第11步：因为3位于数组末尾，所以把它和第三次遍历最初检查的值7进行交换。现在3也得到了正确排序。

第12步：比较7和4。4仍是目前为止本次遍历中的最小值。因为它已经位于正确位置，所以无须交换。

代码实现：选择排序

function selectionSort(array) {
  for(let i = 0; i < array.length - 1; i++) {
    let lowestNumberIndex = i;
    for(let j = i + 1; j < array.length; j++) {
      if(array[j] < array[lowestNumberIndex]) {
        lowestNumberIndex = j;
      }
    }
    if(lowestNumberIndex != i) {
      let temp = array[i];
      array[i] = array[lowestNumberIndex];
      array[lowestNumberIndex] = temp;
    }
  }
  return array;
}

选择排序的效率

选择排序包含两类步骤：比较和交换。在每次遍历中，需要把每个值和当前最小值进行比较。如有必要，需要把最小值交换到正确位置。

一般来说，对于有N个元素的数组，一共需要(N – 1) + (N – 2) + (N – 3) + … + 1次比较。

至于交换，每次遍历最多需要1次。这是因为在一次遍历中，交换的次数取决于最小值是否位于正确位置。这个次数不是0就是1。而冒泡排序在数组完全倒序这种最坏情况下，每次比较都需要1次交换。

选择排序所需的步数大约是冒泡排序的一半，因此前者比后者快一倍。

总结

可以用大O来大致确定算法效率，还可以比较相同时间复杂度的算法的效率。

不过，在比较两个算法效率时还需要考虑一个重要因素。但根据定义，不可能总出现最坏情况。一般来说，大部分情境是平均情况。

作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。
如果看完文章有所收获，欢迎点赞👍 | 收藏⭐️ | 留言📝。