一、归并排序
算法思想:
将两个或两个以上的有序表组合成一个新的有序表。采用分治思想！
二路排序：
思路排序：
模拟实现：
算法实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| int *B = (int *)malloc((n+1)*sizeof(int));
void merge(int A[],int low,int mid,int high){
for(int k = low;k<=high;k++){
B[k] = A[k]; //将k中所有元素复制到B
}
int i,j;
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++];
}
void sort(int A[],int low,int high){
if(low<high){
int mid = (low+high)/2;
sort(A,low,mid);
sort(A,mid+1,high);
merge(A,low,mid,high);
}
}
|
算法评估：
空间效率：$O(n)$
时间效率：
稳定性：是
二、基数排序
算法思想:
不基于比较和移动进行排序，而是基于关键字各位的大小进行排序。
模拟实现：
1.初始化数字
2.第一趟，对个位进行划分
3.对第一趟进行收集，重新转换成链表
4.以十位进行划分
5.重新转换成链表
6.以百位作为关键字进行划分
7.重新收集
8.汇总如下，最终排序结果
算法评估：
空间效率：$O(r)$ (辅助存储空间为r，r个队列)
时间效率：
- $O(d(n+r))$ (d趟分配和收集，一趟分配要O(n),一趟收集需要O(r))
稳定性：是
