迭代的并归排序#

算法思维#

并归的含义是将两个或两个以上的有序序列合并成一个新的有序序列
并归排序的时间复杂度为 $n \log n$ ，需要申请与待排序序列相等的辅助空间，是一种稳定的排序方法

算法设计#

将初始待并归序列长度设为 1
将两个相邻的未并归的子序列并归成一个新的有序序列
循环执行2直到所有子序列并归成一个有序序列

算法实现#

1
// 迭代并归排序
2
/*
3
mode: 非0：升序， 0：降序
4
*/
5
void sort_mergeSort_noRecursion(int *arr, int len, int mode)
6
{
7
    int *arr_point = arr;
8
    int *arr_tmp = (int *)malloc(sizeof(int) * len), *tmp;
9
    int s_1,e_1,s_2,e_2, arr_tmp_index;
10
    int span = 1;
11

12
    while(span < len)
13
    {
14
        arr_tmp_index = 0;
15
        for(int i = 0; i < len; i += 2*span)
16
        {
17
            // 两个相邻序列的开始和结束索引
18
            s_1 = utils_min(i, len);
19
            e_1 = utils_min(s_1+span, len);
20
            s_2 = utils_min(e_1, len);
21
            e_2 = utils_min(s_2+span, len);
22

23
            // 将两个序列按顺序并入新序列
24
            while(s_1 < e_1 && s_2 < e_2)
25
                arr_tmp[arr_tmp_index++] = sort_judgeWithMode(arr[s_1], arr[s_2], mode)? arr[s_1++] : arr[s_2++];
26

27
            // 当其中一个序列全部并入，剩下的一个序列直接按顺序并入
28
            while(s_1 < e_1) arr_tmp[arr_tmp_index++] = arr[s_1++];
29
            while(s_2 < e_2) arr_tmp[arr_tmp_index++] = arr[s_2++];
30

31
        }
32

33
        // 交换两个数组的指针方便运算
34
        tmp = arr_tmp;
35
        arr_tmp = arr;
36
        arr = tmp;
37

38
        // 并归序列长度翻倍
39
        span *= 2;
40
    }
41

42
    // 如果当前arr的地址不是原来的地址，将有序序列赋给原来地址的数组
43
    if(arr != arr_point)
44
    {
45
        for(int i = 0; i < len; i ++)
46
        {
47
            arr_point[i] = arr[i];
48
        }
49
    }
50
}

运算结果#

测试代码

1
#define N 7
2

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

7
    printf("升序排列结果:\n");
8
    utils_print_arr(arr, N, "%2d ");
9
    printf("\n");
10
    sort_mergeSort_noRecursion(arr, N, 1);
11

12
    printf("\n\n降序排列结果:\n");
13
    utils_print_arr(arr, N, "%2d ");
14
    printf("\n");
15
    sort_mergeSort_noRecursion(arr, N, 0);
16

17
    return 0;
18
}

运算结果

原文链接：CSDN