JS编程: 插入排序
想成为一个更好的开发者，那么理解数据结构、算法和基本编程思想是必须的。现在大多数问题都被现代工具和各种库解决了，但是对这些领域有一个更深的了解，将会大大拓宽你软件开发的视野。
就我自己而言，掌握这些概念是相当困难的，因为在我每天的工作里，几乎都不用这些。我正在写的这一系列文章就是为了提升我和那些跟我一样的人对这些方面的理解。
什么是插入排序？
插入排序是另一个常用的排序算法，即使它相比快速排序或归并排序而言，性能并不高。它的工作原理是将数组分成两个部分——一部分排好序，一部分没有排序。我们不知道每个项是否都已经处在正确的位置，所以我们会从第一个项开始排序。
然后我们检查数组里的其它项。对于排序数组里的每一个项，我们都必须找到它恰当的位置。做法是找打第一个比它小的项，或者直到列表的开头。或许我直接给你展示一个实际例子更好。被排序的项会被加粗：
**5**, 9, 13, 4, 1, 6 // 唯一被排序的部分是第一个项**5, 9,** 13, 4, 1, 6 // 9 > 5 ，所以我们不移动**5, 9, 13**, 4, 1, 6 // 13 > 9 我们也不移动**4, 5, 9, 13**, 1, 6 // 所有项和4相比, 一直到数组开头**1, 4, 5, 9, 13**, 6 // 所有项和1相比, 一直到数组开头**1, 4, 5, 6, 9, 13** // 第一个比6小的项5, 把6放在它前面它是
插入排序的特别之处在于我们并没有交换项，即使看起来像是我们交换并移动了它们。实际情况是我们循环遍历排好序的部分，并找到第一个较小的项（或数组的开头），并将我们的项放在那里。在这之前，我们对它们做了什么？ 由于我们循环遍历了每一个项，每一个值较大的项实际上都往前移动了一位（好吧，不是移动，是复制），以此给当前项让出位置。
最好给出一个关于实际算法的代码展示，以便你能对具体发生了什么有一个更好的了解：
function insertionSort (items) {
for (var i = 0; i < items.length; i++) {
let value = items[i]
// 存储当前项的值，以便它能被放在正确的位置
for (var j = i - 1; j > -1 && items[j] > value; j--) {
// 遍历数组排序好的项 (从当前项到数组开头)
// 复制每一个项到下一个位置
items[j + 1] = items[j]
}
// 到最后一个项时，我们应该保存当前排好序的项的值
items[j + 1] = value
}
return list
}
const list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
console.log(insertionSort(list)) // [ 17, 20, 26, 31, 44, 54, 55, 77, 93 ]一旦你明白了这个概念，再将其转移到代码上就一点不难。我认为这是一种更简单的算法实现。花些时间在上面，在纸上把它写下来，抓住其思想，再去编码就不是问题了。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2017-08-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
