使用 Javascript 进行算法之旅 - 插入排序

什么是插入排序？

插入排序是计算机科学中的另一种基本排序算法。它一次构建一个最终的排序数组。这很像对一手扑克牌进行排序 - 您一张一张地拿起牌，并将每张牌插入到您已排序的牌中的正确位置。

插入排序如何工作

插入排序迭代数组，每次迭代都会增加已排序的部分。对于每个元素，它将与已排序的元素进行比较，向上移动它们，直到找到插入当前元素的正确位置。

以下是分步说明：

1. 从第二个元素（索引 1）开始作为“当前”元素。
2. 将当前元素与之前的元素进行比较。
3. 如果当前元素较小，则与之前的元素进行比较。将较大的元素向上移动，为交换的元素腾出空间。
4. 重复步骤2-3，直到整个数组排序完毕。

插入排序的可视化：

录制的 gif 来自 https://visualgo.net/en/sorting

在 JavaScript 中实现插入排序

让我们看一下JavaScript中插入排序的实现，每个部分都有详细的注释解释：

function insertionSort(arr) {
  // Start from the second element (index 1)
  // We assume the first element is already sorted
  for (let i = 1; i < arr.length; i++) {
    // Store the current element we're trying to insert into the sorted portion
    let currentElement = arr[i];
    // Define the starting index of lookup (this is the last index of sorted portion of array)
    let j = j - 1;
    // Move elements of arr[0..i-1] that are greater than currentElement
    // to one position ahead of their current position
    while (j >= 0 && arr[j] > currentElement) {
      // Shift element to the right
      arr[j + 1] = arr[j];
      j--;
    }
    // We've found the correct position for currentElement (at j + 1), insert it:
    arr[j + 1] = currentElement;
  }

  // The array is now sorted in-place:
  return arr;
}

要点：

1. 双向过程：插入排序通过向前移动的外循环和向后查看的内循环进行操作，从而创建构成算法核心的来回运动。
2. 前向扫描（外环）：

   for (let i = 1; i < arr.length; i++)

在数组中向前移动，一次选择一个未排序的元素 (currentElement = arr[i])。

1. 向后插入（内循环）：

   while (j >= 0 && arr[j] > currentElement)

向后查看已排序的部分，向右移动较大的元素 (arr[j 1] = arr[j]) 以为当前元素腾出空间。

1. 元素插入：

   arr[j + 1] = currentElement;

将当前元素插入到正确的位置，增加排序部分。

1. 就地稳定排序：直接修改原数组，保持相等元素的相对顺序。

插入排序每次构建一个最终排序数组，模仿您对一手牌进行排序的方式。它重复地从未排序的部分中选择一张卡片（元素）并将其插入到已排序的卡片中的正确位置，并根据需要移动较大的卡片。这种直观的过程使得插入排序对于小型或接近排序的数据集非常高效。

插入排序稳定吗？

是的，插入排序是一种稳定的排序算法。排序算法的稳定性意味着相等元素的相对顺序在排序后得以保留。插入排序因其操作方法而自然地实现了这一点：

1. 保留顺序：将元素插入已排序部分时，插入排序仅移动严格大于当前元素的元素。这意味着如果有多个元素具有相同的值，它们的相对顺序将被保持。
2. 没有不必要的交换：与可能交换相等元素的其他排序算法不同，插入排序仅在必要时移动元素。这个特性确保相等的元素保持在原来的相对位置。
3. 从左到右处理：通过从左到右处理数组，并将每个元素插入到已排序元素中的正确位置，插入排序自然会保持相等元素的原始顺序。

在对复杂数据结构进行排序时，插入排序的稳定性特别有用，因为保持相等元素的原始顺序非常重要。例如，当先按年级然后按姓名对学生列表进行排序时，稳定的排序将确保具有相同年级的学生仍按姓名的字母顺序排列。

这种稳定性是基本插入排序算法的固有属性，不需要任何额外的修改或开销即可实现，使其成为一种天然稳定的排序方法。

时间和空间复杂度分析

插入排序的性能特点如下：

• 时间复杂度：

  • 最佳情况：O(n) - 当数组已排序时
  • 平均情况：O(n^2)
  • 最坏情况：O(n^2) - 当数组反向排序时

• 空间复杂度：O(1) - 插入排序是一种就地排序算法

Unlike Selection Sort, Insertion Sort can perform well on nearly sorted arrays, achieving close to linear time complexity in such cases.

Advantages and Disadvantages of Insertion Sort

Advantages:

• Simple to implement and understand
• Efficient for small to medium-sized datasets
• Adaptive - performs well on nearly sorted arrays
• Stable - maintains relative order of equal elements
• In-place sorting (O(1) space)
• Suitable for online sorting scenarios

Disadvantages:

• Inefficient for large datasets (O(n^2) in average and worst cases)
• Performance degrades quickly as input size increases

When to Use Insertion Sort

• Small to medium-sized datasets (generally up to a few hundred elements)
• Nearly sorted data
• Online sorting scenarios where elements are received and sorted incrementally
• As a subroutine in more complex algorithms (e.g., Quicksort for small partitions)

Practical Applications and Use Cases

1. Standard library implementations: Often used for small arrays or as part of hybrid sorting algorithms
2. Database operations: Sorting small sets of records
3. Embedded systems: Suitable for systems with limited resources due to its simplicity and low memory overhead
4. Real-time data processing: Maintaining sorted order as data is received

Conclusion

Insertion Sort, despite its limitations for large datasets, offers valuable advantages in specific scenarios. Its intuitive nature, resembling how we might sort cards by hand, makes it an excellent educational tool for understanding sorting algorithms.

Key takeaways:

• Best-case time complexity of O(n) for nearly sorted data
• Stable, in-place, and adaptive sorting algorithm
• Efficient for small datasets and online sorting
• Often incorporated into hybrid sorting strategies

While not suitable for large-scale sorting tasks, Insertion Sort's principles are often applied in more sophisticated methods. Its simplicity and efficiency in certain scenarios make it a valuable addition to a programmer's algorithmic toolkit.

The choice of sorting algorithm ultimately depends on your specific use case, data characteristics, and system constraints. Understanding Insertion Sort provides insights into algorithm design trade-offs and lays a foundation for exploring more advanced sorting techniques.

以上是使用 Javascript 进行算法之旅 - 插入排序的详细内容。更多信息请关注PHP中文网其他相关文章！