JavaScript插入排序算法原理与实现方法示例

算法原理

插入排序是一种简单直观的排序算法，其基本原理是将一个待排序的数组依次插入一个有序的数组中，使得最终生成的有序数组是全局有序的。每次将一个待排序的元素插入到有序数组中时，我们从有序数组的末尾开始比较，如果待排序的元素比当前比较的元素小，则交换位置，继续比较，否则插入到当前位置。

实现方法

下面是JavaScript中插入排序的实现方法：

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

该算法采用了循环嵌套的方式，外层循环控制待排序的元素，内层循环控制有序数组。在每一次内层循环中，我们将待排序的元素与有序数组中的元素依次比较，找到能够插入的位置，然后将其插入到对应的位置。

示例说明

示例一

let arr = [3, 1, 5, 4, 2];
console.log(insertionSort(arr));
// 输出：[1, 2, 3, 4, 5]

在该实例中，我们定义了一个数组arr，并对其进行插入排序。最终输出的结果是一个有序数组[1, 2, 3, 4, 5]，证明了插入排序的正确性。

示例二

let arr = [10, 8, 4, 9, 7, 12, 2];
console.log(insertionSort(arr));
// 输出：[2, 4, 7, 8, 9, 10, 12]

在该实例中，我们定义了一个数组arr，并对其进行插入排序。最终输出的结果是一个有序数组[2, 4, 7, 8, 9, 10, 12]，证明了插入排序的普适性。