数据结构归并排序（Merge Sort）详解附C++代码实现：-蒲公英云

数据结构归并排序（Merge Sort）详解附C++代码实现：

た入场券 2024-02-19 18:11 190阅读 0赞

简介：

算法描述：

代码实现：

总结：

简介：

归并排序是典型的递归思想的应用，将一个序列分为两个子序列，叫做二路归并，是一种稳定的排序算法，时间复杂度为：O(nlogn）

算法描述：

把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

代码实现：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
using namespace std;
#define num 10000
void mergearray(int a[],int first,int mid,int last,int t[])
{
    int i=first,j=mid+1;
    int n=mid,m=last;
    int k=0;
    while(i<=n&&j<=m)
    {
        if(a[i]<=a[j])
        t[k++]=a[i++];
        else
        t[k++]=a[j++];
    }
    while(i<=n)
    {
        t[k++]=a[i++];
    }
    while(j<=m)
    {
        t[k++]=a[j++];
    }
    for(i=0;i<k;i++)
    {
        a[first+i]=t[i];
    }
}
void mergesort(int a[],int first,int last,int t[])
{
    if(first<last)
    {
        int mid=(first+last)/2;
        mergesort(a,first,mid,t);
        mergesort(a,mid+1,last,t);
        mergearray(a,first,mid,last,t);
    }
}
int MergeSort(int a[],int len)
{
    int *temp=new int [len];
    if(temp==NULL)
    return 0;
    else
    mergesort(a,0,len-1,temp);
    delete []temp;
    return 1;
} 
int main()
{
    clock_t start,end;
    start=clock();
    freopen("out_arr.txt","r",stdin);
    freopen("out归并排序.txt","w",stdout);
    int arr[num];
    int n=num;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    MergeSort(arr,n);
    for(int i=0;i<n;i++)
    {
        printf("%5d ",arr[i]);
        if((i+1)%50==0)
        printf("\n");
    }
    end=clock();
    printf("归并排序耗时：%dms\n",(float)(end-start)*1000.0/CLOCKS_PER_SEC);
    return 0;
}