数据结构课件：10.内部排序.ppt

1、第九章第九章一、排序一、排序( (Sorting)Sorting)2第一节排序第一节排序n排序排序：将一个数据元素（或记录）的任意序列，：将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列重新排列成一个按关键字有序的序列n内部排序内部排序：在排序期间数据对象全部存放在内：在排序期间数据对象全部存放在内存的排序；存的排序；n外部排序外部排序：在排序期间全部对象个数太多，不：在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。不断在内、外存之间移动的排序。第第9章内部排序章内部排序二、排序

2、基本操作二、排序基本操作3第一节排序第一节排序排序的基本操作包括：n比较：比较两个关键字的大小比较：比较两个关键字的大小n移动：将记录从一个位置移动至另一个位置移动：将记录从一个位置移动至另一个位置第第9章内部排序章内部排序三、排序时间复杂度三、排序时间复杂度4第一节排序第一节排序n排序的时间复杂度可用算法执行中的记录关键排序的时间复杂度可用算法执行中的记录关键字比较次数与记录移动次数来衡量。字比较次数与记录移动次数来衡量。第第9章内部排序章内部排序四、排序方法的稳定性四、排序方法的稳定性5第一节排序第一节排序n如果在记录序列中有两个记录如果在记录序列中有两个记录riri和和rj, rj, 它

3、它们的关键字们的关键字 keyi = keyj , keyi = keyj , 且在排序之且在排序之前前, , 记录记录riri排在排在rjrj前面。前面。n如果在排序之后如果在排序之后, , 记录记录riri仍在记录仍在记录rjrj的前的前面面, , 则称这个排序方法是稳定的则称这个排序方法是稳定的, , n否则称这个排序方法是不稳定的。否则称这个排序方法是不稳定的。第第9章内部排序章内部排序6第二节插入排序第二节插入排序n每步将一个待排序的对象每步将一个待排序的对象, , 按其关键字大小按其关键字大小, , 插入到前面已经排好序的有序表的适当位置上插入到前面已经排好序的有序表的适当位置上,

4、 , 直到对象全部插入为止。直到对象全部插入为止。第第9章内部排序章内部排序一、直接插入排序一、直接插入排序7第二节插入排序第二节插入排序n当插入第当插入第i(i1)i(i1)个对象时个对象时, , 前面的前面的r0, r0, r1, r1, , ri-1, ri-1已经排好序。已经排好序。n用用riri的关键字与的关键字与ri-1, ri-2, ri-1, ri-2, 的关键的关键字顺序进行比较字顺序进行比较( (和顺序查找类似和顺序查找类似) )，如果小于，如果小于，则将则将rxrx向后移动向后移动( (插入位置后的记录向后顺插入位置后的记录向后顺移移) )n找到插入位置即将找到插入位置即

5、将riri插入插入第第9章内部排序章内部排序一、直接插入排序一、直接插入排序( (举例举例) )8第二节插入排序第二节插入排序n已知待序的一组记录的初始排列为：已知待序的一组记录的初始排列为：21, 25, 21, 25, 49, 2549, 25* *, 16, 08, 16, 08第第9章内部排序章内部排序0 1 2 3 4 5一、直接插入排序一、直接插入排序( (举例举例) )9第二节插入排序第二节插入排序第第9章内部排序章内部排序0 1 2 3 4 5 temp2525250 1 2 3 4 5 temp494949一、直接插入排序一、直接插入排序( (举例举例) )10第二节插入排序

6、第二节插入排序第第9章内部排序章内部排序252525* * *0 1 2 3 4 50 1 2 3 4 5 temp161616一、直接插入排序一、直接插入排序( (举例举例) )11第二节插入排序第二节插入排序第第9章内部排序章内部排序0 1 2 3 4 5 temp0808080 1 2 3 4 5完成一、直接插入排序一、直接插入排序( (算法实现算法实现) )12第二节插入排序第二节插入排序void InsertSort (int r , int m ) void InsertSort (int r , int m ) / / 假设关键字为整型，放在向量假设关键字为整型，放在向量rr中中

