数据结构6第6章：内部分类

1、第第6 6章章 内部分类内部分类 Slide. 6 - 12015秋秋数据结构与算法数据结构与算法内存中完成：内存中完成：6.1 简单的分类算法简单的分类算法6.2 Shell分类分类6.3 快速分类快速分类6.4 归并分类归并分类6.5 堆分类堆分类6.6 基数分类基数分类第第6章章 内部分类（内部分类（Sorting）分类分类内部分类内部分类外部分类外部分类外存上完成：外存上完成：归并归并第第6 6章章 内部分类内部分类 Slide. 6 - 22015秋秋数据结构与算法数据结构与算法分类分类(Sorting)也叫排序也叫排序(Ordering)，是将一组数据按照规定顺，是将一组数据按照规

2、定顺序进行排列，其目的是为了方便查询和处理。序进行排列，其目的是为了方便查询和处理。对于给定数组对于给定数组A，经过分类处理之后，满足关系：，经过分类处理之后，满足关系： A1.keyA2.key An.key如果在分类之前存在关系如果在分类之前存在关系 Ai.key=Aj.key ( 1ijn )经分类后，经分类后，Ai和和Aj分别被移至分别被移至Ai1和和Aj1，并且，并且i1和和j1满足关系满足关系 1i1j1n我们称这种分类是我们称这种分类是稳定稳定的，否则称其为的，否则称其为不稳定不稳定的分类。的分类。第第6 6章章 内部分类内部分类 Slide. 6 - 32015秋秋数据结构与算

3、法数据结构与算法按分类时分类对象存放的设备，分成内部分类按分类时分类对象存放的设备，分成内部分类(internal sorting)和外部分类和外部分类(external sorting)。分类分类过程中数据对象全部在内存中的分类，叫内部分类。过程中数据对象全部在内存中的分类，叫内部分类。分类过程数据对象并非完全在内存中的分类，叫外部分类。分类过程数据对象并非完全在内存中的分类，叫外部分类。分类的种类分类的种类struct records keytype key ; fields other ; ；typedef records LISTmaxsize ;分类表的存储结构分类表的存储结构影响分

4、类性能的因素影响分类性能的因素比较关键字的次数比较关键字的次数当关键字是字符串时，是主要因素。当关键字是字符串时，是主要因素。交换记录位置和移动记录的次数交换记录位置和移动记录的次数当记录很大时，是主要因素。当记录很大时，是主要因素。第第6 6章章 内部分类内部分类 Slide. 6 - 42015秋秋数据结构与算法数据结构与算法 0 1 2 3 4 5 6 7 8 9 10265 076301 265 129751 301 265 265129 751 301 301 301937 129 751 438 438 438863 937 438 751 694 694 694742 863 9

5、37 694 751 742 742 742694 742 863 937 742 751 751 751 751076 694 742 863 937 863 863 863 863 863438 438 694 742 863 937 937 937 937 937 937如何取消不必如何取消不必要的循环？要的循环？6.1 简单的分类算法简单的分类算法6.1.1 气泡分类气泡分类第第6 6章章 内部分类内部分类 Slide. 6 - 52015秋秋数据结构与算法数据结构与算法气泡分类算法：气泡分类算法：Void BubbleSort ( int n , LIST &A ) int

6、x, y ; for ( i =1; i = i+1; j- ) if ( Aj.key =i+1; j-) /较小元素较小元素Aj if( Aj.key Aj-1.key ) flag=1; swap(Aj,Aj-1); for( j=i+1; j Aj+1.key ) flag=1; swap(Aj,Aj+1); i+; T(n)=O(n2)flag ?第第6 6章章 内部分类内部分类 Slide. 6 - 72015秋秋数据结构与算法数据结构与算法 初始状态：初始状态： (265) 301 751 129 937 863 742 694 076 438 第第1趟：趟： (265 301)

7、 751 129 937 863 742 694 076 438 第第2趟：趟： (265 301 751) 129 937 863 742 694 076 438 第第3趟：趟： (129 265 301 751) 937 863 742 694 076 438 第第4趟：趟： (129 265 301 751 937) 863 742 694 076 438 第第5趟：趟： (129 265 301 751 863 937) 742 694 076 438 第第6趟：趟： (129 265 301 742 751 863 937) 694 076 438 第第7趟：趟： (129 265

8、301 694 742 751 863 937) 076 438 第第8趟：趟： (076 129 265 301 694 742 751 863 937) 438 第第9趟：趟： (076 129 265 301 438 694 742 751 863 937) 6.1.2 插入分类插入分类第第6 6章章 内部分类内部分类 Slide. 6 - 82015秋秋数据结构与算法数据结构与算法插入分类算法：插入分类算法：void InsertSort ( n, A )Int n; LIST A ; int i, j ; A0.key = - ; for(i=1; i=n; i+) j=i; whi

