归并排序
二路归并排序
归并过程
归并排序.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))
稳定
