湘潭大学 数据结构 Ch07 Sorting 排序算法

1、编辑ppt第7章 排序很常见的一类问题（很常见的一类问题（编辑ppt1 预备知识预备知识void X_Sort ( ElementType A , int N )/* N 是排序元素个数，是合法的整数是排序元素个数，是合法的整数*/* 为简单起见，假设数组只包含整数为简单起见，假设数组只包含整数 */* 和和 运算符存在，而且是仅有的允许对输入数据进行的操运算符存在，而且是仅有的允许对输入数据进行的操作作 */基于比较基于比较的排序的排序/* 仅考虑内部排序仅考虑内部排序 */整个排序工作能够在主存中完成整个排序工作能够在主存中完成编辑ppt2 插入排序插入排序void InsertionSo

2、rt ( ElementType A , int N ) int j, P; ElementType Tmp; for ( P = 1; P 0 & A j - 1 Tmp; j- ) A j = A j - 1 ; /* shift sorted cards to provide a position for the new coming card */A j = Tmp; /* place the new card at the proper position */ /* end for-P-loop */最坏情形最坏情形:输入的输入的 A 是反序的。是反序的。 T( N ) =

3、O( N2 )最好情形最好情形:输入的输入的 A 是已预先排序的。是已预先排序的。 T( N ) = O( N )编辑ppt3 一些简单排序算法的下界一些简单排序算法的下界【定义定义】成员存数的数组的一个成员存数的数组的一个逆序逆序是指数组中具有性质是指数组中具有性质 i Aj 的序偶（的序偶（ Ai， Aj）。）。例例1 输入数据输入数据 34, 8, 64, 51, 32, 21 有有 个逆序。个逆序。9 (34, 8) (34, 32) (34, 21) (64, 51) (64, 32) (64, 21) (51, 32) (51, 21) (32, 21)在插入排序中恰好需要执行在插

4、入排序中恰好需要执行 次交换。次交换。9交换两个不按原序排列的相邻元素交换两个不按原序排列的相邻元素恰好消除恰好消除一个逆序。一个逆序。T ( N, I ) = O( ) ， I 是初始数组中的逆序数。是初始数组中的逆序数。I + N如果数组如果数组几乎有序几乎有序，这个时间是很快的。这个时间是很快的。编辑ppt这就是全部结论这就是全部结论?那么怎么加速排序那么怎么加速排序?嘿嘿! 我们讨论的是我们讨论的是基于比较的基于比较的排序，排序，你必须进行比较，然后呢？你必须进行比较，然后呢？这个定理告诉我们什么这个定理告诉我们什么? 聪明聪明! 为了使算法运行更快，为了使算法运行更快，我们必须在一次

5、交换中我们必须在一次交换中不止消除一个逆序不止消除一个逆序。 交换距离较远的元素？交换距离较远的元素？呃呃 散列散列?对一整类只交换相邻元素的算法来说，对一整类只交换相邻元素的算法来说，都需要花费都需要花费 O( N2 ) 的时间来排序。的时间来排序。3一些简单排序算法的下界一些简单排序算法的下界【定理定理】N 个互异数的数组的平均逆序数是个互异数的数组的平均逆序数是 N ( N 1 ) / 4.【定理定理】通过交换相邻元素进行排序的任何算法平均需要通过交换相邻元素进行排序的任何算法平均需要 ( N2 ) 时间。时间。编辑ppt4 希尔排序希尔排序 - by Donald Shell例例2So

6、rt: 81941196123517952858417515962812588135419417751195155-sort964194112858357595128117153-sort1-sort96419411285835759512811715 定义一个定义一个增量序列增量序列 h1 h2 0; Increment /= 2 ) /*h sequence */for ( i = Increment; i = Increment; j - = Increment ) if( Tmp A j - Increment ) A j = A j - Increment ; else break;

7、 A j = Tmp; /* end for-I and for-Increment loops */编辑ppt4 希尔排序希尔排序 最坏情形分析最坏情形分析:【定理定理】使用希尔增量的希尔排序的最坏运行时间是使用希尔增量的希尔排序的最坏运行时间是 ( N2 )。例例3一个坏例子一个坏例子:19210311412513614715816192103114125136147158168-sort192103114125136147158164-sort192103114125136147158162-sort123456789101112 13 14 15 161-sort增量对未必增量对未必互

