js 插入排序|极客笔记

js 插入排序

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对未排序的数据依次进行比较，并插入到已排序序列中的适当位置。插入排序在实践中比较高效，因为它的内部循环可以提前终止。

算法步骤

插入排序的算法步骤如下：
1. 从第一个元素开始，认为该元素是已经排序好的。
2. 取出下一个元素，在已经排序的序列中从后向前扫描。
3. 如果该元素大于新元素，将该元素移到下一位置。
4. 重复步骤3，直到找到小于或等于新元素的位置。
5. 将新元素插入到该位置后。
6. 重复步骤2~5，直到所有元素都被排序。

示例代码

以下是使用JavaScript编写的插入排序算法：

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let current = arr[i];
    let j = i - 1;

    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }

    arr[j + 1] = current;
  }

  return arr;
}

// 测试
const array = [9, 2, 5, 6, 4, 3, 7, 10, 1, 8];
console.log(insertionSort(array)); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

在上面的示例代码中，我们定义了一个insertionSort函数来实现插入排序。我们首先从数组的第二个元素开始遍历，然后将当前元素与已排序的子数组依次比较并插入到正确的位置。