归并排序（MergeSort）递归&非递归实现详解

创作时间:

作者:

@小白创作中心

归并排序（MergeSort）递归&非递归实现详解

引用

CSDN

https://m.blog.csdn.net/blkblizzard/article/details/139473721

归并排序（Merge Sort）是一种基于分治策略的排序算法，其历史可以追溯到1945年，由美国计算机科学家约翰·冯·诺伊曼（John von Neumann）在二战期间首次提出。归并排序的基本思想是将一个大的问题分解成多个小问题，然后分别解决这些小问题，最后再将结果合并。具体来说，归并排序将数组递归地分成两半，直到每个子数组只有一个元素为止，然后将这些子数组逐步合并成一个有序的数组。这个过程包括两个主要步骤：分割（Divide）和合并（Merge）。

代码实现

递归实现

在实现归并排序的过程中我们需要创建一个临时数组（tmp），用来存放单次排序后形成的新的有序数组。注意：我们将前后两部分的递归放在前面，也就是说我们先将数组分成单个元素后再进行排序，这个逻辑大家需要理清。最后的两个while循环就是将还剩下数据的部分拷贝到临时数组中。最后用memcpy将临时数组拷贝到原数组的对应位置（容易出错）记得引用头文件<string.h>在C++中引用

//递归主体
void _MergeSort(int* a, int begin, int end, int* tmp){
    if (begin >= end)
        return;
    int mid = (begin + end) / 2;
    // [begin, mid][mid+1, end]
    _MergeSort(a, begin, mid, tmp);
    _MergeSort(a, mid + 1, end, tmp);
    // [begin, mid][mid+1, end]归并
    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;
    int i = begin;
    while (begin1 <= end1 && begin2 <= end2){
        if (a[begin1] < a[begin2]){
            tmp[i++] = a[begin1++];
        }
        else{
            tmp[i++] = a[begin2++];
        }
    }
    while (begin1 <= end1){        //判断左右两边虽没有走完，将剩下的插入到后面，因为左右两边早已有序。
        tmp[i++] = a[begin1++];
    }
    while (begin2 <= end2){
        tmp[i++] = a[begin2++];
    }
    memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}  

//归并排序
void MergeSort(int* a, int n) {
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL) {
        perror("malloc fail");
        return;
    }
    _MergeSort(a, 0, n - 1, tmp);
    free(tmp);
}

非递归实现

非递归的归并排序设计的核心就是设置一个gap，随着我们排序范围的增大，gap也是double增长，实现逻辑与递归形式大同小异。

void MergeSortNonR(int* a, int n){
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL){
        perror("malloc fail");
        return;
    }
    int gap = 1;
    while (gap < n){
        printf("gap:%2d->", gap);
        for (size_t i = 0; i < n; i += 2 * gap){
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;
            // [begin1, end1][begin2, end2] 归并
            //printf("[%2d,%2d][%2d, %2d] ", begin1, end1, begin2, end2);
            // 边界的处理
            if (end1 >= n || begin2 >= n){
                break;
            }
            if (end2 >= n){
                end2 = n - 1;//自适应
            }
            //printf("[%2d,%2d][%2d, %2d] ", begin1, end1, begin2, end2);
            int j = begin1;       //开始归并
            while (begin1 <= end1 && begin2 <= end2){
                if (a[begin1] < a[begin2]){
                    tmp[j++] = a[begin1++];
                }
                else{
                    tmp[j++] = a[begin2++];
                }
            }
            while (begin1 <= end1){
                tmp[j++] = a[begin1++];
            }
            while (begin2 <= end2){
                tmp[j++] = a[begin2++];
            }
            memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));    //每一次归并都拷贝回去
        }
        printf("\n");
        gap *= 2;
    }
    free(tmp);
}