8、素互素，因此较小的增量可能影响很小。，因此较小的增量可能影响很小。编辑ppt4 希尔排序希尔排序 Hibbard增量序列增量序列:hk = 2k 1 - 相邻增量没有公因子。相邻增量没有公因子。【定理定理】使用使用Hibbard增量的希尔排序的最坏情形运行时增量的希尔排序的最坏情形运行时间为间为 ( N3/2 ).猜测：猜测： Tavg Hibbard ( N ) = O ( N5/4 ) Sedgewick的最好增量序列是的最好增量序列是 1, 5, 19, 41, 109, ，该，该序列中的项要么是序列中的项要么是 9 4i 9 2i + 1，或者是，或者是 4i 3 2i + 1。 猜测

9、其平均运行时间猜测其平均运行时间Tavg ( N ) = O ( N7/6 ) ， 最坏情形运行时间最坏情形运行时间Tworst ( N ) = O ( N4/3 ).编辑ppt希尔排序算法的整体时间复杂度希尔排序算法的整体时间复杂度和增量序列的选取有和增量序列的选取有关关，目前并没有统一的最优增量序列。，目前并没有统一的最优增量序列。 希尔排序是算法非常简单但又具有极其复杂的分析的希尔排序是算法非常简单但又具有极其复杂的分析的一种排序算法。它对适度的大量输入数据（万数量级）一种排序算法。它对适度的大量输入数据（万数量级）是经常选用的算法。是经常选用的算法。编辑ppt5 堆排序堆排序Algor

10、ithm 1: BuildHeap( H ); for ( i=0; iN; i+ ) TmpH i = DeleteMin( H ); for ( i=0; i= 0; i - - ) /* BuildHeap */ PercDown( A, i, N ); for ( i = N - 1; i 0; i - - ) Swap( &A 0 , &A i ); /* DeleteMax */ PercDown( A, 0, i ); 堆排序的数据从位置堆排序的数据从位置 0 开始。开始。【定理定理】对对 N 个互异项的随机排列进行堆排序，所用的比较个互异项的随机排列进行堆排序，

11、所用的比较平均次数为平均次数为 2N log N O( N log log N ) .Note: 虽然堆排序有虽然堆排序有最好的平均情形时间最好的平均情形时间，但实践中它比某个版本，但实践中它比某个版本的使用的使用 Sedgewick 增量序列的希尔排序要慢。增量序列的希尔排序要慢。编辑ppt6 归并排序归并排序1. 合并两个已排序数组合并两个已排序数组113 24 26215 27 3812LposRposTposT ( N ) = O ( ) ， N 是总的元素个数。是总的元素个数。NLposRposTpos Tpos二路归并二路归并。也可以使用也可以使用多路多路归并归并。编辑ppt6 归

12、并排序归并排序2. Mergesortvoid MSort( ElementType A , ElementType TmpArray , int Left, int Right ) int Center; if ( Left Right ) /* if there are elements to be sorted */Center = ( Left + Right ) / 2; MSort( A, TmpArray, Left, Center ); /* T( N / 2 ) */MSort( A, TmpArray, Center + 1, Right ); /* T( N / 2 )

13、*/Merge( A, TmpArray, Left, Center + 1, Right ); /* O( N ) */ void Mergesort( ElementType A , int N ) ElementType *TmpArray; /* need O(N) extra space */ TmpArray = malloc( N * sizeof( ElementType ) ); if ( TmpArray != NULL ) MSort( A, TmpArray, 0, N - 1 ); free( TmpArray ); else FatalError( No space

14、 for tmp array! ); 如果如果 TmpA 定义成定义成Merge的的局部变量局部变量，则每次调用，则每次调用Merge都需要开辟不同的空间都需要开辟不同的空间, 那么那么 S(N) = O( )N log N编辑ppt6 归并排序归并排序/* Lpos = start of left half, Rpos = start of right half */ void Merge( ElementType A , ElementType TmpArray , int Lpos, int Rpos, int RightEnd ) int i, LeftEnd, NumElements

15、, TmpPos; LeftEnd = Rpos - 1; TmpPos = Lpos; NumElements = RightEnd - Lpos + 1; while( Lpos = LeftEnd & Rpos = RightEnd ) /* main loop */ if ( A Lpos = A Rpos ) TmpArray TmpPos+ = A Lpos+ ; else TmpArray TmpPos+ = A Rpos+ ; while( Lpos = LeftEnd ) /* Copy rest of first half */ TmpArray TmpPos+ =

16、 A Lpos+ ; while( Rpos = RightEnd ) /* Copy rest of second half */ TmpArray TmpPos+ = A Rpos+ ; for( i = 0; i NumElements; i+, RightEnd - - ) /* Copy TmpArray back */ A RightEnd = TmpArray RightEnd ; 编辑ppt6 归并排序归并排序3. 分析分析T ( 1 ) = 1T ( N ) = 2T ( N / 2 ) + O( N )= 2k T ( N / 2k ) + k * O( N )= N *

