【数据结构】归并排序、基数排序

1. 归并排序

1. 归并排序的定义

归并：把两个或多个已经有序的序列合并成一个。

两个称为二路归并。

多个称为m路归并。

“2路”归并—每选出一个小元素需要对比关键字1次。

对比i，j所指元素，选择更小的一个放入k所指位置。

m路归并，每选出一个元素需要对比关键字m-1次。

2. 手算模拟

核心操作：把数组内的两个有序序列归并为一个。

3. 算法实现

int *B=(int *)malloc(n*sizeof(int));  // 辅助数组B

// A[low,...,mid]和A[min+1,...,high]各自有序，将两部分归并
void Merge(int A[],int low,int mid,int high){
    int i,j,k;
    for(k=low;k<=high;k++){
        B[k]=A[k];  // 将A中所有元素复制到B中
    }
    for(i=low,j=mid+1,k=i;i<=mid && j<=high;k++){ // 归并
        if(B[i]<=B[j]){
            A[k]=B[i++];  // 将较小值复制到A中。两个元素相等时，优先使用靠前的那个（稳定性）
        }else{
            A[k]=B[j++];
        }
    }
    while(i<=mid){
        A[k++]=B[i++];
    }
    while(j<=high){
        A[k++]=B[j++];
    }
}

void MergeSort(int A[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;  // 从中间划分
        MergeSort(A,low,mid); // 对左半部分归并排序
        MergeSort(A,mid+1,high);  // 对右半部分归并排序
        Merge(A,low,mid,high);  // 归并
    }
}