C语言实现归并排序

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
75
#include "sort_.h"

void print_array(int *arr, int n)
// 打印数组
{
    if(n==0){
        printf("ERROR: Array length is ZEROn");
        return;
    }
    printf("%d", arr[0]);
    for (int i=1; i<n; i++) {
        printf(" %d", arr[i]);
    }
    printf("n");
}

int* merge_array(int *arr1, int n1, int* arr2, int n2)
//  编程实现两个有序数组arr1和arr2合并
//  函数参数：有序数组arr1 数组arr1长度 有序数组arr2 数组arr2长度
//  函数返回值：返回从小到大排序后的合并数组
{
 
 int* res;
    res = new int[n1 + n2];
    int a1 = 0, a2 = 0;
    int index = 0;

    for (int i = 0; i < n1+n2; i++) {
        if (i < n1) {
            res[i] = arr1[i];
        }
        else {
            res[i] = arr2[i - n1];
        }
    }

    sort(res, res + n1 + n2);

    return res;
    
    /********** End **********/
}
int* merge_sort(int *arr, int n)
//  基于merge_array函数编程实现归并排序：自上而下的递归方法
//  函数参数：有序数组arr 数组arr长度
//  函数返回值：返回从小到大排序后的数组
{


    int mid = n / 2;
    if (mid > 0) {
        int* arr1 = new int[mid];
        int n1 = mid;
        int n2 = n - mid;
        int* arr2 = new int[n2];
        for (int i = 0; i < n; i++) {
            if (i < mid) {
                arr1[i] = arr[i];
            }
            else {
                arr2[i - mid] = arr[i];
            }
        }

        merge_sort(arr1, n1);   
        merge_sort(arr2, n - mid);     
        merge_array(arr1, n1, arr2, n2);
    }
    else
    {
        return  merge_array(arr, n, NULL, 0);
    }

}