归并排序

二路归并排序
归并过程

归并排序.JPG
辅助数组B，把A都赋值进去，然后每次分别从B的两段中按顺序取出两个元素，将小的那个输出（放到A里）（就相当于每次在找当前最小值嘛）然后被输出的那段就往后取，重复这个过程知道有一段被取完了，把还没取完的那段剩下的部分整个放到A里。

ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType));
void Merge(ElemType A[], int low, int mid, int high)
{
    for(int k=low;k<=high;++k)
        B[k]=A[k];
    for(i=low, j=mid+1, k=i;i<mid&&j<=high;++k){
        if(B[i]<=B[j])
            A[k]=B[i++];  //先赋值再加一
        else
            A[k]=B[j++];
    }
    while(i<=mid) A[k++]=B[i++];
    while(j<=high) A[k++]=B[j++];
}

O(n)
整个归并排序需要⌈log2n⌉趟（k路归并需要⌈logkn⌉）

void MergeSort(ElemType 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);
    }
}

空间效率O(n)
时间效率O(nlog2n)
稳定

---

基数排序

不基于比较进行排序，采用多关键字排序思想（基于关键字各位的大小进行排序）
分为最高位优先MSD排序和最低位优先LSD排序
以r为基数的LSD排序的过程
线性表由节点序列a0, a1, ..., an-1构成
每个节点aj的关键字由d元组（kj(d-1), kj(d-1), ..., kj(1), kj(0)）组成，其中0<=kj(i)<=r-1（就是aj在r进制下的各个位上的值吧）
使用r个队列Q0, Q1,...,Qn-1
对i=0,1,...,d-1一次做一次分配和收集
分配
开始时，把Q0, Q1,...,Qn-1各个队列置为空队列，然后一次考察线性表中的每个节点aj，若aj的关键字kj(i)=k，就把aj放入队列Qk
收集
把Q0, Q1,...,Qn-1各个队列中的结点首尾相接，得到新的节点序列，从而组成新的线性表

基数排序.JPG
空间效率O(r)
时间效率O(d(n+r))
稳定