7、 int n, j, temp; int n, j, temp; for ( n = 1; n m; n+ ) for ( n = 1; n 0; j- ) / for ( j = n; j 0; j- ) /从后向前顺序比较，并依次后移从后向前顺序比较，并依次后移 if ( temp rj-1 ) rj = rj-1;if ( temp rj-1 ) rj = rj-1; else break; else break; rj = temp; rj = temp; 第第9章内部排序章内部排序一、直接插入排序一、直接插入排序( (算法分析算法分析) )13第二节插入排序第二节插入排序n关键字比较

8、次数和记录移动次数与记录关键字关键字比较次数和记录移动次数与记录关键字的初始排列有关。的初始排列有关。n最好情况下最好情况下, , 排序前记录已按关键字从小到大排序前记录已按关键字从小到大有序有序, , 每趟只需与前面有序记录序列的最后一每趟只需与前面有序记录序列的最后一个记录比较个记录比较1 1次次, , 移动移动2 2次记录次记录, , 总的关键字比总的关键字比较次数为较次数为 n-1, n-1, 记录移动次数为记录移动次数为 2( 2(n-1)n-1)。第第9章内部排序章内部排序一、直接插入排序一、直接插入排序( (算法分析算法分析) )14第二节插入排序第二节插入排序n最坏情况下最坏情