17、T ( 1 ) + log N * O( N )= O( N + N log N )非递归实现非递归实现:A0123 n 4 n 3 n 2 n 1 Note:归并排序需要归并排序需要线性的额外线性的额外存储存储, 并且经常复制临时并且经常复制临时数组导致效率降低。数组导致效率降低。 它它很很少用于内部排序少用于内部排序，然而在，然而在外部排序外部排序中非常常用。中非常常用。编辑ppt7 快速排序快速排序- 实践中已知的实践中已知的最快最快排序算法排序算法1. 算法算法void Quicksort ( ElementType A , int N ) if ( N = e元素元素 = e2元素元

18、素 = e1元素元素 jiijiiji A Center ) Swap( &A Left , &A Center ); if ( A Left A Right ) Swap( &A Left , &A Right ); if ( A Center A Right ) Swap( &A Center , &A Right ); /* Invariant: A Left = A Center = A Right */ Swap( &A Center , &A Right - 1 ); /* Hide pivot */ /* only

19、need to sort A Left + 1 A Right 2 */ return A Right - 1 ; /* Return pivot */ 编辑ppt7 快速排序快速排序void Qsort( ElementType A , int Left, int Right ) int i, j; ElementType Pivot; if ( Left + Cutoff = Right ) /* if the sequence is not too short */ Pivot = Median3( A, Left, Right ); /* select pivot */ i = Lef

20、t; j = Right 1; /* why not set Left+1 and Right-2? */ for( ; ; ) while ( A + +i Pivot ) /* scan from right */ if ( i j ) Swap( &A i , &A j ); /* adjust partition */ else break; /* partition done */ Swap( &A i , &A Right - 1 ); /* restore pivot */ Qsort( A, Left, i - 1 ); /* recursive

21、ly sort left part */ Qsort( A, i + 1, Right ); /* recursively sort right part */ /* end if - the sequence is long */ else /* do an insertion sort on the short subarray */ InsertionSort( A + Left, Right - Left + 1 );编辑ppt7 快速排序快速排序6. 分析分析T( N ) = T( i ) + T( N i 1 ) + c N 最坏情形最坏情形:T( N ) = T( N 1 ) +

