数据结构 归并排序.ppt

归并排序
归并排序( Merging sort是与插入排序、交换排序、
选择排序不同的另一类排序方法。
归并的含义是将两个或两个以上的有序表组合成一个
新的有序表。归并排序可分为2-路归并排序、多路归并
排序,既可用于内排序,也可用于外排序。这里以2路
归并排序为例。
2-路归并排序算法
(1)算法思路:
假设初始序列含有n个记录,首先把n个记录看成n
个长度为1的有序序列,进行两两归并,得到[/2]个长
度为2的关键字有序序列,再两两归并直到所有记录归
并成一个长度为n的有序序列为止。
例1设有n个记录n=8)的关键字是(46,55,33,12
54,17,15,80),试用归并排序方法将这组记录由
小到大进行排序。其排序过程如图所示,
初始[46][55][33][12][54][17][15][80]L=1
第1趟[4655][1233][1754][1580]L=2
第2趟[12834655][15175480]L=4
第3趟[1215173346545580]L=n
归并排序核心算法
void Merge(RedType SR[, RedType TRO, int i, int m,
int n)
/*将有序的SR[m]和SR[m+1n归并为有序的TR[in]*
int j, k;
for(j=m+1,k=i;ik=m&&j<=n;++k){/将SR中记录由
小到大地并入TR
if LQ(SR[]key, SRO].key) TR[k]= SR[++
else TR[k]= SR[++]; 1
(i<=m)/TRkn]=SRm];将剩余的SRm复制到TR
while(k<=n &&k<=m) TRk++]=SR[i++
f(j<=n)鬥将剩余的SR[n复制到TR
while(k<=n &&j<=) TRk++=SR[++
/ Merge*/
一趟归并算法
void MSort(Red Type SR[, RedType TR1[, int s, int
t){
/将SR[s订归并排序为TRs.]。
int m;
RedType TR2[20]
if (s==)TR1[t]= Sr[s]
else
m=(s+t)/2
/*将SR[[sm和SR[m+
MSor(SR,TR2s,m);/递归地将SRsm归并为有序TR2sm
MSort(SR,TR2,m+1,t);将SR[m+1归并为有序TR2m+1y
Merge(TR2,TR1,s,m);/将TR2m和TR2[m+1.,归并到
TR1[st
/ Msort*/
主体框架算法
void Merge Sort(sqList &L)i
/对顺序表L作归并排序。*
MSort(Lr, Lr, 1, L length);
}鬥 Merge Sort*.
(2)算法分析:
主体算法调用 Merge约[og2n]趟。每趟处理考虑两
两子序列归并,其运算数量级为o(n)。所以归并排序
的时间复杂度为o( nlog2n)。该算法需占用与待排序记
录相等的辅助向量空间。与快速排序和堆排序相比,归
并排序是一种稳定的排序方法,其它没有什么优越。所
以在一般情况下,不利用2-路归并排序法进行内部排序
基数排序
基数排序( radix sol是与已介绍的各类排序方法完
全不同的一种排序方法。前面所介绍的排序方法主要是
通过比较记录的关键字大小和移动记录来实现的,而基
数排序法不必经过关键字的比较来实现排序,而是根据
关键字每个位上的有效数字的值,借助于“分配”和
“收集”两种操作来实现排序。
基数排序分类
基数排序有两种最高位优先法和最低位优先法
最高位优先法( Most Significant Digit first,简称
MSD),即是首先根据最高位有效数字进行排序,然后根
据次高位有效数字进行排序,依次类推,直到根据最低
位(个位)有效数字进行排序,产生一个有序序列。
最低位优先法( Least significant Digit first,简称
LSD法),即是首先根据关键字最低位(个位)有效数字进
行排序,然后根据次低位(十位)有效数字进排序,依此
类推,直到根据最高位有效数字进行排序,产生一个有
序序列。