JavaScript 插入排序代码

什么是排序？

排序是按顺序排列数据的方法。这种排序可以是数字、字母或用户定义的顺序。排序的一个常见应用是按字母顺序排列学生姓名列表，或按升序排列产品价格。排序有助于优化搜索和数据操作操作，因为已排序的数据更容易遍历和管理。

有几种排序算法，如快速排序、归并排序、插入排序和冒泡排序。每种算法都有其自己的使用场景和特性性能。选择合适的算法可以基于数据集的大小以及时间复杂度等因素。

什么是插入排序？

插入排序是一种非常简单直观的算法，非常接近你如何整理扑克牌。它一次一步地创建正在排序的数组，并将新项目插入到已排序项的正确位置。对于小型或几乎已排序的数据，插入排序是一种不错的算法。

插入排序是一种原地算法，这意味着它通过比较和交换值来排序数据，它在除了输入数组之外不使用任何额外空间来排序数据。事实上，其时间复杂度高于一些更高级的算法（例如快速排序、归并排序），这使得它对于大型数据集效率较低。

插入排序的工作原理

插入排序将一部分元素保持已排序状态，另一部分为未排序状态。这意味着已排序部分有一个元素，其余为未排序。该算法遍历未排序的部分， taking each element and inserting it into the correct position in the now-sorted part.

插入排序涉及的步骤

1. 关键（Key）将是第二个元素（索引号为 1）。
2. 将关键与已排序子数组的元素进行比较。
3. 在将关键插入已排序部分时，我们需要将所有大于关键的元素向右移动一个位置。
4. 将关键插入到正确的位置。

示例：插入排序的工作原理

让我们来看数组 [7, 3, 5, 2]，以了解插入排序的逐步工作过程

初始数组：[7, 3, 5, 2]

第一个数字7是我们唯一需要排序的数字。第二部分是未排序的部分，以 3 开始。

步骤 1

• 关键 = 3（第二个元素）
• 比较 3 和 7。由于 3 < 7，将 7 向右移动一个位置。
• 将 3 插入第一个位置。
• 步骤 1 后的数组：[3, 7, 5, 2]

步骤 2

• 关键 = 5（第三个元素）
• 比较 5 和 7。由于 5 < 7，将 7 向右移动一个位置。
• 比较 5 和 3。由于 5 > 3，将 5 放在 3 之后。
• 步骤 2 后的数组：[3, 5, 7, 2]

步骤 3

• 关键 = 2（第四个元素）
• 比较 2 和 7。由于 2 < 7，将 7 向右移动一个位置。
• 比较 2 和 5。由于 2 < 5，将 5 向右移动一个位置。
• 比较 2 和 3。现在，2 < 3，因此需要将 3 向右移动一个位置。
• 将 2 插入第一个位置。
• 步骤 3 后的数组：[2, 3, 5, 7]

最终排序数组[2, 3, 5, 7]

JavaScript 插入排序代码

插入排序算法的 JavaScript 实现如下：

输出

 
Original Array: [
  64, 34, 25, 12,
  22, 11, 90
]
Sorted Array: [
  11, 12, 22, 25,
  34, 64, 90
]   

代码解释

• 外层循环从第二个元素（索引 1）开始，因为我们假设第一个元素已排序。
• 关键 = 当前要比较的元素。
• 内部 while 循环将已排序空间中的大于关键的元素向右移动。
• 找到关键的合适位置后，插入关键，然后检查下一个元素。

插入排序是稳定的吗？

是的，如果对于相等元素，它们在输入数组中的顺序在输出数组中保持不变，则该排序算法是稳定的。正是这种特性使得插入排序在需要保留重复元素顺序的情况下很有用，例如根据多个字段对记录进行排序。

插入排序是什么类型的算法？

插入排序是一种基于比较的排序算法，它仍然能回答如何在内存中对元素数组进行排序的问题。因此，它利用比较来为每个元素找到正确的位置，并在不使用额外内存的情况下将其全部移动到输入数组中。其简洁性和较低的实现难度使其适合用于小型或几乎已排序的数据集。

插入排序是贪心算法吗？

不是，插入排序不是贪心算法。贪心算法是一类算法，它们在每一步都做出局部选择，希望获得全局最优解。另一方面，插入排序只旨在通过将每个元素放置在其正确位置来构建一个已排序的数组，而不必在每一步进行全局优化。

插入排序算法的时间复杂度

插入排序基于输入数组的类型

1. 最佳情况 (O(n))：当数组已排序时发生。它不需要任何移位，算法只需遍历数组。
2. 最坏情况 (O(n²))：当数组按降序排列时。对于已排序部分中的每个其他元素，都需要将每个元素进行比较并移回。
3. 平均情况 (O(n²))：适用于元素的随机排列。

由于插入排序在最坏情况下的时间复杂度是二次的，因此插入排序不是大型数据集的理想选择。

插入排序是否使用分治法？

不，分治法是指将问题分解为越来越小的子问题，分别解决它们，然后合并它们的结果。快速排序和归并排序等算法属于此类。而插入排序则以增量方式对数组进行排序，而无需将其分解为更小的问题。

为什么插入排序慢？

由于插入排序的平均和最坏情况时间复杂度为 O(n²)，对于大型数据集来说它太慢了。该算法将当前元素与前一个已排序部分的每个元素进行比较，然后在需要时进行移位。通过这些重复的比较和移位，当数组很大时，插入排序的效率非常低。对于更大的数据集，应优先选择优化的算法，例如归并排序或快速排序，它们可以最大限度地减少对整个数据集进行排序所需的比较和交换次数。

结论

插入排序是一种简单的排序算法，最适用于小型或几乎已排序的数据集。虽然它不是处理大型数组的最快算法，但考虑到其相对的简洁性和稳定性，它仍然是相当不错的。了解其工作原理使程序员有机会通过JavaScript来实现它。