递归的归并排序#

算法思维#

利用递归的特性，先将当前序列的子序列并归，再并归当前序列

算法设计#

递归结束条件，当前序列的长度为1
并归前一个子序列
归并后一个子序列
对当前序列进行并归

算法实现#

1
// 递归归并排序算法
2
void sort_mergeSort(int* arr, int len, int mode)
3
{
4
    int* arr_tmp = (int* )malloc(sizeof(int) * len);
5
    sort_mergeSort_main(arr, arr_tmp, 0, len-1, mode);
6
}
7

8
// 递归并归的执行函数
9
void sort_mergeSort_main(int* arr, int* arr_tmp, int s, int e, int mode)
10
{
11

12
    if(s == e) // 如果只有一个元素，直接赋值
13
    {
14
        arr_tmp[s] = arr[s];
15
    }
16
    else
17
    {
18
        int m = (s+e)/2;
19
        // 先并归前后两个子序列
20
        sort_mergeSort_main(arr, arr_tmp, s, m, mode);
21
        sort_mergeSort_main(arr, arr_tmp, m+1, e, mode);
22

23
        // 将两个子序列进行并归
24
        int s_1 = s, e_1 = m+1, s_2 = m+1, e_2 = e+1;
25
        int k = s;
26

27
        while(s_1 < e_1 && s_2 < e_2)
28
        {
29
            arr[k++] = sort_judgeWithMode(arr_tmp[s_1], arr_tmp[s_2], mode)? arr_tmp[s_1++]: arr_tmp[s_2++];
30
        }
31
        while(s_1 < e_1) arr[k++] = arr_tmp[s_1++];
32
        while(s_2 < e_2) arr[k++] = arr_tmp[s_2++];
33

34
        // 将并归好的序列赋给原地址
35
        for(int i = s; i <= e; i ++)
36
        {
37
            arr_tmp[i] = arr[i];
38
        }
39

40
    }
41
}

运算结果#

测试代码

1
#define N 7
2

3
int main()
4
{
5
    int arr[N] = {49,38,65,97,76,13,27};
6

7
    sort_mergeSort(arr, N, 1);
8
    utils_print_arr(arr,0, N-1, "%2d ","升序排列结果:\n", "\n\n");
9

10
    sort_mergeSort(arr, N, 0);
11
    utils_print_arr(arr,0, N-1, "%2d ", "降序排列结果:\n", "\n");
12

13
    return 0;
14
}

运算结果

原文链接：CSDN