归并排序————数据结构课程

归并排序是一个稳定的排序算法

核心思路为：不断地将两个有序序列合并为一个更长的有序序列

现将长度为1的相邻子序列合并，然后长度为2的，长度为4的，直到整个序列被合并。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<malloc.h>
using namespace std;
#define RecType int
void disp(int R[],int n) {
    for(int i=1; i<=n; i++)
        printf("%d ",R[i]);
    printf("\n");
}
void Merge(RecType R[],int low,int mid,int high) {//对给定的相邻两段序列进行归并
    RecType *R1;
    int i=low,j=mid+1,k=0;
    //k是R1的下标,i、j分别为第1、2段的下标
    R1=(RecType *)malloc((high-low+1)*sizeof(RecType));//临时储存排好的序列
    while (i<=mid && j<=high)//从两个系列中,找较小的元素放入暂存系列中
        if (R[i]<=R[j]) {    //将第1段中的记录放入R1中
            R1[k]=R[i];
            i++;
            k++;
        } else {    //将第2段中的记录放入R1中
            R1[k]=R[j];
            j++;
            k++;
        }
    while (i<=mid) {      //将第1段余下部分复制到R1
        R1[k]=R[i];
        i++;
        k++;
    }
    while (j<=high) {    //将第2段余下部分复制到R1
        R1[k]=R[j];
        j++;
        k++;
    }
    for (k=0,i=low; i<=high; k++,i++) //将R1复制回R中
        R[i]=R1[k];
    free(R1);
    return ; 
}

void MergeSort(RecType R[],int n) {//不断的将相邻子序列,两两合并  
    int length;
    for (length=1; length<n; length=2*length) {
        int i;
        for (i=1; i+2*length-1<=n; i=i+2*length) //归并length长的两相邻子表
            Merge(R,i,i+length-1,i+2*length);
        if (i+length-1<n)               //余下两个子表,后者长度小于length
            Merge(R,i,i+length-1,n);  //归并这两个子表
    }
    return ;
}
int main() {
    RecType R[]={9,1,4,3,5,0,2,6,8,7};
    int n=9;
    disp(R,n);
    MergeSort(R,n);
    disp(R,n);
    return 0;
}