排序算法:归并排序

icy2003 程序 2020-05-18 12:29:41 933 0条

归并排序(Merge Sort)是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用

5.gif

算法评价

  • 平均时间复杂度:O(nlogn)
  • 最好情况:O(nlogn)
  • 最坏情况:O(nlogn)
  • 空间复杂度:O(n)
  • 稳定性:稳定

算法思想

  1. 把长度为 n 的输入序列分成两个长度为 n/2 的子序列。
  2. 对这两个子序列分别采用归并排序。
  3. 将两个排序好的子序列合并成一个最终的排序序列。

实例分析

以数组 array = [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-300px.gif

代码示例

Javascript

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);
}
标签: 算法

非特殊说明,本博所有文章均为博主原创。