归并排序

归并排序

思想

分治思想

将一个大问题分解为k个小问题再进行简单的解决。

具体思想

将一个数组,分解为两个各自有序的子数组,再将两个有序子数组合并为一个有序的数组。当两个子数组中都只有一个元素时,他们显然各自有序。所以将数组不断向下分解直到子数组只有一个元素是开始递归地进行合并即可保证每次合并的两个子数组各自有序。

归并排序图示

基本信息

1.时间复杂度:O(n*log2(n))
2.特点: 稳定的排序方法
3.空间与时间: 排序速度仅次于'快速排序',但空间占用较高.

具体实现

1
#include<stdio.h>
2
#define MAX 65535
3
#define Array_num 20
4
5
 void merge(int A[],int start, int mid, int end)
6
 {
7
     /*
8
        start是在数组A中需要合并的两个子数组的起始位置
9
        mid是两个子数组在A中的分界位置
10
        end是两个子数组在A中的终结位置
11
    */
12
     int n = end - start + 1;   //n为待合并的两个子数组中元素的总个数
13
     int i = 0;
14
     int j = 0;
15
     int L[Array_num];
16
     int R[Array_num];
17
     for(int m = 0; m < Array_num; m++)L[m] = MAX;
18
     for(int m = 0; m < Array_num; m++)R[m] = MAX;
19
     for(int m = 0; m <= mid - start; m++)L[m] = A[start + m];
20
     for(int m = 0; m <= end - mid - 1; m++)R[m] = A[mid + m + 1];
21
     for(int counter = 0; counter < n; counter++)//n个元素的合并需要n次操作
22
    {
23
        if(L[i] < R[j])
24
        {
25
            A[start + counter] = L[i];
26
            i++;
27
        }
28
        else
29
        {
30
            A[start + counter] = R[j];
31
            j++;
32
        }
33
    }
34
 }
35
 
36
 void merge_sort(int A[],int start, int end)
37
 {
38
     if(start < end)//start = end 时开始返回递归
39
     {
40
         int p = (end + start)/2;
41
         merge_sort(A, start, p);
42
         merge_sort(A, p+1, end);
43
         merge(A, start, p, end);
44
     }
45
 }
46
 int main()
47
 {
48
     //正确排序:[1,3,4,5,5,5,6,7,23,46,67,123,123,222,342,421,645,934]共18个数
49
     int A[] = {5,5,7,6,1,4,3,23,123,222,123,342,421,934,645,67,46,5};
50
     int length = sizeof(A)/4;
51
     merge_sort(A,0,length-1);
52
     for(int i = 0; i < length; i++)printf("%d\t",A[i]);//输出结果
53
     return 0;
54
 }

此处不给出循环不变式地证明

碎碎念

周更blog还行2333