22、 c NT( N ) = O( N2 ) 最好情形最好情形: . . . . T( N ) = 2T( N / 2 ) + c NT( N ) = O( N log N ) 平均情形平均情形:假设对任意的假设对任意的i， T( i )的平均值是的平均值是 10)(1NjjTNcNjTNNTNj 10)(2)(T( N ) = O( N log N )void Qselect( ElementType A , int k, int Left, int Right ) int i, j; ElementType Pivot;/* 1*/ if( Left + Cutoff = Right ) /*

23、 2*/ Pivot = Median3( A, Left, Right );/* 3*/ i = Left; j = Right - 1;/* 4*/ for( ; ; ) /* 5*/ while( A +i Pivot ) /* 7*/ if( i j )/* 8*/ Swap( &A i , &A j ); else/* 9*/ break; /*10*/ Swap( &A i , &A Right - 1 ); /* Restore pivot */*11*/ if( k i + 1 )/*14*/ Qselect( A, k, i + 1, Righ

24、t ); else /* Do an insertion sort on the subarray */*15*/ InsertionSort( A + Left, Right - Left + 1 ); /* END */例例选择问题。选择问题。 快速选择快速选择关于此问题的关于此问题的第第5种种算法。算法。编辑ppt8 大型结构的排序大型结构的排序问题问题: 交换大型结构可能是非常昂贵的操作。交换大型结构可能是非常昂贵的操作。解决方法解决方法: 在数组中包含指向结构的指针，通过交换指针来排序在数组中包含指向结构的指针，通过交换指针来排序 间接间接排序。排序。 最后在必要时再实际地重新安排结

25、构。最后在必要时再实际地重新安排结构。listkeytable0d01b12f23c34a45e5table 413052排序列表是排序列表是list table0 , list table1 , , list tablen 1 Note: 每一个序列都由不相交的环构成。每一个序列都由不相交的环构成。listkeytable0d41b12f33c04a55e2temp = dcurrent = 0next = 4a045e452f523c23d3最坏情形下有最坏情形下有 ? 个环，需要个环，需要 ? 次记录的移动。次记录的移动。 N / 2 3N / 2 T = O( m N ) ， m 是每

26、个结构的大小。是每个结构的大小。例例Table Sort编辑ppt9 排序的一般下界排序的一般下界【定理定理】只使用只使用元素间比较元素间比较的任何排序算法需要进行的任何排序算法需要进行 ( N log N )次比较。次比较。证明证明:K0 K1K1 K2K0 K2stop0,1,2stop0,2,1stop2,0,1TFTFK0 K2K1 K2stop1,0,2stop1,2,0stop2,1,0TFTFTF三元素排序的决策树三元素排序的决策树当进行当进行 N 个互异元素排序时，有个互异元素排序时，有 N! 种可能的结果。种可能的结果。因此任意决策树必定含有至少因此任意决策树必定含有至少N!

27、 片树叶。片树叶。如果树高为如果树高为 k, 那么那么 N! 2k 1 (一棵完全二叉树中的叶子数量一棵完全二叉树中的叶子数量) k log(N!) + 1由于由于 N! (N/2)N/2 及及 log2 N! (N/2)log2(N/2) = ( N log2 N )因此因此 T(N) = k c N log2 N .编辑ppt 桶排序桶排序例例 假如有假如有N 个学生，每个人的成绩分布在个学生，每个人的成绩分布在 0 到到 100 (令令 M = 101 种可能的成绩种可能的成绩). 如何在如何在线性的时间线性的时间内按照成绩给他们内按照成绩给他们排序排序 ?count0110088算法思

28、想：算法思想： 初始化链表头数组初始化链表头数组 count ; while (读一个学生的成绩读一个学生的成绩) 把它插入链表把它插入链表 countstdnt.grade; for (i=0; i N 将会怎样将会怎样 ? “基数排序基数排序 ( Radix Sort )” 是是“桶排序桶排序 ( Bucket Sort )”的推广的推广。10 基数排序基数排序编辑ppt 基数排序基数排序：一般用于多关键字的排序：一般用于多关键字的排序10 基数排序基数排序例例 一叠牌的排序要基于一叠牌的排序要基于两个关键字。两个关键字。第一关键字第一关键字花色花色 第一关键字第一关键字面值面值2 3 4

29、 5 6 7 8 9 10 J Q K A排序结果应该是排序结果应该是: 2 . A 2 . A 2 . A 2 . A 基数排序的方法一般采用基数排序的方法一般采用“主位优先法主位优先法” ( Most Significant Digit First, MSD) 或者或者“次位优先法次位优先法” ( Least Significant Digit First, LSD)相当于相当于“分治法分治法”“分配分配-收集收集”法法编辑ppt主位优先法主位优先法(MSD ) 排序排序 先排花色先排花色: 比如比如, 建立建立4个花色的个花色的“桶桶”3 3 5 5 A A 4 4 再排面值再排面值:

30、每个桶分别独立排序每个桶分别独立排序(可以采用以前介绍的任何排序方法可以采用以前介绍的任何排序方法) 10 基数排序基数排序编辑ppt先排面值先排面值: 建立建立13个面值的个面值的“桶桶”，把牌放入相应的桶中（这叫，把牌放入相应的桶中（这叫“分配分配”）；）；2 2 3 3 4 4 5 5 A A . 依次依次“收集收集”它们成为一叠牌；它们成为一叠牌；A A 3 3 2 2 再排花色再排花色: 建立建立4个桶进行再个桶进行再“分配分配”；次次位优先法位优先法(LSD ) 排序排序 再次再次“收集收集”它们成为一叠牌即告完成。它们成为一叠牌即告完成。10 基数排序基数排序还不赶紧拿一副牌出来

31、试试？还不赶紧拿一副牌出来试试？编辑ppt例例 给定给定 N = 10 个整数，范围介于个整数，范围介于 0 到到 999 ( M = 1000 ) 之间。是否之间。是否可以在可以在线性的时间线性的时间内把它们排序内把它们排序 ? 单关键字的单关键字的基数排序基数排序输入输入: 64, 8, 216, 512, 27, 729, 0, 1, 343, 1250桶：桶：123456789（3位数可以看成个位数可以看成个3关键关键字，再按字，再按“次位优先法次位优先法”排序）排序）0轮次轮次 11512 34364125 216278729轮次轮次 20151234364125216278729轮次轮次 30185122161252772934364输出输出: 0, 1, 8, 27, 64, 125, 216, 343, 512, 729时间复杂性：时间复杂性：T=O(D(N+R) 其中其中D是轮次是轮次, N 是元素个数是元素个数, R 是桶的数是桶的数量量.按按“主位优先法主位优先法”排序将会怎样排序将会怎样?10 基数排序基数排序空间复杂性空间复杂性：S=O(