排序算法之归并排序

发表于

排序算法之归并排序及其优化

归并排序介绍

归并排序是创建在归并操作上的一种有效的排序算法，效率为O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

自顶向下

不说废话了，开工。
待排数组如下：

插入排序初始数组

第一步

我们首先将这 8 个元素，一层一层的分割，如：

  • 第一层两组：[8 , 6, 2 , 3],[ 1, 5, 7, 4]
  • 第二层四组：[8, 6], [2, 3], [1, 5], [7, 4]
  • 第三层八组：[8], [6], [2], [3], [1], [5], [7], [4]

如下图:

归并排序01

第二步 归并操作(Merge)

从底层开始两两归并（当然也可以三三进行归并），归并之后是有序的。

第三层八组，进行两两归并：

归并排序02

第二层四组，进行两两归并：

归并排序03

第一层两组，进行两两归并：

归并排序04

此时，数组已经排序完成！

第三步 分析程序

很明显，上面的是自顶向下，采用的是分治法，我们采用递归的方法，来实现这个算法：

1
2
3
void mergeSort(int arr[],int n) {
    __mergeSort(arr, 0, n-1);
}

开始分割：

1
2
3
4
5
6
7
8
9
10
11
12
13
void __mergeSort(int arr[],int l,int r) {
    
    int mid = l + (r - l)/2;
    
    if (l >= r) {
        return;
    }
    
    __mergeSort(arr, l, mid);
    __mergeSort(arr, mid + 1, r);
    
    _merge(arr, l, mid, r);
}

注意：这里取中间的 mid 有个问题，大多数人都会写成这样：

1
int mid = (l + r)/2;

这样写不严谨，当l和r 都很大时，(l + r) 会溢出。

先不断的分割[l,mid],然后[mid+1,r]

最后归并：

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
26
void _merge(int arr[],int l, int mid,int r) {
    int count = r-l+1;
    int ta[count];
    
    for (int i = l; i <= r; i++) {
        int a = i - l;
        ta[a] = arr[i];
    }
    
    int i = l,j = mid + 1;
    for (int k = l; k <= r; k++) {
        if (i > mid) {
            arr[k] = ta[j - l];
            j ++;
        } else if (j > r) {
            arr[k] = ta[i - l];
            i ++ ;
        } else if (ta[i - l] < ta[j - l]) {
            arr[k] = ta[i-l];
            i ++;
        } else {
            arr[k] = ta[j - l];
            j ++;
        }
    }
}

这里创建了一个临时的数组长度为 (r - l) + 1 .

注意：如果数据量很大，可能会造成栈溢出，这是归并排序的一个缺点。

咱们来分析一下归并排序的最后一步：

归并排序05

先排除边界：

  • 当 i > mid 时，说明[l,mid]区间已经结束，所以 [mid+1,r] 直接赋值就行了;
  • 当 j > r 时，说明[mid+1,r]区间已经结束，所以 [l,mid] 直接赋值就行了;

开始比较：

第一次比较

i -> 2，j -> 1; 2 > 1,将 1 放进去：

归并排序06

第二次比较

此时数组的状态及各个变量的指向：

归并排序07

i -> 2，j -> 4; 2 < 4,将 2 放进去：

归并排序08

第三次比较

此时数组的状态及各个变量的指向：

归并排序09

i -> 3，j -> 4; 3 < 4,将 3 放进去：

归并排序11

第四次比较

此时数组的状态及各个变量的指向：

归并排序10

i -> 6，j -> 4; 6 > 4,将 4 放进去：

归并排序12

后面的就不一一解释了，按照这个思路，请继续往下画…

我相信前面的程序，现在是非常清晰了。

自低向上

其实自低向上很好理解，就是第一步被分割后，开始向上归并，只不过不是使用递归的解法，而是迭代法。

我这里把程序贴出来，大家跟着程序把图画一下，就理解了。

1
2
3
4
5
6
7
8
void mergeSortBackUp(int arr[],int n) {
    
    for (int size = 1; size <= n; size += size ) {
        for (int i = 0; i + size < n; i += (size + size)) {
            _merge(arr, i, i + size - 1, MIN(i + size + size - 1,n-1));
        }
    }
}

注意：这里的_merge 函数 用的是上一步的！

测试

这里用了 1千万一个数据测试，测试结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
**************有序*************
sortname:归并排序 　　	 sorttime: 3.218722s
sortname:归并排序2　　	 sorttime: 2.599350s

**************近乎有序*************
sortname:归并排序 　　	 sorttime: 3.078164s
sortname:归并排序2　　	 sorttime: 2.605246s

**************随机*************
sortname:归并排序 　　	 sorttime: 4.810648s
sortname:归并排序2　　	 sorttime: 4.118894s

**************倒叙*************
sortname:归并排序 　　	 sorttime: 3.054663s
sortname:归并排序2　　	 sorttime: 2.569524s

最后附上Demo