归并排序思想

归并排序时间复杂度分析

归并排序特点

归并排序实现

递归

#include <iostream>
using namespace std;
void merge(int *arr,int *temp,int left,int mid,int right) {
    int p=left,q=mid+1,index=0;
    while(p<=mid&&q<=right) {
        if(arr[p]<arr[q])temp[index++]=arr[p++];
        else temp[index++]=arr[q++];
    }
    while(p<=mid)temp[index++]=arr[p++];
    while(q<=right)temp[index++]=arr[q++];
    memcpy(arr+left, temp, sizeof(int)*(right-left+1));
}
void msort(int *arr,int *temp,int left, int right) {
    if(left>=right)return;
    int mid = left+((right-left)>>1);
    msort(arr,temp,left,mid);
    msort(arr,temp,mid+1,right);
    merge(arr,temp,left,mid,right);
}
void merge_sort(int arr[],int len) {
    int *temp=(int *)malloc(sizeof(int)*len);
    if(temp!=NULL) {
        msort(arr,temp,0,len-1);
        free(temp);
    }
}
int main(int argc,char *argv[]) {
    int arr[]= {1,6,4,7,2,5,3,9,8,0};
    merge_sort(arr,sizeof(arr)/sizeof(int));
    for(int i=0;i<10;i++)printf("%d ",arr[i]);
    return 0;
}

非递归

#include <iostream>
using namespace std;
void merge(int *arr,int *temp,int left,int mid,int right) {
    int p=left,q=mid+1,index=left;
    while(p<=mid&&q<=right) {
        if(arr[p]<arr[q])temp[index++]=arr[p++];
        else temp[index++]=arr[q++];
    }
    while(p<=mid)temp[index++]=arr[p++];
    while(q<=right)temp[index++]=arr[q++];
}
void msort(int *arr,int *temp,int n,int len) {
    int i;
    for(i=0; i<=n-2*len; i+=2*len)
        merge(arr,temp,i,i+len-1,i+2*len-1);
    if(i+len<n) //剩余两段未排序
        merge(arr,temp,i,i+len-1,n-1);
    else { // 剩余一段未排序
        for(int j=i; j<n; j++)
            temp[j]=arr[j];
    }
}
void merge_sort(int arr[],int n) {
    int *temp=(int *)malloc(sizeof(int)*n);
    int len =1;
    if(temp!=NULL) {
        while(len<n) {
            msort(arr,temp,n,len); //将排序结果保存在temp数组中 
            len*=2;
            msort(temp,arr,n,len); //将排序结果保存在arr数组中（如果len>n,只做了从temp到arr的元素拷贝） 
            len*=2;
        }
        free(temp);
    }
}
int main(int argc,char *argv[]) {
    int arr[]= {1,17,6,4,7,2,12,5,3,9,8,19,0,10,15,11,14,13,18,16};
    merge_sort(arr,sizeof(arr)/sizeof(int));
    for(int i=0; i<10; i++)printf("%d ",arr[i]);
    return 0;
}