归并排序

归并操作

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

如 设有数列{6，202，100，301，38，8，1}

初始状态:6,202,100,301,38,8,1

第一次归并后:{6,202},{100,301},{8,38},{1}，比较次数:3;

第二次归并后:{6,100,202,301}，{1,8,38}，比较次数:4;

第三次归并后:{1,6,8,38,100,202,301},比较次数:4;

总的比较次数为:3+4+4=11;

图片演示

代码实现：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void merge (int *a,int low,int mid, int high);
 
void merge_sort (int *a,int low,int high);

int main (){
    int a[]={2,6,4,8,12,56,88,65,14,22};
    int high = sizeof(a)/sizeof(a[0]);
    printf("排序前\n");
    for (int i=0;i<high;i++){
        printf("%d\t",a[i]);
    }
    printf("\n");
    merge_sort(a,0,high-1);
    printf("排序后\n");
    for (int i=0;i<high;i++){
        printf("%d\t",a[i]);
    }
    system("pause");
    return 0;

}


void merge (int *a,int low ,int mid ,int high){
    
    int i = low;
    int j = mid + 1;
    int *copya = (int *)malloc((high-low+1)*sizeof(int));
    int p = 0;
    while ( i<=mid && j<=high){
        if ( a[i]>a[j]){
            copya[p++] = a[j++];          
        }else{
            copya[p++] = a[i++];      
        }
        
    }
    // 
    while (i<=mid){
        copya[p++] = a[i++];
    }
    while (j<=high){
        copya[p++] = a[j++];
    }
    
    for (int k = 0;k<high-low+1;k++){
        a[k+low] = copya[k];
    }
    
    //memcpy(a + low, copya + low, sizeof(int)*(high - low+1));
    //
    free(copya);
    return;
}

void merge_sort (int *a,int low,int high){
    if (low < high ){
        int mid = (low+high)/2;
        merge_sort(a,low,mid);
        merge_sort(a,mid+1,high);
        merge(a,low,mid,high);
        /*
        for (int i=low;i<high+1;i++){
            printf("%d\t",a[i]);
        }
        printf("\n");
        */
    }
    

}
我遇到的问题

在归并，把copya的值赋回给a的时候最开始：

1
2
3
for (int k = 0;k<high-low+1;k++){
        a[k] = copya[k];
    }

仅仅是对应的赋值，那么其实就会造成当low=2，high=3时，a[2]的值会把a[0]的值给覆盖掉导致a[2]之后就没有值了.

看了csdn发现了错误.

时间复杂度

归并的递归易得出O（nlogn）

空间复杂度

因为申请了一个n大小的动态内存，那么空间复杂度为O（n）.