9、le(Aj.keyAj-1.key) swap(Aj,Aj-1) ; j=j-1; T(n)=O(n2)j=i; temp=AjWhile (temp.keyAj-1.key) Aj=Aj-1; j=j-1; Aj=temp;第第6 6章章 内部分类内部分类 Slide. 6 - 92015秋秋数据结构与算法数据结构与算法 初始状态：初始状态： 265 301 751 129 937 863 742 694 076 438 第第1趟：趟： 076 301 751 129 937 863 742 694 265 438 第第2趟：趟： 076 129 751 301 937 863 742 69

10、4 265 438 第第3趟：趟： 076 129 265 301 937 863 742 694 751 438 第第4趟：趟： 076 129 265 301 937 863 742 694 751 438 第第5趟：趟： 076 129 265 301 438 863 742 694 751 937 第第6趟：趟： 076 129 265 301 438 694 742 863 751 937 第第7趟：趟： 076 129 265 301 438 694 742 863 751 937 第第8趟：趟： 076 129 265 301 438 694 742 751 863 937 第第

11、9趟：趟： 076 129 265 301 438 694 742 751 863 9376.1.3 选择分类选择分类第第6 6章章 内部分类内部分类 Slide. 6 - 102015秋秋数据结构与算法数据结构与算法选择分类算法（冒泡程序）选择分类算法（冒泡程序）void SelectSort ( n, A )int n; LIST A ; int i, j，lowindex ; keytype lowkey; for(i=1; in; i+) lowindex = i ; for ( j = i+1; j=n; j+) if ( Aj.key Ai+1) swap(Ai,Ai+1);if(

12、AiAi+1) swap(Ai,Ai+1); 重复上述二趟交换过程交换进行，直至整个数组有序。重复上述二趟交换过程交换进行，直至整个数组有序。问：问： (1)(1)结束条件是什么？结束条件是什么？ (2)(2)实现算法。实现算法。第第6 6章章 内部分类内部分类 Slide. 6 - 122015秋秋数据结构与算法数据结构与算法Void OESort(LIST &A , int n) int i , flag ; do flag = 0 ; for( i=0; i Ai+1 ) flag = 1; swap(Ai,Ai+1); for( i=1; i Ai+1 ) flag = 1;

13、swap(Ai,Ai+1); while(flag); (2)奇偶转换排序算法：奇偶转换排序算法：(1)结束条件为不产生交换：结束条件为不产生交换：第第6 6章章 内部分类内部分类 Slide. 6 - 132015秋秋数据结构与算法数据结构与算法6.2 Shell 分类分类希尔（希尔（ShellShell）排序又称缩小增量法，基本思想为：）排序又称缩小增量法，基本思想为：先取定一个整数先取定一个整数d d1 1nn，把全部结点分成，把全部结点分成d d1 1个组，所有距离为个组，所有距离为d d1 1倍数的记录放在一组中，在各组内进行直接插入排序；然倍数的记录放在一组中，在各组内进行直接插入