9、况下, , 第第i i趟时第趟时第i i个记录必须与前面个记录必须与前面i i个记录都做关键字比较个记录都做关键字比较, , 并且每做并且每做1 1次比较就次比较就要做要做1 1次数据移动。则总关键字比较次数次数据移动。则总关键字比较次数KCNKCN和和记录移动次数记录移动次数RMNRMN分别为分别为第第9章内部排序章内部排序111122142221nininnniRMNnnniKCN/)()( ,/)(22一、直接插入排序一、直接插入排序( (算法分析算法分析) )15第二节插入排序第二节插入排序n在平均情况下的关键字比较次数和记录移动次在平均情况下的关键字比较次数和记录移动次数约为数约为

10、n n2 2/4/4。n直接插入排序的时间复杂度为直接插入排序的时间复杂度为O(nO(n2 2) )。n直接插入排序是一种稳定的排序方法直接插入排序是一种稳定的排序方法n直接插入排序最大的优点是简单，在记录数较直接插入排序最大的优点是简单，在记录数较少时，是比较好的办法少时，是比较好的办法第第9章内部排序章内部排序二、折半插入排序二、折半插入排序16第二节插入排序第二节插入排序n折半插入排序在查找记录插入位置时，采用折折半插入排序在查找记录插入位置时，采用折半查找算法半查找算法n折半查找比顺序查找快折半查找比顺序查找快, , 所以折半插入排序在所以折半插入排序在查找上性能比直接插入排序好查找上

11、性能比直接插入排序好n但需要移动的记录数目与直接插入排序相同但需要移动的记录数目与直接插入排序相同( (为为O(nO(n2 2)n折半插入排序的时间复杂度为折半插入排序的时间复杂度为O(nO(n2 2) )。n折半插入排序是一种稳定的排序方法折半插入排序是一种稳定的排序方法第第9章内部排序章内部排序三、希尔排序三、希尔排序17第二节插入排序第二节插入排序n从直接插入排序可以看出，当待排序列为正序从直接插入排序可以看出，当待排序列为正序时，时间复杂度为时，时间复杂度为O(n)O(n)n若待排序列基本有序时，插入排序效率会提高若待排序列基本有序时，插入排序效率会提高n希尔排序方法是先将待排序列分成

12、若干子序列希尔排序方法是先将待排序列分成若干子序列分别进行插入排序，待整个序列基本有序时，分别进行插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序再对全体记录进行一次直接插入排序n希尔排序又称为缩小增量排序。希尔排序又称为缩小增量排序。第第9章内部排序章内部排序三、希尔排序三、希尔排序( (算法算法) )18第二节插入排序第二节插入排序n首先取一个整数首先取一个整数 gap n(gap 1; i- - ) for ( i = m; i 1; i- - ) for ( j = 1; j m; j+ ) for ( j = 1; j rj+1 )if ( rj rj+1 ) rj

13、rj+1; rj rj+1; 第第9章内部排序章内部排序一、起泡排序一、起泡排序27第三节快速排序第三节快速排序第第9章内部排序章内部排序初始关键字第一趟排序第四趟排序第二趟排序第三趟排序第五趟排序一、起泡排序一、起泡排序( (性能分析性能分析) )28第三节快速排序第三节快速排序n最好情况：在记录的初始排列已经按关键字从最好情况：在记录的初始排列已经按关键字从小到大排好序时小到大排好序时, ,此算法只执行一趟起泡此算法只执行一趟起泡, ,做做n-n-1 1次关键字比较次关键字比较, ,不移动记录不移动记录第第9章内部排序章内部排序一、起泡排序一、起泡排序( (性能分析性能分析) )29第三节

14、快速排序第三节快速排序n最坏情况：执行最坏情况：执行n-1n-1趟起泡趟起泡, ,第第i i趟做趟做n-in-i次关键次关键字比较字比较, , 执行执行n-in-i次记录交换，共计：次记录交换，共计：n起泡排序的时间复杂度为起泡排序的时间复杂度为O(nO(n2 2) )n起泡排序是一种稳定的排序方法起泡排序是一种稳定的排序方法第第9章内部排序章内部排序11111233121nininninRMNnninKCN)()()()(二、快速排序二、快速排序30第三节快速排序第三节快速排序n任取待排序记录序列中的某个记录任取待排序记录序列中的某个记录( (例如取第例如取第一个记录一个记录) )作为基准作

15、为基准( (枢枢),),按照该记录的关键字按照该记录的关键字大小大小, ,将整个记录序列划分为左右两个子序列：将整个记录序列划分为左右两个子序列： n左侧子序列中所有记录的关键字都小于或等于左侧子序列中所有记录的关键字都小于或等于基准记录的关键字基准记录的关键字 n右侧子序列中所有记录的关键字都大于基准记右侧子序列中所有记录的关键字都大于基准记录的关键字录的关键字第第9章内部排序章内部排序二、快速排序二、快速排序31第三节快速排序第三节快速排序n基准记录则排在这两个子序列中间基准记录则排在这两个子序列中间( (这也是该这也是该记录最终应安放的位置记录最终应安放的位置) )。n然后分别对这两个子

16、序列重复施行上述方法，然后分别对这两个子序列重复施行上述方法，直到所有的记录都排在相应位置上为止。直到所有的记录都排在相应位置上为止。n基准记录也称为枢轴（或支点）记录。基准记录也称为枢轴（或支点）记录。第第9章内部排序章内部排序二、快速排序二、快速排序( (算法算法) )32第三节快速排序第三节快速排序n取序列第一个记录为枢轴记录，其关键字为取序列第一个记录为枢轴记录，其关键字为PivotkeyPivotkeyn指针指针lowlow指向序列第一个记录位置指向序列第一个记录位置n指针指针highhigh指向序列最后一个记录位置指向序列最后一个记录位置第第9章内部排序章内部排序二、快速排序二、快

17、速排序( (算法算法) )33第三节快速排序第三节快速排序n一趟排序一趟排序( (某个子序列某个子序列) )过程过程1.1.从从highhigh指向的记录开始指向的记录开始, ,向前找到第一个关键字的值向前找到第一个关键字的值小于小于PivotkeyPivotkey的记录的记录, ,将其放到将其放到lowlow指向的位指向的位置置, ,low+1low+12.2.从从lowlow指向的记录开始指向的记录开始, ,向后找到第一个关键字的值向后找到第一个关键字的值大于大于PivotkeyPivotkey的记录的记录, ,将其放到将其放到highhigh指向的位指向的位置置, ,high-1high

18、-13.3.重复重复1,21,2，直到，直到low=highlow=high，将枢轴记录放在将枢轴记录放在low(high)low(high)指向的位置指向的位置第第9章内部排序章内部排序二、快速排序二、快速排序( (算法算法) )34第三节快速排序第三节快速排序n对枢轴记录前后两个子序列执行相同的操作，对枢轴记录前后两个子序列执行相同的操作，直到每个子序列都只有一个记录为止直到每个子序列都只有一个记录为止第第9章内部排序章内部排序一、快速排序一、快速排序( (算法实现算法实现) )35第二节快速排序第二节快速排序第第9章内部排序章内部排序void void QuickSortQuickSor

19、t ( (intint r ; r ;intint b;intb;int m ) m ) / / 假设关键字为整型，放在向量假设关键字为整型，放在向量rr中中 intint low=b, high=m, temp=r1; low=b, high=m, temp=r1; while ( lowhigh) while ( lowtemp) high=high-1; while(rhightemp) high=high-1; rlow rlow-rhigh-rhigh; while(rlowtemp) low=low+1; while(rlow-rhigh;rhigh; rlow=rhigh=tem

20、p; rlow=rhigh=temp; QuickSortQuickSort(r,1,high-1);(r,1,high-1); QuickSortQuickSort(r,high+1,m);(r,high+1,m); 二、快速排序二、快速排序( (举例举例) )36第三节快速排序第三节快速排序第第9章内部排序章内部排序初始关键字初始关键字pivotkey一次交换一次交换二次交换二次交换三次交换三次交换high-1完成一趟排序完成一趟排序lowhighlowlowlowlowlowhighhighhighhighhigh二、快速排序二、快速排序( (举例举例) )37第三节快速排序第三节快速排

21、序第第9章内部排序章内部排序完成一趟排序完成一趟排序分别进行快速排序分别进行快速排序有序序列有序序列二、快速排序二、快速排序( (性能分析性能分析) )38第三节快速排序第三节快速排序n快速排序是一个递归过程快速排序是一个递归过程, , 其递归树如图所示其递归树如图所示第第9章内部排序章内部排序n利用序列第一个记录作为利用序列第一个记录作为基准，将整个序列划分为基准，将整个序列划分为左右两个子序列。只要是左右两个子序列。只要是关键字小于基准记录关键关键字小于基准记录关键字的记录都移到序列左侧字的记录都移到序列左侧二、快速排序二、快速排序( (性能分析性能分析) )39第三节快速排序第三节快速排

22、序n快速排序的趟数取决于递归树的高度。快速排序的趟数取决于递归树的高度。n如果每次划分对一个记录定位后如果每次划分对一个记录定位后, , 该记录的左该记录的左侧子序列与右侧子序列的长度相同侧子序列与右侧子序列的长度相同, , 则下一步则下一步将是对两个长度减半的子序列进行排序将是对两个长度减半的子序列进行排序, , 这是这是最理想的情况。最理想的情况。第第9章内部排序章内部排序二、快速排序二、快速排序( (性能分析性能分析) )40第三节快速排序第三节快速排序n在在 n n个元素的序列中个元素的序列中, ,对一个记录定位所需时对一个记录定位所需时间为间为 O(n)O(n)。若设若设 t(n)

23、t(n) 是对是对 n n 个元素的序列个元素的序列进行排序所需的时间进行排序所需的时间, , 而且每次对一个记录正而且每次对一个记录正确定位后确定位后, , 正好把序列划分为长度相等的两个正好把序列划分为长度相等的两个子序列子序列, , 此时此时, , 总的计算时间为：总的计算时间为：T(n) cn + 2T(n/2 ) / c 是一个常数是一个常数 cn + 2 ( cn/2 + 2T(n/4) ) = 2cn + 4T(n/4) 2cn + 4 ( cn/4 +2T(n/8) ) = 3cn + 8T(n/8) cn log2n + nT(1) = O(n log2n )第第9章内部排序

24、章内部排序二、快速排序二、快速排序( (性能分析性能分析) )41第三节快速排序第三节快速排序n可以证明可以证明, , 快速排序的平均计算时间也是快速排序的平均计算时间也是O(nlogO(nlog2 2n)n)。n实验结果表明实验结果表明: : 就平均计算时间而言就平均计算时间而言, , 快速排快速排序是所有内排序方法中最好的一个。序是所有内排序方法中最好的一个。n但快速排序是一种不稳定的排序方法但快速排序是一种不稳定的排序方法第第9章内部排序章内部排序二、快速排序二、快速排序( (性能分析性能分析) )42第三节快速排序第三节快速排序n在最坏情况下在最坏情况下, , 即待排序记录序列已经按其

25、关键字从即待排序记录序列已经按其关键字从小到大排好序小到大排好序, , 其递归树成为单支树其递归树成为单支树, , n每次划分只得到一个比上一次少一个记录的子序列。每次划分只得到一个比上一次少一个记录的子序列。n必须经过必须经过n-1 n-1 趟才能把所有记录定位趟才能把所有记录定位, , n而且第而且第 i i 趟需要经过趟需要经过 n-i n-i 次关键字比较才能找到第次关键字比较才能找到第 i i 个记录的安放位置，总的关键字比较次数将达到个记录的安放位置，总的关键字比较次数将达到第第9章内部排序章内部排序2121211nnninni)()(二、快速排序二、快速排序( (改进改进) )4

26、3第三节快速排序第三节快速排序n枢轴记录取枢轴记录取lowlow、highhigh、(low+high)/2(low+high)/2三者指三者指向记录关键字居中的记录向记录关键字居中的记录第第9章内部排序章内部排序一、简单选择排序一、简单选择排序44第四节选择排序第四节选择排序n每一趟每一趟( (例如第例如第i i趟趟, ,i=0,1,i=0,1,n-2),n-2)在后面在后面n-in-i个待排序记录中选出关键字最小的记录个待排序记录中选出关键字最小的记录, ,与第与第i i个记录交换个记录交换第第9章内部排序章内部排序一、简单选择排序一、简单选择排序( (举例举例) )45第四节选择排序第四

27、节选择排序第第9章内部排序章内部排序0 1 2 3 4 5 最小者 08交换21,08最小者 16交换25,16最小者 21交换49,21i=0i=1i=2一、简单选择排序一、简单选择排序( (举例举例) )46第四节选择排序第四节选择排序第第9章内部排序章内部排序0 1 2 3 4 5 最小者 25*不需交换最小者 25不需交换结束i=3i=4i=5一、简单选择排序一、简单选择排序( (性能分析性能分析) )47第四节选择排序第四节选择排序n直接选择排序的关键字比较次数直接选择排序的关键字比较次数 KCN KCN 与记录与记录的初始排列无关。的初始排列无关。n设整个待排序记录序列有设整个待排

28、序记录序列有n n个记录个记录, ,则第则第i i趟选趟选择具有最小关键字记录所需的比较次数总是择具有最小关键字记录所需的比较次数总是 n-i-1n-i-1次。总的关键字比较次数为次。总的关键字比较次数为第第9章内部排序章内部排序20211ninninKCN)()(一、简单选择排序一、简单选择排序( (性能分析性能分析) )48第四节选择排序第四节选择排序n记录的移动次数与记录序列的初始排列有关。记录的移动次数与记录序列的初始排列有关。当这组记录的初始状态是按其关键字从小到大当这组记录的初始状态是按其关键字从小到大有序的时候有序的时候, ,记录的移动次数记录的移动次数RMN=0,RMN=0,达

29、到最少。达到最少。n最坏情况是每一趟都要进行交换，总的记录移最坏情况是每一趟都要进行交换，总的记录移动次数为动次数为 RMN = 3(n-1)RMN = 3(n-1)。n直接选择排序是一种不稳定的排序方法。直接选择排序是一种不稳定的排序方法。第第9章内部排序章内部排序二、堆排序二、堆排序49第四节选择排序第四节选择排序n设有一个关键字集合，按完全二叉树的顺序存设有一个关键字集合，按完全二叉树的顺序存储方式存放在一个一维数组中。对它们从根开储方式存放在一个一维数组中。对它们从根开始，自顶向下，同一层自左向右从始，自顶向下，同一层自左向右从 1 1 开始连开始连续编号。若满足续编号。若满足 K K

30、i i K K2i2i & K & Ki i K K2i+1 2i+1 则称该关键字集合构成一个堆则称该关键字集合构成一个堆( (最大堆最大堆) )第第9章内部排序章内部排序二、堆排序二、堆排序( (举例举例) )50第四节选择排序第四节选择排序第第9章内部排序章内部排序136542二、堆排序二、堆排序51第四节选择排序第四节选择排序n堆排序主要要解决两个问题：堆排序主要要解决两个问题：1.1.如何根据给的序列建初始堆如何根据给的序列建初始堆2.2.如何在交换掉根结点后，将剩下的结点调整为如何在交换掉根结点后，将剩下的结点调整为新的堆新的堆( (筛选筛选) )第第9章内部排序章内部排序二、堆排

31、序二、堆排序( (筛选筛选) )52第四节选择排序第四节选择排序n输出根结点输出根结点n用最后结点代替根结点值用最后结点代替根结点值n比较根结点与两个子结点的值，如果小于其中比较根结点与两个子结点的值，如果小于其中一个子结点，则选择大的子结点与根结点交换一个子结点，则选择大的子结点与根结点交换n继续将交换的结点与其子结点比较继续将交换的结点与其子结点比较n直到叶子结点或者根节点值大于两个子结点直到叶子结点或者根节点值大于两个子结点第第9章内部排序章内部排序二、堆排序二、堆排序( (筛选举例筛选举例) )53第四节选择排序第四节选择排序第第9章内部排序章内部排序13654213654213654

32、2二、堆排序二、堆排序( (创建初始堆创建初始堆) )54第四节选择排序第四节选择排序n根据给定的序列，从根据给定的序列，从1 1至至n n按顺序创建一个完全按顺序创建一个完全二叉树二叉树n由最后一个非终端结点由最后一个非终端结点( (第第n/2n/2个结点个结点) )开始至开始至第第1 1个结点，逐步做筛选个结点，逐步做筛选第第9章内部排序章内部排序二、堆排序二、堆排序( (创建初始堆举例创建初始堆举例) )55第四节选择排序第四节选择排序n已知待序的一组记录的初始排列为：已知待序的一组记录的初始排列为：21,25,49, 21,25,49, 2525* *,16,08,16,08第第9章内

33、部排序章内部排序123456二、堆排序二、堆排序( (创建初始堆举例创建初始堆举例) )56第四节选择排序第四节选择排序第第9章内部排序章内部排序123456136542i = 3 时的局部调整时的局部调整二、堆排序二、堆排序( (创建初始堆举例创建初始堆举例) )57第四节选择排序第四节选择排序第第9章内部排序章内部排序123456136542二、堆排序二、堆排序( (举例举例) )58第四节选择排序第四节选择排序第第9章内部排序章内部排序012345025431二、堆排序二、堆排序( (举例举例) )59第四节选择排序第四节选择排序第第9章内部排序章内部排序012345025431二、堆排

34、序二、堆排序( (举例举例) )60第四节选择排序第四节选择排序第第9章内部排序章内部排序012345025431二、堆排序二、堆排序( (举例举例) )61第四节选择排序第四节选择排序第第9章内部排序章内部排序012345025431二、堆排序二、堆排序( (举例举例) )62第四节选择排序第四节选择排序第第9章内部排序章内部排序012345025431二、堆排序二、堆排序( (性能分析性能分析) )63第四节选择排序第四节选择排序n对于长度为对于长度为n n的序列，其对应的完全二叉树的的序列，其对应的完全二叉树的深度为深度为k(k(2 2k-1k-1 n n 2 2k k) )n对深度为对

35、深度为k k的堆，筛选算法中进行的关键比较的堆，筛选算法中进行的关键比较次数至多为次数至多为2(2(k-1)k-1)次次n堆排序时间主要耗费在建初始堆和调整建新堆堆排序时间主要耗费在建初始堆和调整建新堆( (筛选筛选) )上上n建初始堆最多做建初始堆最多做n/2n/2次筛选次筛选第第9章内部排序章内部排序二、堆排序二、堆排序( (性能分析性能分析) )64第四节选择排序第四节选择排序n对长度为对长度为n n的序列，排序最多需要做的序列，排序最多需要做n-1n-1次调整次调整建新堆建新堆( (筛选筛选) )n因此共需要因此共需要O(nxk)O(nxk)量级的时间量级的时间nk = logk =

36、log2 2n nn堆排序时间复杂度为堆排序时间复杂度为O(nlogO(nlog2 2n)n)n堆排序是一个不稳定的排序方法堆排序是一个不稳定的排序方法第第9章内部排序章内部排序一、归并一、归并65第五节归并排序第五节归并排序n归并是将两个或两个以上的有序表合并成一个归并是将两个或两个以上的有序表合并成一个新的有序表。新的有序表。第第9章内部排序章内部排序二、两路归并二、两路归并66第五节归并排序第五节归并排序typedef int SortData;void merge ( SortData InitList , SortData mergedList , int left, int mid

37、, int right ) int i = left, j = mid+1, k = left; while ( i = mid & j = right ) /两两比较将较小的并入 if ( InitListi = InitListj ) mergedList k = InitListi; i+; k+; else mergedList k = InitListj; j+; k+; while (i = mid) mergedListk = InitListi; i+; k+; /将mid前剩余的并入 while (j = right) mergedListk = InitListj; j+;

38、 k+; /将mid后剩余的并入第第9章内部排序章内部排序Left midrightInitListmergedList二、两路归并二、两路归并( (性能分析性能分析) )67第五节归并排序第五节归并排序n假设待归两个有序表长度分别为假设待归两个有序表长度分别为m m和和n n，则两路则两路归并后，新的有序表长度为归并后，新的有序表长度为m+nm+nn两路归并操作至多只需要两路归并操作至多只需要m+nm+n次移位和次移位和m+nm+n次比次比较较n因此两路归并的时间复杂度为因此两路归并的时间复杂度为O(m+n)O(m+n)第第9章内部排序章内部排序三、三、2 2路归并排序路归并排序68第五节归

39、并排序第五节归并排序n将将n n个记录看成是个记录看成是n n个有序序列个有序序列n将前后相邻的两个有序序列归并为一个有序序将前后相邻的两个有序序列归并为一个有序序列列( (两路归并两路归并) )n重复做两路归并操作，直到只有一个有序序列重复做两路归并操作，直到只有一个有序序列为止为止第第9章内部排序章内部排序三、三、2 2路归并排序路归并排序( (举例举例) )69第五节归并排序第五节归并排序第第9章内部排序章内部排序0 1 2 3 4 5 一趟归并之后二趟归并之后三趟归并之后三、三、2 2路归并排序路归并排序( (性能分析性能分析) )70第五节归并排序第五节归并排序n如果待排序的记录为如

40、果待排序的记录为n n个，则需要做个，则需要做loglog2 2n n趟两趟两路归并排序路归并排序n每趟两路归并排序的时间复杂度为每趟两路归并排序的时间复杂度为O(n)O(n)n因此因此2 2路归并排序的时间复杂度为路归并排序的时间复杂度为O(nlogO(nlog2 2n)n)n归并排序是一种稳定的排序方法归并排序是一种稳定的排序方法第第9章内部排序章内部排序一、多关键字的排序一、多关键字的排序71第六节基数排序第六节基数排序n例：对例：对5252张扑克牌按以下次序排序：张扑克牌按以下次序排序：23A23A23A23An两个关键字：花色两个关键字：花色（） 面值面值（23A）n并且并且“花色花

41、色”地位高于地位高于“面值面值”第第9章内部排序章内部排序一、多关键字的排序一、多关键字的排序( (最低位优先法最低位优先法LSD)LSD)72第六节基数排序第六节基数排序n从最低位关键字从最低位关键字kdkd起进行排序，起进行排序，n然后再对高一位的关键字排序，然后再对高一位的关键字排序，n依次重复，直至对最高位关键字依次重复，直至对最高位关键字k1k1排序后，便排序后，便成为一个有序序列成为一个有序序列第第9章内部排序章内部排序一、多关键字的排序一、多关键字的排序( (最低位优先法最低位优先法LSDLSD举例举例) )73第六节基数排序第六节基数排序第第9章内部排序章内部排序0 1 2 3

42、 4 5 最低位(个位)排序后最高位(十位)排序后二、链式基数排序二、链式基数排序74第六节基数排序第六节基数排序n基数排序：借助基数排序：借助“分配分配”和和“收集收集”对单逻辑对单逻辑关键字进行排序的一种方法关键字进行排序的一种方法n链式基数排序方法：用链表作存储结构的基数链式基数排序方法：用链表作存储结构的基数排序排序n设置设置1010个队列，个队列，fifi和和eiei分别为第分别为第i i个队列个队列的头指针和尾指针的头指针和尾指针第第9章内部排序章内部排序二、链式基数排序二、链式基数排序75第六节基数排序第六节基数排序n第第i i趟分配：根据第趟分配：根据第i i位关键字的值，改变

43、记录位关键字的值，改变记录的指针，将链表中记录分配至的指针，将链表中记录分配至1010个链队列中，个链队列中，每个队列中记录关键字的第每个队列中记录关键字的第i i位关键字相同位关键字相同n第第i i趟收集：改变所有非空队列的队尾记录的趟收集：改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，指针域，令其指向下一个非空队列的队头记录，重新将重新将1010个队列链成一个链表个队列链成一个链表第第9章内部排序章内部排序二、链式基数排序二、链式基数排序76第六节基数排序第六节基数排序n从最低位至最高位，逐位执行上述两步操作，从最低位至最高位，逐位执行上述两步操作，最后得到一个有序

44、序列最后得到一个有序序列第第9章内部排序章内部排序二、链式基数排序二、链式基数排序( (举例举例) )第六节基数排序第六节基数排序第第9章内部排序章内部排序初始状态初始状态278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配一趟分配930063083184505278008109589269一趟收集一趟收集二、链式基数排序二、链式基数排序( (举例举例) )第六节基数排序第六节基数排序第第9章内部排序章内部排序505008109930063

45、269278083184589二趟收集二趟收集083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配二趟分配008109278930063083184505278008109589269一趟收一趟收集集二、链式基数排序二、链式基数排序( (举例举例) )第六节基数排序第六节基数排序第第9章内部排序章内部排序008063083109184269278505589930三趟收集三趟收集109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配三趟分配0630832692

46、78505589505008109930063269278083184589二趟收集二趟收集二、链式基数排序二、链式基数排序( (性能分析性能分析) )80第六节基数排序第六节基数排序n若每个关键字有若每个关键字有 d d 位位, ,关键字的基数为关键字的基数为radixradix n需要重复执行需要重复执行d d 趟趟“分配分配”与与“收集收集”n每趟对每趟对 n n 个对象进行个对象进行“分配分配”，对，对radixradix个队个队列进行列进行“收集收集”n总时间复杂度为总时间复杂度为O(d(n+radix)O(d(n+radix)。第第9章内部排序章内部排序二、链式基数排序二、链式基数

47、排序( (性能分析性能分析) )81第六节基数排序第六节基数排序n若基数若基数radixradix相同相同, , 对于对象个数较多而关键对于对象个数较多而关键字位数较少的情况字位数较少的情况, , 使用链式基数排序较好。使用链式基数排序较好。n基数排序需要增加基数排序需要增加n+2radixn+2radix个附加链接指针。个附加链接指针。n基数排序是稳定的排序方法。基数排序是稳定的排序方法。第第9章内部排序章内部排序82第七节各种排序方法比较第七节各种排序方法比较第第9章内部排序章内部排序排序方法排序方法平均时间平均时间最坏情况最坏情况辅助存储辅助存储适合情况适合情况插入排序插入排序O(nO(

48、n2 2) )O(nO(n2 2) )O(1)O(1)记录数不很多记录数不很多希尔排序希尔排序O(n(logO(n(log2 2n)n)2 2) )O(nO(n2 2) )O(1)O(1)不太多不太多快速排序快速排序O(nlogO(nlog2 2n)n)O(nO(n2 2) )O(logO(log2 2n)n)较多较多堆排序堆排序O(nlogO(nlog2 2n)n)O(nlogO(nlog2 2n)n)O(1)O(1)较多较多归并排序归并排序O(nlogO(nlog2 2n)n)O(nlogO(nlog2 2n)n)O(n)O(n)都可以都可以基数排序基数排序O(d(n+rd)O(d(n+rd) O(d(n+rd)O(d(n+rd)O(rd)O(rd)关键字位数少关键字位数少