文章目录

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实现

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;
}

验证

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实现

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)
}

验证

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]

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