归并排序 基数排序 算法讲解
需积分: 0 38 浏览量
2010-06-23
13:29:36
上传
评论
收藏 103KB DOC 举报
第六章 排序
1．理解归并排序的算法思想及其算法设计。
2．理解基数排序方法及其性能分析方法。
重点：
归并排序、基数排序方法及其性能分析。
难点：
归并排序、基数排序方法及其性能分析。
内容
6.2.4 归并排序
归并排序（Merging sort）是与插入排序、交换排序、选择排序不同的另一类排序方法。
归并的含义是将两个或两个以上的有序表组合成一个新的有序表。归并排序可分为多路归并排
序，两路归并排序，既可用于内排序，也可以用于外排序。这里仅对内排序的两路归并方法进
行讨论。
两路归并排序算法思路：假设初始序列含有 n 个记录，首先把 n 个记录看成 n 个长度为 1
的有序序列，进行两两归并，得到[n/2]个长度为 2 的关键字有序序列，再两两归并直到所有
记录归并成一个长度为 n 的有序序列为止。
void Mergesort(RcdType r[ ],int n)
{
l=1;
while(l<n)
{
Mergepass(r,r2,l,n);
l=l*2;
Mergepass(r2,r,l,n);
l=l*2;
}
}
void Mergepass(RcdType r[ ],RcdType r2[MAXSIZE],int l,int n){
归并排序、基数排序
评论0