使用 Javascript 实现插入排序

数组排序

算法

开发人员需要哪些算法？

插入排序

JavaScript 中的插入排序

解释如下……

分析算法（像计算机科学家一样思考 :D）

最坏情况和最好情况

接下来会发生什么？

喜欢这篇文章吗？

你觉得算法很酷吗？你最喜欢的编程语言是 JavaScript 吗？

在本文中，我将介绍如何开始学习算法，以及为什么作为开发者需要理解算法，还会涉及一些其他主题。作为我们的第一个算法，我将使用插入排序，它对于初学者来说很容易理解。

数组排序

var arr = [6,3,2,1,7,4];

在 JavaScript 中，对这个数组进行排序非常容易。

arr.sort();

这种排序方式是一种高级方法，是 JavaScript 提供的功能。在本文中，我们将以算法的方式探讨排序问题。

有很多算法可以用来对数组进行排序，插入排序就是其中之一。插入排序是理解算法的绝佳入门方法。（排序是计算机科学中的一项基本操作。）

算法

算法是一种计算过程，它接受输入并产生输出。例如，将一个未排序的数组输入到排序算法中，然后得到一个排序后的数组。（这就是我们在这里要做的。）

算法是为了解决特定的计算问题而创建的。好的算法能够快速高效地解决这些问题。稍后我会解释“好”的含义。

开发人员需要哪些算法？

这很难解释。但是，理解算法确实能帮助你在开发过程中以全新的方式思考。它能帮助你快速编写代码，并让你的大脑快速运转，从而为你提供最佳结果。（Quora 上关于此主题的讨论）

插入排序

让我们来深入探讨这个问题！

问题：对数组进行排序
输入：一个数字数组（未排序）
输出：已排序的数组

插入排序是一种高效的算法，用于解决计算机领域的“排序问题”。它的工作原理与我们整理一副扑克牌的方式完全相同。

• 首先，你手里的牌都摆在桌面上。
• 然后，你拿一个，把它拿在手里。
• 接下来，你再拿一个，把它和第一个进行比较，然后把它放到正确的位置。
• 然后，你拿到第三张牌，并将其放在与其他两张牌对应的正确位置。
• 同样的过程仍在继续……
• 最后，你将得到一手整理好的牌。

你应该注意到的一点是，手中的牌总是已经排序好的。

JavaScript 中的插入排序

让我们用 JavaScript 来实现我们刚才用英语讨论的内容。（只需 7 条规则）

