使用 JavaScript 实现插入排序以按升序对数字数组进行排序

介绍

插入排序是一种简单的排序算法，它的基本思想是将待排序元素按照其大小关系依次插入到已排序的元素序列中。插入排序的时间复杂度为 O(n^2)，但是它的实际表现优于其他时间复杂度相同的排序算法，因为它在大多数情况下都只需要简单地交换相邻的元素，所以它的常数因子比较小。

算法流程

下面是插入排序的算法流程：

将第一个元素看作是已排序的元素序列。

从第二个元素开始，依次将每个元素插入到已排序的元素序列中，直到所有元素都被插入。

插入一个元素时，将它与已排序的元素序列从后往前依次比较，将大于它的元素向右移动一个位置，直到找到它的插入位置，然后将它插入到该位置。

JavaScript 实现插入排序

下面是使用 JavaScript 实现插入排序以按升序对数字数组进行排序的代码：

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

在这个代码中，我们遍历数组中的所有元素（从第一个元素开始），对于每个元素，我们都将它与已排序的元素序列从后往前依次比较，将大于它的元素向右移动一个位置，直到找到它的插入位置，然后将它插入到该位置。

这个算法的时间复杂度为 O(n^2)，因为它需要比较和移动的元素数量随着数组长度的增加而增加。

测试代码

下面是使用上面实现的插入排序算法对一个数字数组进行排序的代码：

let arr = [5, 2, 9, 3, 1, 6, 8, 7, 4];
console.log(insertionSort(arr)); // Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

在这个测试代码中，我们首先创建了一个包含 9 个数字的数组，然后使用上面实现的插入排序算法对它进行排序，并输出排序后的结果。

总结

在这篇文章中，我们介绍了插入排序算法的基本思想和流程，并使用 JavaScript 实现了一个简单的插入排序算法。我们还通过测试代码验证了这个算法的正确性。

虽然插入排序的时间复杂度比其他一些排序算法高，但是它的实际表现要比其他时间复杂度相同的排序算法好，因为它的常数因子比较小，所以大多数情况下都只需要简单地交换相邻的元素。如果您需要对一个较小的数字数组进行排序，插入排序是一个不错的选择。