排序——二路归并排序

素颜马尾好姑娘i 2021-11-05 15:06 356阅读 0赞

> **算法思想：将无序序列拆分至只有一个关键字的子序列；然后两两归并，直至归并成一个序列**
> 
> **时间复杂度分析：共需进行log2n趟排序，每趟排序执行n次归并操作，因此时间复杂度为O(nlog2n)；时间复杂度与初始序列无关，平均和最好和最坏时间复杂度都是O(nlog2n)**
> 
> **空间复杂度：需要转存整个无序序列，空间复杂度为O(n)**

**代码：**

void Merge(int arr[],int left,int mid,int right)
    {
        int i,k;
        int left_min = left;
        int left_max = mid;
        int right_min = mid+1;
        int right_max = right;
        int *b = (int *)malloc((right-left+1)*sizeof(int));     //申请辅助空间，大小为两个子序列总的顶点数
        for(k=0;left_min<=left_max&&right_min<=right_max;k++)   //每次循环将两个子序列中值最小的保存到b空间中
        {
            if(arr[left_min]<arr[right_min])
                b[k] = arr[left_min++];
            else
                b[k] = arr[right_min++];
        }
        if(left_min<=left_max)      //如果right的长度小于left，比较结束left有剩余，将剩余节点插入到b空间中
        {
            for(i=left_min;i<=left_max;i++)
                b[k++] = arr[i];
        }
        if(right_min<=right_max)    //如果right的长度大于left，比较结束left有剩余，将剩余节点插入到b空间中
        {
            for(i=right_min;i<=right_max;i++)
                b[k++] = arr[i];
        }
        for(i=0;i<right-left+1;i++) //此时b空间是已经有序的两个子序列合并后的结果，将其复制到原数组对应的位置
            arr[left+i] = b[i];
        free(b);                    //释放节点空间
    }
    void Merge_sort(int arr[],int left,int right)
    {
        if(left<right)
        {
            int mid = (left+right)/2;
            Merge_sort(arr,left,mid);           //不断对左边序列进行拆分，直至每个子序列只有一个元素
            Merge_sort(arr,mid+1,right);        //不断对右边序列进行拆分，直至每个子序列只有一个元素
            Merge(arr,left,mid,right);          //合并子序列
        }
    }

## 完整代码： ##

#include <stdio.h>
    #include <stdlib.h>
    void Merge(int arr[],int left,int mid,int right)
    {
        int i,k;
        int left_min = left;
        int left_max = mid;
        int right_min = mid+1;
        int right_max = right;
        int *b = (int *)malloc((right-left+1)*sizeof(int));     //申请辅助空间，大小为两个子序列总的顶点数
        for(k=0;left_min<=left_max&&right_min<=right_max;k++)   //每次循环将两个子序列中值最小的保存到b空间中
        {
            if(arr[left_min]<arr[right_min])
                b[k] = arr[left_min++];
            else
                b[k] = arr[right_min++];
        }
        if(left_min<=left_max)      //如果right的长度小于left，比较结束left有剩余，将剩余节点插入到b空间中
        {
            for(i=left_min;i<=left_max;i++)
                b[k++] = arr[i];
        }
        if(right_min<=right_max)    //如果right的长度大于left，比较结束left有剩余，将剩余节点插入到b空间中
        {
            for(i=right_min;i<=right_max;i++)
                b[k++] = arr[i];
        }
        for(i=0;i<right-left+1;i++) //此时b空间是已经有序的两个子序列合并后的结果，将其复制到原数组对应的位置
            arr[left+i] = b[i];
        free(b);                    //释放节点空间
    }
    void Merge_sort(int arr[],int left,int right)
    {
        if(left<right)
        {
            int mid = (left+right)/2;
            Merge_sort(arr,left,mid);           //不断对左边序列进行拆分，直至每个子序列只有一个元素
            Merge_sort(arr,mid+1,right);        //不断对右边序列进行拆分，直至每个子序列只有一个元素
            Merge(arr,left,mid,right);          //合并子序列
        }
    }
    int main()
    {
        int i;
        int arr[] = {56,12,78,34,10,90,23,67,56,43};
        Merge_sort(arr,0,9);
        for(i=0;i<10;i++)
            printf("%d\t",arr[i]);
    }