By 被删

更新日期:

文章目录
  1. 1. 归并排序
    1. 1.1. 排序问题
    2. 1.2. 思路
    3. 1.3. js实现
    4. 1.4. 验证

归并排序的javascript实现。

归并排序

排序问题

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

思路

假设桌面上有两堆扑克牌，每堆都已排序，最小的牌在上，把这两堆牌合并成单一的排好序的输出堆。

对总输入堆进行处理：

  1. 将扑克牌分成两堆，每堆重复步骤1~3排序
  2. 在牌面朝上的两堆牌的顶上两张牌中选取最小的一张，放置到输出堆
  3. 重复步骤2，直到一个输入堆为空
  4. 将两堆扑克牌重复2~3，合成输出堆

js实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function mergeSort(iArr) {
    var n = iArr.length;
    // 若小于两位数，则按顺序排列后返回
    if (n === 2 && iArr[0] > iArr[1]) { return [iArr[1], iArr[0]]; }
    else if(n <= 2) { return iArr; }
    // 若大于两位数，则分成两组，递归处理
    else{
        var p = parseInt(n/2);
        var iArr1 = mergeSort(iArr.slice(0,p));
        var iArr2 = mergeSort(iArr.slice(p));
        var oArr = [];
        for(var i = 0; i< n; i++){
            if(iArr1.length && iArr2.length){
                // 比较最前两个数，取出较小的
                oArr.push(iArr1[0] <= iArr2[0] ? iArr1.splice(0, 1)[0] : iArr2.splice(0, 1)[0]);
            }else{
                // 若其中一组为空，则将另一组剩下的添加到输出尾部
                oArr = oArr.concat(iArr1.length === 0 ? iArr2 : iArr1);
                break;
            }
        }
        return oArr;
    }
}

验证

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

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

insertionSort([5, 2, 12, 2, 134, 1, 3, 34, 4, 6, 1, 3, 4]); 
// 输出[1, 1, 2, 2, 3, 3, 4, 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. 验证