JavaScript 插入排序程序

JavaScript 中插入排序概述

排序是任何从事计算机科学领域的人都必须理解的概念，无论他们选择学习哪种编程语言。排序过程通过按升序或降序排列数据，使我们能够高效便捷地查找所需数据。

排序算法对数字或字符串等元素进行排序。排序算法有很多种，可以根据它们的排序方法和实现过程中的方法进行分类，每种方法都有不同的优缺点。

在本文中，我们将重点介绍插入排序，这是一种常用的排序算法，也易于理解和使用。

JavaScript 中的插入排序是什么？

插入排序是一种简单直观的算法，适用于对小列表进行排序。它通过从左到右按顺序放置每个元素来工作。这是一种比较排序，因为它将当前元素与已排序列表中的另一个元素进行比较。它使用迭代方法将每个元素放置到列表中的正确位置。

算法的效率可以通过其完成排序过程所需的时间来判断；耗时越长，说明时间复杂度较差，需要其他排序技术。插入排序的时间复杂度为 O(n²)，表示最坏情况下的操作次数为 n。因此，由于性能不佳，它通常不能应用于大列表。相比之下，对于小列表，它比快速排序和归并排序等复杂技术更有效。

插入排序比选择排序和冒泡排序等其他二次排序更有效。最佳情况时间复杂度为 O(n)，即线性。这发生在输入数组已排序的情况下。然而，插入排序的平均运行时间复杂度仍然是二次的。

现在我们将看几个输入和输出的例子。

考虑一个包含随机顺序（未排序）元素的数组。我们可以借助插入排序算法对它们进行排序。那么让我们来看下面的例子。

插入排序算法是如何工作的？

可以通过实际演示来理解插入排序算法的功能。考虑数组 arr = [24, 22, 26, 10, 12]。

第一次遍历

在插入排序算法开始时，数组的前两个元素会相互比较。

在这种情况下，22 小于 24；因此，数字没有按升序排序，24 也未正确放置。因此，必须交换 22 和 24 的位置。在这种情况下，24 当前保留在一个子数组中。

第二次遍历

现在，比较数组中的接下来的两个元素。

在这种情况下，数字 24 和 26 是升序的，因为 26 大于 24。所以，不会发生交换。

此外，24 也属于包含 22 的子数组。

第三次遍历

目前，子数组包含两个元素 22 和 24。现在，我们将比较接下来的两个元素，10 和 26。

因为 10 小于 26，交换这两个值。

即使交换后，10 和 24 仍未排序，因此再次交换。

再次，10 和 22 未排序，因此再次交换。

现在，10 处于正确的位置。

第四轮

已排序子数组中的元素是 10、22 和 24。

接下来的两个元素是 26 和 12，它们正在进行比较。

由于它们未排序，因此交换这两个值。

现在，12 小于 24。因此，交换它们。

这里 12 小于 22，它们未排序，因此交换它们。

最后，数组已完全排序。

算法

要使用插入排序算法将大小为 n 的数组按升序排序，需要遵循以下步骤

1. 如果考虑的元素是第一个，则它已经排序。返回 1。
2. 选择下一个元素。
3. 将此元素与已排序子列表中的所有元素进行比较。
4. 将已排序子列表中的所有大于当前值的元素向右移。
5. 将当前值放入其正确的位置。
6. 重复此步骤，直到列表排序完成。

如果数据是有序的，它有助于找到复杂问题的最佳解决方案。这些操作的一些示例如下

1. 查找特定值。
2. 查找最小值或最大值。
3. 检查唯一性并消除重复项。
4. 计算给定值的出现次数等等。

演示 1

下面是插入排序算法的一个说明。

代码

输出

演示 2

使用 unshift() 方法

此方法用于在数组的开头插入其他元素。它返回数组的更新后的长度。

代码

输出

结论

插入排序是一种简单、稳定且就地（in-place）的比较排序算法。尽管它的时间复杂度为 O(n²)，这使得它相对较慢，但它对小型输入数组来说是非常有效的。在这种情况下，它的性能可能优于广泛使用的分治算法。正是由于这个原因，JavaScript 在其内置排序函数中采用了混合方法，将插入排序与归并排序或快速排序结合使用。

对于更大的数组，与许多其他二次排序算法（如冒泡排序、侏儒排序和选择排序）相比，插入排序也表现出卓越的性能。