Merge sort 合併排序法

Merge sort 合併排序法
Categories:
Tags:

複杂度

複杂度 Big O
最差时间複杂度 Worst-case time complexity Big O(n log n)
平均时间複杂度 Average-case time complexity Big theta (n log n)
最佳时间複杂度 Best-case time complexity Big omega (n log n)
空间複杂度 Space complexity Big O (n)

演算法

1. 建立储存最后排序结果阵列

会持续比较阵列数字的大小，然后将找到的最小数字储存在结果阵列

2. 比较两个最小的排序阵列

将数字阵列不断地切割，直到切割到剩下最后一个数字阵列，然后往上递迴比较

持续比较两个已排序阵列，然后比较两个排序阵列中最小的数字，加入到最后的排序结果阵列

3. 加入剩馀尚未比较阵列

两阵列比较完，避免其中一个阵列比完了，但另外一个阵列还有数字还没比完

因为两个都是已排序的阵列，所以剩馀阵列的数字一定是比已加入的数字大

所以就直接将剩馀数字的阵列数字，依序地加入到结果阵列中

4. 阵列往上递迴合併

比较好的新阵列，也会是排序好的阵列，往上回传后，持续和其他切割的阵列做比较

最后持续这个步骤，会得到一个完整排序后的阵列

Merge sort 合併排序法

程式

JavaScript

function merge(numberList1, numberList2) {
    // 最后比较结果阵列
    var finalOrderNumberList = [];
    // 阵列 1 比较数量
    var numberList1Counter = 0;
    // 阵列 2 比较数量
    var numberList2Counter = 0;
    // 比较两个数字阵列，直到其中一个阵列比较完毕
    while (numberList1Counter < numberList1.length && numberList2Counter < numberList2.length) {
        if (numberList1[numberList1Counter] < numberList2[numberList2Counter]) {
            // 「阵列 1 的数字」比「阵列 2 的数字」小，将「阵列 1 的数字」加到结果阵列
            finalOrderNumberList.push(numberList1[numberList1Counter]);
            // 阵列 1 继续比较下一个
            numberList1Counter++;
        }
        else {
            // 「阵列 2 的数字」比「阵列 1 的数字」小，将「阵列 2 的数字」加到结果阵列
            finalOrderNumberList.push(numberList2[numberList2Counter]);
            // 阵列 2 继续比较下一个
            numberList2Counter++;
        }
    }
    // 处理剩馀数字
    while (numberList1Counter < numberList1.length) {
        // 如果「阵列 1 的数字」还有剩，将所有阵列 1 数字加到结果阵列
        finalOrderNumberList.push(numberList1[numberList1Counter]);
        numberList1Counter++;
    }
    while (numberList2Counter < numberList2.length) {
        // 如果「阵列 2 的数字」还有剩，将所有阵列 2 数字加到结果阵列
        finalOrderNumberList.push(numberList2[numberList2Counter]);
        numberList2Counter++;
    }
    return finalOrderNumberList;
}
function mergeSort(sortNumberList) {
    if (sortNumberList.length <= 1) {
        // 如果只有 1 个数字，不用排序，直接回传
        return sortNumberList;
    }
    //  取得中间切割点
    var middlePointer = Math.floor(sortNumberList.length / 2);
    // 计算切割点左方排序
    var leftPartitionOrderNumberList = mergeSort(sortNumberList.slice(0, middlePointer));
    // 计算切割点右方排序
    var rightPartitionOrderNumberList = mergeSort(sortNumberList.slice(middlePointer));
    // 合併两个排序阵列
    return merge(leftPartitionOrderNumberList, rightPartitionOrderNumberList);
}
console.log(mergeSort([70, 50, 30, 10, 20, 40, 60]));

TypeScript

function merge(numberList1: number[], numberList2: number[]): number[] {
    // 最后比较结果阵列
    let finalOrderNumberList = [];
    // 阵列 1 比较数量
    let numberList1Counter = 0;
    // 阵列 2 比较数量
    let numberList2Counter = 0;

    // 比较两个数字阵列，直到其中一个阵列比较完毕
    while (numberList1Counter < numberList1.length && numberList2Counter < numberList2.length) {
        if (numberList1[numberList1Counter] < numberList2[numberList2Counter]) {
            // 「阵列 1 的数字」比「阵列 2 的数字」小，将「阵列 1 的数字」加到结果阵列
            finalOrderNumberList.push(numberList1[numberList1Counter]);
            // 阵列 1 继续比较下一个
            numberList1Counter++;
        } else {
            // 「阵列 2 的数字」比「阵列 1 的数字」小，将「阵列 2 的数字」加到结果阵列
            finalOrderNumberList.push(numberList2[numberList2Counter]);
            // 阵列 2 继续比较下一个
            numberList2Counter++;
        }
    }

    // 处理剩馀数字
    while (numberList1Counter < numberList1.length) {
        // 如果「阵列 1 的数字」还有剩，将所有阵列 1 数字加到结果阵列
        finalOrderNumberList.push(numberList1[numberList1Counter]);
        numberList1Counter++;
    }
    while (numberList2Counter < numberList2.length) {
        // 如果「阵列 2 的数字」还有剩，将所有阵列 2 数字加到结果阵列
        finalOrderNumberList.push(numberList2[numberList2Counter]);
        numberList2Counter++;
    }

    return finalOrderNumberList;
}

function mergeSort(sortNumberList: number[]): number[] {
    if (sortNumberList.length <= 1){
        // 如果只有 1 个数字，不用排序，直接回传
        return sortNumberList;
    }

    //  取得中间切割点
    let middlePointer = Math.floor(sortNumberList.length / 2);
    // 计算切割点左方排序
    let leftPartitionOrderNumberList = mergeSort(sortNumberList.slice(0, middlePointer));
    // 计算切割点右方排序
    let rightPartitionOrderNumberList = mergeSort(sortNumberList.slice(middlePointer));

    // 合併两个排序阵列
    return merge(leftPartitionOrderNumberList, rightPartitionOrderNumberList);
}

console.log(mergeSort([70, 50, 30, 10, 20, 40, 60]));

参考资料