JS插入排序简单理解与实现方法分析

描述

插入排序是一种比较简单的排序方法，它的核心思想是将待排序的元素，依次插入到已经排好序的部分，从而逐渐将整个序列排好。具有较好的稳定性和适用性。

实现思路

插入排序的实现思路:

1. 将第一个元素当做已经排序好的序列
2. 从第二个元素开始遍历整个数组
3. 回溯已经排序好的序列，将当前元素插入到比它大的元素之前
4. 重复2、3步骤直到排序完成

代码实现

下面是JavaScript实现插入排序的示例代码：

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

示例解析

为了更好地理解插入排序的实现方法，我们将使用以下两个示例来帮助我们分析。

示例1:

给定数组 [3, 1, 6, 2, 9, 10] ，使用插入排序算法进行排序。

首先将数组下标为0的元素3视为已排序的序列，从下标为1的元素1开始遍历数组, 当前元素为1，需要将1插入到已排序的序列中。

1. 将1与已排序的序列中最后一个元素(3)比较，如果1小于3，则将1插入到（3前面的位置）。

   [3, 1, 6, 2, 9, 10]
// 1 < 3
[1, 3, 6, 2, 9, 10]

2. 继续遍历数组，当前元素为6，需要将6插入到已排序的序列中。

   [1, 3, 6, 2, 9, 10]
// 6 > 3
[1, 3, 6, 2, 9, 10]

3. 继续遍历数组，当前元素为2，需要将2插入到已排序的序列中。

   [1, 3, 6, 2, 9, 10]
// 2 < 6
[1, 3, 2, 6, 9, 10]
// 2 < 3
[1, 2, 3, 6, 9, 10]

4. 继续遍历数组，当前元素为9，需要将9插入到已排序的序列中。

   [1, 2, 3, 6, 9, 10]
// 9 > 6
[1, 2, 3, 6, 9, 10]

   当前元素为10，需要将10插入到已排序的序列中。

   [1, 2, 3, 6, 9, 10]
// 10 > 9
[1, 2, 3, 6, 9, 10]

最终排序结果为[1, 2, 3, 6, 9, 10]。

示例2:

给定数组 [-2, 45, 0, 11, -9] ，使用插入排序算法进行排序。

首先将数组下标为0的元素-2视为已排序的序列，从下标为1的元素45开始遍历数组, 当前元素为45，需要将45插入到已排序的序列中。

1. 将45与已排序的序列中最后一个元素(-2)比较，如果45大于-2，则将45插入到-2后的位置。

   [-2, 45, 0, 11, -9]
// 45 > -2
[-2, 45, 0, 11, -9]

2. 继续遍历数组，当前元素为0，需要将0插入到已排序的序列中。

   [-2, 45, 0, 11, -9]
// 0 > -2
[-2, 0, 45, 11, -9]

3. 继续遍历数组，当前元素为11，需要将11插入到已排序的序列中。

   [-2, 0, 45, 11, -9]
// 11 > 0
[-2, 0, 11, 45, -9]
// 11 < 45
[-2, 0, 11, 45, -9]

4. 继续遍历数组，当前元素为-9，需要将-9插入到已排序的序列中。

   [-2, 0, 11, 45, -9]
// -9 < 0
[-2, -9, 0, 11, 45]

最终排序结果为[-2, -9, 0, 11, 45]。