各种排序方法的综合比较
1. 平均的时间性能
时间复杂度为 O(nlogn)： 快速排序、堆排序和归并排序
时间复杂度为 O(n2)： 直接插入排序、起泡排序和 简单选择排序
时间复杂度为 O(n): 基数排序
2.简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
void Merge (RcdType SR[], RcdType &TR[], int i, int m, int n)
{ // 将有序的记录序列 SR[i..m] 和 SR[m+1..n] // 归并为有序的记录序列 TR[i..n]
for (k=i,j=m+1; i<=m && j<=n; ++k)
{ // 将SR中记录由小到大地并入TR
if (SR[i].key<=SR[j].key)
TR[k] = SR[i++];
else TR[k] = SR[j++];
}
if (i<=m) TR[k..n] = SR[i..m]; // 将剩余的 SR[i..m] 复制到 TR
if (j<=n) TR[k..n] = SR[j..n]; // 将剩余的 SR[j..n] 复制到 TR
}