C语言实现归并排序：递归与非递归方法详解

C语言实现归并排序：递归与非递归方法详解

引用

CSDN

1.

https://m.blog.csdn.net/EWIAW_ilove/article/details/135365089

归并排序是一种基于分治法的高效排序算法，通过将数组不断分割成更小的子数组，然后将这些子数组合并成有序数组。本文将详细介绍归并排序的递归和非递归实现方式，包括算法思想、代码实现以及性能分析。

一.排序思想

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

二.写代码流程及思路

绝大部分排序都可以分为单趟排序和多趟排序，当我们要写排序时，可以先写单趟排序，再写多趟排序，这样使得我们写代码简单易懂。

三.单趟归并排序

单趟归并排序的思想是：分别取左右两个有序数组，并把它们合并起来形成新的有序数组。
如下图所示。

1.单趟归并排序代码实现

//数组参数为：待排数组，临时数组，[left,mid] 和 [mid+1,right]区间
void MergeArr(int* arr, int* tmp, int left, int mid, int right)
{
    int begin1 = left;//左区间起始位置
    int end1 = mid;//左区间终止位置
    int begin2 = mid + 1;//右区间起始位置
    int end2 = right;//右区间终止位置
    int i = begin1;//用于给临时数组的下标，即把arr数组中的数放入tmp数组的下标位置
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (arr[begin1] < arr[begin2])
        {
            tmp[i] = arr[begin1];
            i++;
            begin1++;
        }
        else
        {
            tmp[i] = arr[begin2];
            i++;
            begin2++;
        }
    }
    while (begin1 <= end1)//将剩余的数放入tmp中
    {
        tmp[i] = arr[begin1];
        i++;
        begin1++;
    }
    while (begin2 <= end2)//将剩余的数放入tmp中
    {
        tmp[i] = arr[begin2];
        i++;
        begin2++;
    }
    //将tmp数组拷回去arr中
    for (int i = left; i <= right; i++)
    {
        arr[i] = tmp[i];
    }
}  

2.多趟归并排序代码实现

完成单趟排序后，接下来要做的是进行多趟归并排序，归并排序需要将一个数组区间不断二分，直到一个小区间中只有一个元素后，开始返回进行合并。

//数组参数为：待排数组，临时数组，待排数组的起始位置，待排数组的终止位置
void MergePartSort(int* arr, int*tmp, int begin, int end)//归并排序分区间和归并
{
    if (begin >= end)
    {
        return;
    }
    //分区间
    int mid = (begin + end) / 2;
    MergePartSort(arr, tmp, begin, mid);
    MergePartSort(arr, tmp, mid + 1, end);
    //归并
    MergeArr(arr, tmp, begin, mid, end);
}
void MergeSort(int* arr, int begin, int end)//归并排序
{
    //创建临时数组
    int* tmp = (int*)malloc(sizeof(int) * (end - begin + 1));
    if (tmp == NULL)
    {
        printf("malloc false\n");
        exit(-1);
    }
    MergePartSort(arr, tmp, begin, end);
    free(tmp);
}  

四.非递归实现

归并排序的给递归实现思想是：第一次先，一个一个数的合并，第二次，两个两个数合并，第三次，四个四个数合并，第四次，八个八个数合并，以此类推。直到一次性合并的数大于数组元素总个数即可。

1.归并排序非递归代码实现

void MergeSortNonR(int* arr, int begin, int end)//归并排序非递归实现
{
    int* tmp = (int*)malloc(sizeof(int) * (end - begin + 1));//开辟临时数组tmp
    if (tmp == NULL)
    {
        printf("malloc false\n");
        exit(-1);
    }
    int gap = 1;//默认先合并一个
    while (gap < (end - begin + 1))
    {
        for (int i = 0; i <= end; i = i + 2 * gap)
        {
            int left = i;
            int right = i + 2 * gap - 1;
            int mid = (right + left) / 2;
            if (right > end)//如果有区间越界，则右区间给到end（末尾）
            {
                right = end;
            }
            MergeArr(arr, tmp, left, mid, right);
        }
        gap = gap * 2;
    }
}  

五.时间复杂度和空间复杂度

归并排序的时间复杂度为：O（n*logN）
空间复杂度为：O（n）

六.稳定性分析

什么是稳定性？
稳定性是，如果一组数里面有两个相同的数，则排序完成后，如果不会改变他们的相对顺序，则这个排序算法是稳定的，否则是不稳定的。

结论

归并排序时稳定的。

七.所有源代码

#include<stdio.h>
#include<stdlib.h>
void Print(int* arr, int sz)
{
    for (int i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
//单趟归并排序
void MergeArr(int* arr, int* tmp, int left, int mid, int right)
{
    int begin1 = left;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = right;
    int i = begin1;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (arr[begin1] < arr[begin2])
        {
            tmp[i] = arr[begin1];
            i++;
            begin1++;
        }
        else
        {
            tmp[i] = arr[begin2];
            i++;
            begin2++;
        }
    }
    while (begin1 <= end1)
    {
        tmp[i] = arr[begin1];
        i++;
        begin1++;
    }
    while (begin2 <= end2)
    {
        tmp[i] = arr[begin2];
        i++;
        begin2++;
    }
    for (int i = left; i <= right; i++)
    {
        arr[i] = tmp[i];
    }
}
void MergePartSort(int* arr, int*tmp, int begin, int end)//归并排序分区间和归并
{
    if (begin >= end)
    {
        return;
    }
    //分区间
    int mid = (begin + end) / 2;
    MergePartSort(arr, tmp, begin, mid);
    MergePartSort(arr, tmp, mid + 1, end);
    //归并
    MergeArr(arr, tmp, begin, mid, end);
}
void MergeSort(int* arr, int begin, int end)//归并排序
{
    int* tmp = (int*)malloc(sizeof(int) * (end - begin + 1));
    if (tmp == NULL)
    {
        printf("malloc false\n");
        exit(-1);
    }
    MergePartSort(arr, tmp, begin, end);
    free(tmp);
}
void MergeSortNonR(int* arr, int begin, int end)//归并排序非递归实现
{
    int* tmp = (int*)malloc(sizeof(int) * (end - begin + 1));
    if (tmp == NULL)
    {
        printf("malloc false\n");
        exit(-1);
    }
    int gap = 1;
    while (gap < (end - begin + 1))
    {
        for (int i = 0; i <= end; i = i + 2 * gap)
        {
            int left = i;
            int right = i + 2 * gap - 1;
            int mid = (right + left) / 2;
            if (right > end)
            {
                right = end;
            }
            MergeArr(arr, tmp, left, mid, right);
        }
        gap = gap * 2;
    }
}
int main()
{
    int arr1[] = { 1,5,2,10,3,4,8,9,5,3,1,5 };
    int arr2[] = { 1,5,2,10,3,4,8,9,5,3,1,5 };
    Print(arr1, sizeof(arr1) / sizeof(int));
    MergeSort(arr1, 0, sizeof(arr1) / sizeof(int) - 1);
    Print(arr1, sizeof(arr1) / sizeof(int));
    Print(arr2, sizeof(arr2) / sizeof(int));
    MergeSortNonR(arr2, 0, sizeof(arr2) / sizeof(int) - 1);
    Print(arr2, sizeof(arr2) / sizeof(int));
    return 0;
}