排序算法的详细介绍(七) -- 归并排序

常见排序算法归档介绍:

归并排序 Merge Sort

算法描述

把 n 个记录看成 n 个长度为 l 的有序子表.
进行两两归并使记录关键字有序,得到 n/2 个长度为 2 的有序子表.
重复第 2 步直到所有记录归并成一个长度为 n 的有序表为止.

merge_sort_animation

实例分析

数组: [6, 5, 3, 1, 8, 7, 2, 4], 排序过程:

将数组分为长度为 2 的子数组,并使每个子数组有序:
[6, 5]  [3, 1]  [8, 7]  [2, 4]
   ↓       ↓       ↓       ↓
[5, 6]  [1, 3]  [7, 8]  [2, 4]

然后再两两合并:
[6, 5, 3, 1]  [8, 7, 2, 4]
      ↓             ↓
[1, 3, 5, 6]  [2, 4, 7, 8]

最后将两个子数组合并:
[6, 5, 3, 1, 8, 7, 2, 4]
            ↓
[1, 2, 3, 4, 5, 6, 7, 8]

merge_sort_example

代码实现

function mergeSort(array) {
    function sort(array, first, last) {
        first = (first === undefined) ? 0 : first
        last = (last === undefined) ? array.length - 1 : last
        if (last - first < 1) {
            return;
        }
        var middle = Math.floor((first + last) / 2);
        sort(array, first, middle);
        sort(array, middle + 1, last);
        var f = first,
            m = middle,
            i,
            temp;
        while (f <= m && m + 1 <= last) {
            if (array[f] >= array[m + 1]) { // 这里使用了插入排序的思想
                temp = array[m + 1];
                for (i = m; i >= f; i--) {
                    array[i + 1] = array[i];
                }
                array[f] = temp;
                m++
            } else {
                f++
            }
        }
        return array;
    }
    return sort(array);
}

此文参考于 bubkoo.com,十分感谢.
所有引用内容版权归原作者所有.
使用知识共享“署名-非商业性使用-相同方式共享 3.0 中国大陆”许可协议授权.

常见排序算法归档介绍:

归并排序 Merge Sort

算法描述

实例分析

代码实现

CATALOG

FEATURED TAGS