By 被删

更新日期:

文章目录
  1. 1. 插入排序
    1. 1.1. 排序问题
    2. 1.2. 思路
    3. 1.3. js实现
    4. 1.4. 验证
  2. 2. 单数组插入排序
    1. 2.1. 思路
    2. 2.2. js实现
    3. 2.3. 验证

插入排序的javascript实现。

插入排序

排序问题

  • 输入：n个数的一个序列<a1, a2, ..., an>
  • 输出：输入序列的一个排列<a1', a2', ..., an'>，满足a1' <= a2' <= ... <= an'

思路

插入排序的工作方式像许多人排序一手扑克牌：

  1. 左手为空，桌子上牌面向下
  2. 每次从桌子上拿走一张牌插入左手中正确的位置
  3. 为了找到正确位置，从右到左将它与已经在手中的每张牌进行比较，然后插入
  4. 重复步骤2~3

js实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function insertionSort(iArr) {
    var oArr = [iArr[0]];
    var n = iArr.length;
    // 从左边开始，每次拿一个与已排列好的数组进行比较
    for (var i = 1; i < n; i++) {
        for (var j = 0; j < i; j++) {
            if (iArr[i] <= oArr[j]) {
                // 若介于小于该元素，则插入其前方
                oArr.splice(j, 0, iArr[i]);
                break;
            } else if (j === i - 1) {
                // 若比最后一个还大，则排在最右侧
                oArr.push(iArr[i]);
            }
        }
    }
    return oArr;
}

验证

1
2
3
4
5
insertionSort([5, 2, 4, 6, 1, 3]); 
// 输出[1, 2, 3, 4, 5, 6]

insertionSort[5, 2, 12, 2, 134, 1, 3, 34, 4, 6, 1, 3]); 
// 输出[1, 1, 2, 2, 3, 3, 4, 5, 6, 12, 34, 134]

单数组插入排序

思路

这里在一个数组中进行插入排序：

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素（已排序）小于新元素，将新元素插入该元素下一位置
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置，将新元素插入到该位置后
  5. 若无，则将新元素插入最左侧
  6. 重复步骤2~5

js实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function insertionSort(iArr) {
    var n = iArr.length;
    // 从第一个元素开始，该元素可以认为已经被排序
    for (var i = 1; i < n; i++) {
        // 取出下一个元素，在已经排序的元素序列中从后向前扫描
        for (var j = i - 1; j >= 0; j--) {
            if (iArr[i] >= iArr[j]) {
                // 如果该元素（已排序）小于新元素，将新元素插入该元素下一位置
                iArr.splice(j + 1, 0, iArr.splice(i, 1)[0]);
                break;
            } else if (j === 0) {
                // 如果已是最小元素，则插入最左侧
                iArr.splice(j, 0, iArr.splice(i, 1)[0]);
            }
        }
    }
    return (iArr)
}

验证

1
2
3
4
5
insertionSort([5, 2, 4, 6, 1, 3]); 
// 输出[1, 2, 3, 4, 5, 6]

insertionSort[5, 2, 12, 2, 134, 1, 3, 34, 4, 6, 1, 3]); 
// 输出[1, 1, 2, 2, 3, 3, 4, 5, 6, 12, 34, 134]

码生艰难，写文不易，给我家猪囤点猫粮了喵~

B站: 被删

查看Github有更多内容噢：https://github.com/godbasin
更欢迎来被删的前端游乐场边撸猫边学前端噢

如果你想要关注日常生活中的我，欢迎关注“牧羊的猪”公众号噢

作者：被删

出处：https://godbasin.github.io

本文版权归作者所有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

文章目录
  1. 1. 插入排序
    1. 1.1. 排序问题
    2. 1.2. 思路
    3. 1.3. js实现
    4. 1.4. 验证
  2. 2. 单数组插入排序
    1. 2.1. 思路
    2. 2.2. js实现
    3. 2.3. 验证