14、排序；然后取后取d d2 2d= 1; k /= 2 ) for( i=k+1; i0) & (x.keyR（L=R+1），成功划分，），成功划分，L是右边子序列的是右边子序列的 起始下表；起始下表； 交换：若交换：若LR（L=R+1）为止。）为止。第第6 6章章 内部分类内部分类 Slide. 6 - 192015秋秋数据结构与算法数据结构与算法int findpivot( int i, int j ) keytype firstkey ; int k ; firstkey = Ai.key ; for ( k=i ; k firstkey ) return k ; else if

15、( Ak.key firstkey ) return i ; return 0 ;找中间值找中间值算法算法:第第6 6章章 内部分类内部分类 Slide. 6 - 202015秋秋数据结构与算法数据结构与算法Int partion ( i, j, pivot )Int i, j; keytype pivot ; int L, R ; L = i ; R = j ; do swap ( AL, AR ) ; while ( AL.key = pivot ) R = R -1 ; while ( L = R ); return L ;Void quicksort ( int i, int j )

16、keytype pivot ; int piovtindex , k ; pivotindex = findpivot( i, j ) ; if ( pivotindex ) pivot = Apivotindex.key ; k = partion ( i, j, pivot ) ; quicksort( i, k-1); quicksort( k, j ); 分割分割: i, , j i, k-1, k, k+1, j 快速分类快速分类调用：调用：quicksort( 1, n )T(n) = O( f(n) )第第6 6章章 内部分类内部分类 Slide. 6 - 212015秋秋数据结

17、构与算法数据结构与算法3562951413时间复杂性和稳定性时间复杂性和稳定性时间复杂性：时间复杂性：T(n) =O(nlog2n) 稳定性：是不稳定的分类稳定性：是不稳定的分类举例举例3563954112v =35569334v =5433v =49565v =9655v =6211v =29655433211组合组合第第6 6章章 内部分类内部分类 Slide. 6 - 222015秋秋数据结构与算法数据结构与算法例：对长度为例：对长度为n的记录序列进行快速排序时，所需要的比较次数的记录序列进行快速排序时，所需要的比较次数 依赖于这依赖于这n个元素的初始序列。个元素的初始序列。 问：问：(

18、1) 当当n=8时，在最好情况下需要进行多少次比较？时，在最好情况下需要进行多少次比较？ (2) 给出给出n=8时的最好情况的初始排序实例。时的最好情况的初始排序实例。解：解：n=8n=3n=4n=1n=1n=1n=2n=17次比较2次比较3次比较1次比较(1) 共共13次次第第6 6章章 内部分类内部分类 Slide. 6 - 232015秋秋数据结构与算法数据结构与算法(2) 如：如： 23 13 17 21 60 30 18 28一次划分后：一次划分后：18 13 17 21 23 30 60 28二次划分后：二次划分后：17 13 18 21四次划分后：四次划分后： 28 30 60三

19、次划分后：三次划分后：13 17 13216028结果：结果： 13 17 18 21 23 28 30 60第第6 6章章 内部分类内部分类 Slide. 6 - 242015秋秋数据结构与算法数据结构与算法int Partition(int i，int j，int pivot) /对对Alow.high做划分，并返回基准记录的位置做划分，并返回基准记录的位置 while(ij) /从区间两端交替向中间扫描，直至从区间两端交替向中间扫描，直至i=j为止为止 while(i=pivot) /pivot相当于在位置相当于在位置i上上 j-； /从右向左扫描，查找第从右向左扫描，查找第1个关键字小

20、于个关键字小于pivot的记录的记录Aj if(ij) /表示找到的表示找到的Aj的关键字的关键字pivot Ai+=Aj； /相当于交换相当于交换Ai和和Aj，交换后，交换后i指针加指针加1 while(ij&Ai.key=pivot) /pivot相当于在位置相当于在位置j上上 i+； /从左向右扫描，查找第从左向右扫描，查找第1个关键字大于个关键字大于pivot的记录的记录Ai if(ipivot Aj-=Ai; /相当于交换相当于交换Ai和和Aj，交换后，交换后j指针减指针减1 /endwhile Ai=pivot； /基准记录已被最后定位基准记录已被最后定位 return i

21、； /partition 另一种划分方法另一种划分方法第第6 6章章 内部分类内部分类 Slide. 6 - 252015秋秋数据结构与算法数据结构与算法6.4 归并分类归并分类合并两个有序序列合并两个有序序列Void merge ( l l , m, n, A, B )Int l l, m, n ; LIST A, &B ; int i, j, k, t ; i = l l ; k = l l ; j = m+1 ; while ( ( i = m ) & ( j = n ) ) if ( Ai.key m ) for ( t = j ; t = n ; t+ ) Bk+t-

22、j = At ; else for ( t = i ; t = m ; t+ ) Bk+t-i = At ;合并Al,Am 和 Am+1,An形成新的分类序列 Bl,Bn算法时间复杂度T(n) = O(n-l+1)第第6 6章章 内部分类内部分类 Slide. 6 - 262015秋秋数据结构与算法数据结构与算法26 5 77 1 61 11 59 15 48 19 5 26 1 77 11 61 15 59 19 48 1 5 26 77 11 15 59 61 19 48 1 5 11 15 26 59 61 77 19 48 1 5 11 15 19 26 48 59 61 77 归并次

23、数：归并次数：1，2， ，2i-1，若长度为若长度为 n ，则共需归并，则共需归并 log2n总的时间复杂性为：总的时间复杂性为：T(n) = O( nlog2 n )第第6 6章章 内部分类内部分类 Slide. 6 - 272015秋秋数据结构与算法数据结构与算法Void mpass ( n, l l, A , B )int n, l l ; LIST A, &B ; int i , t ; i = 1 ; while ( i = (n-2*l l+1) ) merge ( i, i+l l-1, i+2*l l-1, A, B ) i = i + 2*l l ; if ( i+l

24、 l-1) n ) merge ( i , i+l l-1, n, A, B ); else for ( t = i ; t = n ; t+ ) Bt = At;Void T_W_SORT(n , A )Int n ; LIST &A ; int l l ; LIST B ; l l = 1 ; while( l l n ) mpass( n, l l, A, B ) ; l l = 2* l l ; mpass( n, l l, B, A ) ; l l = 2*l l ; 第第6 6章章 内部分类内部分类 Slide. 6 - 282015秋秋数据结构与算法数据结构与算法Void

25、 merge ( l , m, n, A, B )Void mpass ( n, l, A , B )l m m+1 nl nABi = 1 ;while ( i = (n-2*l+1) ) merge ( i, i+l-1, i+2*l-1, A, B ) i = i + 2*l ; if ( i+l-1) n ) merge ( i , i+l-1, n, A, B );else for ( t = i ; t ll第第6 6章章 内部分类内部分类 Slide. 6 - 292015秋秋数据结构与算法数据结构与算法26 5 77 1 61 11 59 15 48 19 5 26 1 77

26、11 61 15 59 19 48 1 5 26 77 11 15 59 61 19 48 1 5 11 15 26 59 61 77 19 48 1 5 11 15 19 26 48 59 61 77 归并次数：归并次数：1，2， ，2i-1，若长度为若长度为 n ，则共需归并，则共需归并 log2n总的时间复杂性为：总的时间复杂性为：T(n) = O( nlog2 n )第第6 6章章 内部分类内部分类 Slide. 6 - 302015秋秋数据结构与算法数据结构与算法6.5 堆分类堆分类定义定义把具有如下性质的数组把具有如下性质的数组A表示的二元树称为堆（表示的二元树称为堆（Heap）:

27、 (1) 若若2*in，则，则Ai.key A2*i.key ; (2) 若若2*i+1n，则，则Ai.keyA2*i+1.key ; 小顶堆小顶堆 或：或： 把具有如下性质的数组把具有如下性质的数组A表示的二元树称为堆（表示的二元树称为堆（Heap）: (1) 若若2*in，则，则Ai.key A2*i.key ; (2) 若若2*i+1n，则，则Ai.key A2*i+1.key ; 大顶堆大顶堆例：例：11233946551 1 2 3 3 9 4 6 5 5第第6 6章章 内部分类内部分类 Slide. 6 - 312015秋秋数据结构与算法数据结构与算法11233946551 1 2

28、 3 3 9 4 6 5 51325394651 3 2 5 3 9 4 6 5 1234539562 3 4 5 3 9 5 6 1 133456953 3 4 5 6 9 5 2 1 13545693 5 4 5 6 9 3 2 1 1459564 5 9 5 6 3 3 2 1 155965 5 9 6 4 3 3 2 1 15695 6 9 5 4 3 3 2 1 1696 9 5 5 4 3 3 2 1 199 6 5 5 4 3 3 2 1 1第第6 6章章 内部分类内部分类 Slide. 6 - 322015秋秋数据结构与算法数据结构与算法Void pushdown( first

29、, last )Int first , last ; int r ; r = first ; while ( r A2*r.key ) swap ( Ar, A2*r ) ; r = last ; /*结束循环结束循环*/ else if ( ( Ar.key A2*r.key ) & ( A2*r.key A2*r+1.key ) & ( A2*r+1.key = 1 ; i- ) pushdown( i , n ) ; for ( i = n ; i = 2 ; i- ) swap ( A1, Ai ) ; pushdown ( 1, i -1 ) ; T( n ) = O

30、 ( nlog2n )整理堆整理堆建堆建堆堆排序堆排序？first ？last ?第第6 6章章 内部分类内部分类 Slide. 6 - 352015秋秋数据结构与算法数据结构与算法6.6 基数分类基数分类多关键字分类多关键字分类321 986 123 432 543 018 765 678 987 789 098 890 109 901 210 012Q0:901 109Q1:210 012 018Q2:321 123Q3:432Q4:543Q5:Q6:765Q7:678Q8:986 987 789Q9:890 098901 109 210 012 018 321 123 432 543 7

31、65 678 986 987 789 890 098Q0:012 018 098Q1:109 123Q2:210Q3:321Q4:432Q5:543Q6:678Q7:765 789Q8:890Q9: 901 986 987012 018 098 109 123 310 321 432 543 678 765 789 890 901 986 987Q0:890 210Q1:321 901Q2:432 012Q3:123 543Q4:Q5:765Q6:986Q7:987Q8:018 678 098Q9:789 109890 210 321 901 432 012 123 543 765 986 9

32、87 018 678 098 789 109 第第6 6章章 内部分类内部分类 Slide. 6 - 362015秋秋数据结构与算法数据结构与算法Void radixsort ( figure , A )int figure ; QUEUE &A ; QUEUE Q10 ; records data ; int pass, r, i ; for ( pass=1 ; pass =figure ; pass+ ) for ( i=0 ; i=9 ; i+ ) MAKENULL( Qi ) ; while ( !EMPTY( A ) ) data = FRONT ( A ) ; DEQUE

33、UE ( A ) ; r = RADIX( data. key , pass ) ; ENQUEUE( data , Qr ) ; for ( i=0 ; i =9 ; i+ ) while ( !EMPTY( Qi ) ) data = FRONT ( Qi ) ; DEQUEUE( Qi ) ; ENQUEUE( data , A ) ; Int RADIX( k, p )Int k, p ; int power , i ; power = 1 ; for ( i=1; i=1 ; j- ) for ( i=0 ; i = m-1 ; i+ ) 初始化桶 Qi ; while ( QUEU

34、E 不空 ) 设 Ai 为 QUEUE 的队首元素，删除Ai，并放到桶Qaij中 ； for ( i=0 ; i = m-1 ; i+ ) 将桶 Qi 连接到队列 QUEUE 后 ; 词典排序算法第第6 6章章 内部分类内部分类 Slide. 6 - 382015秋秋数据结构与算法数据结构与算法6.8* 求第求第 k 个最小元素个最小元素顺序统计问题顺序统计问题在一个含有 n 个元素的序列中，要求出第 k 个最小元素, 也称顺序统计。可以先进行排序，然后求出第 k 个最小元素。T(n) = O(nlogn)。下面的算法使得 T(n) =O (n)。（证明P233略）基本思想： 根据某一元素m

35、将 原序列 S 化分成3个子序列S1，S2和S3，使得S1的所有元素都小于m ，S2的所有元素等于m，而S3的所有元素都大于m，通过统计S1和S2的元素个数，可以确定所求的第 k 个最小元素是在S1和S2或S3中。 通过上述方式，将一个给定的问题转换成一个更小的问题。为保证O(n)，必须保证在线性时间里找到划分元素 m，使得S1和S2的大小 不超过S的一个固定部分。问题的关键是如何选择划分元素m。下面算法中，S 被划分成若干子序列，每个子序列由 5 个元素组成。对每个子序列排序，取其中值组成一个序列 M。M 只包含 n/5 个元素， 可以比原来快 5 倍的速度找到 n 个元素的中值。第第6 6

36、章章 内部分类内部分类 Slide. 6 - 392015秋秋数据结构与算法数据结构与算法输入：由 n 个元素组成的序列 S 和 整数 k (1kn) 。输出：S 中第 k 个最小元素 。Elementtype Select ( int k , LIST S ) if ( |S| = k ) return Select ( k , S1 ) ; else if ( |S1| + |S2| = k ) return m ; else return Select ( k - |S1| - |S2| , S3 ); 第第6 6章章 内部分类内部分类 Slide. 6 - 402015秋秋数据结构与算

37、法数据结构与算法小结小结各种排序的比较各种排序的比较排序方法排序方法平均时间平均时间最好情况最好情况最坏情况最坏情况辅助空间辅助空间稳定性稳定性简单排序简单排序O( n2 )O（n）O( n2 )O( 1 )稳定稳定希尔排序希尔排序O（n1.3）-O( 1 )不稳定不稳定快速排序快速排序O( nlog2n )O( nlog2n )O( n2 )O( log2n )不稳定不稳定堆排序堆排序O( nlog2n )O( nlog2n )O( nlog2n )O( 1 )不稳定不稳定归并排序归并排序O( nlog2n )O( nlog2n )O( nlog2n )O( n )稳定稳定基数排序基数排序O

38、( d (n+rd)O( d (n+rd) O( d (n+rd) O(n+ rd )稳定稳定第第6 6章章 内部分类内部分类 Slide. 6 - 412015秋秋数据结构与算法数据结构与算法不同条件下，排序方法的选择：不同条件下，排序方法的选择：(1)若n较小(如n50)，可采用直接插入或直接选择排序。 当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于 直接插人，应选直接选择排序为宜。(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序 为宜；且以直接插入排序最佳。(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法： 快速排序、堆排序

39、或归并排序。 快速排序是目前基于比较的内部排序中被认为是最好的方法， 当待排序的关键字是随机分布时，快速排序的平均时间最短；堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏况。 这两种排序都是不稳定的。基数排序适用于 n 值很大而关键字较小的序列。若要求排序稳定，则可选用归并排序，基数排序稳定性最佳。第第6 6章章 内部分类内部分类 Slide. 6 - 422015秋秋数据结构与算法数据结构与算法课堂练习题：课堂练习题：在上面的排序方法中:(1)直接插入排序、冒泡排序、归并排序和基数排序是稳定的。(2)其他排序算法均是不稳定的。(3)以带 * 号的表示区别： 希尔排序：

40、8, 1, 10, 5, 6, 8* 快速排序： 2, 2*, 1 直接选择排序： 2, 2*, 1 堆排序： 2, 2*, 1 1、以关键字序列 (265, 301, 751, 129, 937, 863, 742, 694, 076, 438)为例， 分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。 (1) 直接插入排序 (2)希尔排序 (3)冒泡排序 (4)快速排序 (5) 直接选择排序 (6) 归并排序 (7) 堆排序 (8)基数排序 上述方法中： (1)哪些是稳定的排序? (2)哪些是非稳定的排序? (3)对不稳定的排序试举出一个不稳定的实例。第第6 6章章 内部分类内部

41、分类 Slide. 6 - 432015秋秋数据结构与算法数据结构与算法初始态：265 301 751 129 937 863 742 694 076 438第一趟：265 301 751 129 937 863 742 694 076 438第二趟：265 301 751 129 937 863 742 694 076 438第三趟：129 265 301 751 937 863 742 694 076 438第四趟：129 265 301 751 937 863 742 694 076 438第五趟：129 265 301 751 863 937 742 694 076 438第六趟：12

42、9 265 301 742 751 863 937 694 076 438第七趟：129 265 301 694 742 751 863 937 076 438第八趟：076 129 265 301 694 742 751 863 937 438第九趟：076 129 265 301 438 694 742 751 863 937 (1)直接插入排序直接插入排序(方括号表示无序区方括号表示无序区)(2)希尔排序希尔排序(增量为增量为5，3，1)初始态：265 301 751 129 937 863 742 694 076 438 第一趟：265 301 694 076 438 863 742

43、751 129 937 第二趟：076 301 129 265 438 694 742 751 863 937 第三趟：076 129 265 301 438 694 742 751 863 937 第第6 6章章 内部分类内部分类 Slide. 6 - 442015秋秋数据结构与算法数据结构与算法 (3)冒泡排序冒泡排序(方括号为无序区方括号为无序区)初始态： 265 301 751 129 937 863 742 694 076 438 第一趟： 076 265 301 751 129 937 863 742 694 438 第二趟： 076 129 265 301 751 438 937

44、 863 742 694 第三趟： 076 129 265 301 438 694 751 937 863 742 第四趟： 076 129 265 301 438 694 742 751 937 863 第五趟： 076 129 265 301 438 694 742 751 863 937 第六趟： 076 129 265 301 438 694 742 751 863 937(4)快速排序快速排序(方括号表示无序区，层表示对应的递归树的层数方括号表示无序区，层表示对应的递归树的层数)初始态： 265 301 751 129 937 863 742 694 076 438第二层： 076

45、129 265 751 937 863 742 694 301 438第三层： 076 129 265 438 301 694 742 751 863 937第四层： 076 129 265 301 438 694 742 751 863 937第五层： 076 129 265 301 438 694 742 751 863 937第六层： 076 129 265 301 438 694 742 751 863 937第第6 6章章 内部分类内部分类 Slide. 6 - 452015秋秋数据结构与算法数据结构与算法(5)直接选择排序直接选择排序(方括号为无序区方括号为无序区) 初始态 265

46、 301 751 129 937 863 742 694 076 438第一趟： 076 301 751 129 937 863 742 694 265 438第二趟： 076 129 751 301 937 863 742 694 265 438第三趟： 076 129 265 301 937 863 742 694 751 438第四趟： 076 129 265 301 937 863 742 694 751 438第五趟： 076 129 265 301 438 863 742 694 751 937第六趟： 076 129 265 301 438 694 742 751 863 937

47、第七趟： 076 129 265 301 438 694 742 751 863 937第八趟： 076 129 265 301 438 694 742 751 937 863第九趟： 076 129 265 301 438 694 742 751 863 937(6)归并排序归并排序(为了表示方便，采用自底向上的归并，方括号为有序区为了表示方便，采用自底向上的归并，方括号为有序区)初始态：265 301 751 129 937 863 742 694 076 438第一趟：265 301 129 751 863 937 694 742 076 438第二趟：129 265 301 751 6

48、94 742 863 937 076 438第三趟：129 265 301 694 742 751 863 937 076 438第四趟：076 129 265 301 438 694 742 751 863 937第第6 6章章 内部分类内部分类 Slide. 6 - 462015秋秋数据结构与算法数据结构与算法(6)堆排序（通过画二叉树可以一步步得出排序结果）堆排序（通过画二叉树可以一步步得出排序结果）初始态： 265 301 751 129 937 863 742 694 076 438建立初始堆： 937 694 863 265 438 751 742 129 075 301第一次排序

49、重建堆：863 694 751 765 438 301 742 129 075 937第二次排序重建堆：751 694 742 265 438 301 075 129 863 937第三次排序重建堆：742 694 301 265 438 129 075 751 863 937第四次排序重建堆：694 438 301 265 075 129 742 751 863 937第五次排序重建堆：438 265 301 129 075 694 742 751 863 937第六次排序重建堆：301 265 075 129 438 694 742 751 863 937第七次排序重建堆：265 129

50、075 301 438 694 742 751 863 937第八次排序重建堆：129 075265 301 438 694 742 751 863 937第九次排序重建堆： 075 129 265 301 438 694 742 751 863 937(8)基数排序基数排序(方括号内表示一个箱子共有方括号内表示一个箱子共有10个箱子，箱号从个箱子，箱号从0到到9)初始态：265 301 751 129 937 863 742 694 076 438第一趟： 301 751 742 863 694 265 076 937 438 129第二趟：301 129 937 438 742 751 8

51、63 265 076 694第三趟：075 129 265 301 438 694 742 751 863 937 第第6 6章章 内部分类内部分类 Slide. 6 - 472015秋秋数据结构与算法数据结构与算法若关键字是非负整数，则基数排序最快；若要求辅助空间为O(1)，则应选堆排序；若要求排序是稳定的，且关键字是实数，则应选归并排序，因为基数排序不适用于实数，虽然它也是稳定的。 此时Partion 返回值是low.此时快速排序的运行时间是： (high-low)(high-low-1)/2=O(high-low)2)， 可以修改Partion ，将其中RecType pivot=Ri;

52、句改为： RecType pivot=R(j+i)/2； 也就是取中间的关键字为基准，这样就能使划分的结果是平衡的。3、若关键字是非负整数，快速排序、归并、堆和基数排序哪一个最快? 若要求辅助空间为O(1)，则应选择谁 ? 若要求排序是稳定的，且关键字是实数，则应选择谁 ?2、当Rlow.high中的关键字均相同时，Partion返回值是什么? 此时快速排序的的运行时间是多少? 能否修改Partion,使得划分结果是 平衡的(即划分后左右区间的长度大致相等)? 第第6 6章章 内部分类内部分类 Slide. 6 - 482015秋秋数据结构与算法数据结构与算法堆的性质是： 任一非叶结点上的关键

53、字均不大于(或不小于)其孩子结点上的关键字。 据此我们可以通过画二叉树来进行判断和调整：(1) 此序列不是堆，经调整后成为大顶堆： (100, 80, 73, 66, 39, 42, 57, 35, 21)(2) 此序列不是堆，经调整后成为小顶堆：(12, 24, 33, 65, 33, 56, 48, 92, 86, 70)(3) 此序列是一大顶堆。(4) 此序列不是堆，经调整后成为小顶堆：(05, 23, 20, 56, 28, 38, 29, 61, 35, 76, 100)4、判别下列序列是否为堆(小顶堆或大顶堆)，若不是，则将其调整为堆：(1) (100,86,73,35,39,42

54、,57,66,21)(2) (12,70,33,65,24,56,48,92,86,33)(3) (103,97,56,38,66,23,42,12,30,52,06,20)(4) (05,56,20,23,40,38,29,61,35,76,28,100)第第6 6章章 内部分类内部分类 Slide. 6 - 492015秋秋数据结构与算法数据结构与算法5、有序数组是堆吗?这四种排序算法中，直接选择、快速排序均是不稳定的，因此先予以排除，剩下两种算法中，由于直接插入算法所费时间比冒泡法更少，因此选择直接插入排序算法为宜。有序数组是堆。因为有序数组中的关键字序列满足堆的性质。若数组为降序，则此

55、堆为大顶堆，反之为小顶堆。6、若文件初态是反序的，且要求稳定排序，则在直接插入、直接选择、 冒泡排序和快速排序中选哪则种方法为宜? 第第6 6章章 内部分类内部分类 Slide. 6 - 502015秋秋数据结构与算法数据结构与算法应选直接选择排序为更好。分析如下：(1)在直接插入排序算法中，反序输入时是最坏情况，此时： 关键字的比较次数：Cmax=(n+2)(n-2)/2 记录移动次数为： Mmax=(n-1)(n+4)/2 Tmax=n2-4n-3 (以上二者相加) (2)在冒泡排序算法中，反序也是最坏情况，此时： Cmax=n(n-1)/2 Mmax=3n(n-1)/2 Tmax=2n2

56、-2n (3)在选择排序算法中， Cmax=n(n-1)/2 Mmax=3(n-1) Tmax=n2/2-5n/2-3 虽然它们的时间复杂度都是O(n2),但是选择排序的常数因子为1/2， 因此选择排序最省时间。7、若文件初态是反序的，则直接插入，直接选择和冒泡排序哪一个更好? 第第6 6章章 内部分类内部分类 Slide. 6 - 512015秋秋数据结构与算法数据结构与算法重写的算法如下： void InsertSort(SeqList R) /对顺序表中记录R0.n-1按递增序进行插入排序 int i,j; for(i=n-2;i=0;i-) /在有序区中依次插入Rn-2.R0if(Ri

57、.keyRi+1.key) /若不是这样则Ri原位不动 Rn=Ri;j=i+1; /Rn是哨兵do /从左向右在有序区中查找插入位置Rj-1=Rj; /将关键字小于Ri.key的记录向右移j+;while(Rj.keyRn.key); Rj-1=Rn; /将Ri插入到正确位置上 /endif 8、将哨兵放在Rn中，被排序的记录放在R0.n-1中，重写直接插入排序算法。第第6 6章章 内部分类内部分类 Slide. 6 - 522015秋秋数据结构与算法数据结构与算法int QuickSort ( SeqList R, int j, int low, int high) /对Rlow.high快

58、速排序int pivotpos； /划分后的基准记录的位置if (low j) return (R, j, low, pivotpos-1);else return quicksort (R, j, pivotpos+1, high); /Endif /QuickSort9、对给定的j(1jn ),要求在无序的记录区R1.n中找到按关键字自小 到大排在第 j 个位置上的记录(即在无序集合中找到第j个最小元)，试 利用快速排序的划分思想编写算法实现上述的查找操作。 第第6 6章章 内部分类内部分类 Slide. 6 - 532015秋秋数据结构与算法数据结构与算法10、设向量 A0.n-1中存有

59、 n 个互不相同的整数，且每个元素的值均在 0 到 n-1之间。试写一时间为O(n)的算法将向量A排序，结果可输出 到另一个向量 B0.n-1 中。Sort ( int *A , int *B ) /将向量A排序后送入B向量中 int i; for(i=0;i=n-1;i+)BAi=Ai;Sort ( int *A ) int i; for(i=0;ilength+；R-dataR-length.key=key; /插入新的记录for(i=R-length/2;i0;i-) /建堆 low=i;high=R-length;R-data0.key=R-datalow.key; /R-datalow是当前调整的结点for(large=2*low;largehigh，则表示R-datalow是叶子，调整结束；否则large指向R-datalow的左孩子 if(largedatal