C语言归并排序递归与非递归模板

这个我是拿来理解和背诵的，选自于胡凡的《算法笔记》。归并排序是一种nlogn的时间复杂度算法，不断地利用空间倒腾去完成，一般也用在排序算法上。

递归版本

将array数组当前区间[left,right]进行归并排序
void mergeSort(int A[],int left,int right) {
    if(left<right) {
        int mid = (left+right)/2;
        mergeSort(A,left,mid);
        mergeSort(A,mid+1,right);
        merge(A,left,mid,mid+1,right);

    }

}
void merge(int A[],int L1,int R1,int L2,int R2){
    int i = L1,j = L2;//i指向A[L1],j指向A[l2]
    int temp[maxn],index = 0;//temp临时存放合并后的数组，index为其下标
    while(i<=R1&& j<=R2){
        if(A[i] <= A[j]){ //如果A[i] <= A[j]
            temp[index++] = A[i++]; //将A[i] 加入序列temp
        }else{ //如果A[i] > A[j]
            temp[index++] = A[j++]; //将A[j] 加入序列temp
        }
    }
    while(i<=R1) temp[index++] = A[i++];
    while(j<=R2) temp[index++] = A[j++];
    for(i=0;i<index;i++){
        A[L1+i] = temp[i];//将合并后的序列赋值回数组A

    }
}



int main()
{
    int A[5] ={3,2,1,5,0};
    mergeSort(A,sizeof(A)/sizeof(int));
    for(int i =0;i<5;i++)
        printf("%d ",A[i]);
    return 0;
}

非递归版本

void merge(int A[],int L1,int R1,int L2,int R2){
    int i = L1,j = L2;//i指向A[L1],j指向A[l2]
    int temp[maxn],index = 0;//temp临时存放合并后的数组，index为其下标
    while(i<=R1&& j<=R2){
        if(A[i] <= A[j]){ //如果A[i] <= A[j]
            temp[index++] = A[i++]; //将A[i] 加入序列temp
        }else{ //如果A[i] > A[j]
            temp[index++] = A[j++]; //将A[j] 加入序列temp
        }
    }
    while(i<=R1) temp[index++] = A[i++];
    while(j<=R2) temp[index++] = A[j++];
    for(i=0;i<index;i++){
        A[L1+i] = temp[i];//将合并后的序列赋值回数组A

    }
}


void mergeSort(int A[],int n){
    //step为组内元素个数,step/2为左子区间元素个数，注意等号可以不取
    for(int step =2;step/2<n;step*=2){
        //每step个元素一组，组内前step/2和后step/2个元素进行合并
        for(int i=0;i<=n;i+=step){
            int mid = i + step /2-1;
            if(mid+1<=n) {
                //左子区间为[i,mid],右子区间[mid+1,min(i+step-1),n];
                merge(A,i,mid,mid+1,min(i+step-1,n));
            }
        }
    }

}

下面给出题目中只要求给出归并排序每一趟结束时的序列，那么完全可以使用merge函数。

void mergeSort(int A[], int n){
    //step为组内元素个数，step/2为左子区间元素个数，注意等号可以不取
    for(int step = 2;step/2 <= n;step*=2){
        //每step一个元素一组，组内[i,min(i+step,n+1)]进行排序
        for(int i=0;i<=n;i+=step) {
            sort(A+i,A+min(i+step,n+1));
        }
    }
}