function insertionSort(arr) {
    for (var i = 1, len = arr.length; i < len; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

函数的使用

var arr = [3,1,5,6,2];
console.log(insertionSort(arr));

解释如下……

• 我们将一个未排序的数组传递给我们的函数。
• for (var i = 1, len = arr.length; i < len; i++)从索引 1 到 n 创建一个循环len - 1。因此，我们不使用循环中的第一个元素。
• key = arr[i]将值保存到变量中。key是我们要插入手中的“牌”。
• j = i - 1初始 j 为i - 1，它是紧邻的前一个索引i。
• while (j >= 0 && arr[j] > key)遍历我们手中的牌，如果索引值j大于我们的键值。
• arr[j + 1] = arr[j]将我们检查过的元素（索引 j）向右移动一位。
• j--，j 值减小。因此，我们可以检查前一个元素。如果 jj < 0为零，则 while 循环结束，因为我们手中没有更多牌了。
• arr[j + 1] = key将卡片插入到正确位置。（j + 1之所以使用 `while` 循环，是因为在循环内部，`i` 的值j会比应该的次数多减一次。）

逐个循环地举例……

理解一个包含循环的算法时，最好的方法是逐层分析，并结合例子进行讲解。这样能让你真正理解算法的运行机制。

我们来看第一个循环。

• [3,1,5,6,2]这是我们的未排序数组。（包含 5 个元素，索引从 0 到 4）
• for 循环遍历索引 1 到 4（[1,5,6,2]元素）

第一个 for 循环

• i是 1
• key是1
• j为 0
• arr[j]是 3
• arr[j]>key

所以，我们将元素 3 向右移动一位。现在我们得到了数组[3,3,5,6,2]。

• j--现在j值为 -1。j < 0因此，while 循环终止。
• arr[j + 1] = key等于arr[0] = 1。

第一次循环后，我们得到了数组[1,3,5,6,2]

我们刚刚把卡片“1”放到了手中的正确位置（我们手中只有[3]张牌）。

第二个 for 循环

• i是 2
• key是5
• j是 1
• arr[j]是 3
• arr[j]<key
• while 循环没有运行

[1,3,5,6,2]第二个 for 循环后，我们得到的数组与之前相同。

第三个 for 循环

• i是 3
• key是6
• j是 2
• arr[j]是5
• arr[j]<key
• while 循环没有运行

[1,3,5,6,2]第二个 for 循环后，我们得到的数组与之前相同。

Forth 循环

这才是精彩的部分。

现在我们[1,3,5,6]手里已经有了（已排序的）元素。2这是我们正在检查的元素。我们将把它插入到正确的位置。

• i是 4
• key是2
• j是 3
• arr[j]是 6
• arr[j]>key
• while 循环运行
  • 6向右移动一次。现在我们有[1,3,5,6,6]
  • 5 > 2向右移动5一次。[1,3,5,5,6]
  • 3 > 2向右移动3一次。[1,3,3,5,6]
  • 1 < 2这就是数字 2 的位置！把它插入到后面1。现在我们有了[1,2,3,5,6]。

我们刚刚使用插入排序对数组进行了排序！

分析算法（像计算机科学家一样思考 :D）

当有多个算法可以解决同一个问题时（例如：对于“排序问题”，有插入排序、归并排序、选择排序等），我们需要分析每个算法，找出最佳算法。

一般来说，算法分析意味着预测算法所需的资源。这些资源包括内存、带宽、计算机硬件使用情况等等。计算时间是最常用的算法分析指标。计算时间越长，算法的性能就越差。算法分析需要考虑诸多因素。

在本文中，我将解释一种分析我们创建的算法的简单方法。要完成这项任务，你需要理解以下概念。

• 如果计算机有一条指令可以对数组进行排序呢？这样只需要一条命令就能完成排序。（这并非arr.sort()JavaScript 的实现方式。JavaScript.sort()会使用插入排序来对数组进行排序，前提是元素个数少于 10 个。）在实际的计算机中，我们只有用于算术运算、条件判断、数据移动等操作的指令。
• 我们将使用 RAM 模型，该模型逐条执行指令，不支持并发操作。
• 使用插入排序对一千个数字进行排序比对三个数字进行排序要花费更多时间。在现代计算机中，这种时间差异可以忽略不计。但是，如果数字达到十亿，这种差异就至关重要了。
• 插入排序所需的时间取决于输入数组的有序程度。
• 插入排序所需的时间取决于输入数据量（输入大小）以及每次执行的步骤数。

最坏情况和最好情况

对于插入排序，

当输入数组已排序时，程序运行时间最佳。最佳情况下，运行时间可以表示为 O(n^2) an + b，其中 na和 nb是常数，nn是输入数组的大小。

最坏情况发生在输入数组按降序排列时。在这种情况下，运行时间可以表示为 O(n^2) an(2) + bn + c，这是一个二次函数。

这些数学公式是基于输入规模和运行时间等概念建立的，这些概念并不难理解。但是，我不会在这里列出具体的数学计算过程。

接下来会发生什么？

如果你读到这里，我真的很高兴！以下是一些你可以做的事情。

• 跟着教程做！（可汗学院的教程就不错）
• 读一本关于算法的书。（我推荐这本。）
• 继续用 Python 编写代码。然后，用 JavaScript 重写一遍。学习算法时，Python 是最容易编写代码的语言。如果你更喜欢享受算法带来的乐趣，那就把它转换成 JavaScript 吧（就像我一样 :) ）。

喜欢这篇文章吗？

如果您喜欢这篇文章，并且愿意支持我，我创建了一个新网站Hyvor Groups，您可以在这里创建群组、加入群组、发布和分享帖子。请加入 Hyvor Groups，分享您的作品、提出问题，并将网站分享给您的朋友。

相关群体

1. Web开发者群组
2. PHP 集团
3. Javascript 组

欢迎创建您自己的群组！

谢谢你！