数据结构第十章内部排序

1、第第10章章 内部排序内部排序10.1 概述概述排序：将一组任意排列的数据元素序列，重新排列成一个按排序：将一组任意排列的数据元素序列，重新排列成一个按 关键字有序（升序或降序）的序列关键字有序（升序或降序）的序列 排序分类排序分类v按待排序记录所在位置按待排序记录所在位置l内部排序：待排序记录存放在内存内部排序：待排序记录存放在内存l外部排序：排序过程中需对外存进行访问的排序外部排序：排序过程中需对外存进行访问的排序v按排序依据原则按排序依据原则l插入排序：直接插入排序、折半插入排序、希尔排序插入排序：直接插入排序、折半插入排序、希尔排序l交换排序：冒泡排序、快速排序交换排序：冒泡排序、快速

2、排序l选择排序：简单选择排序、树型选择排序、堆排序选择排序：简单选择排序、树型选择排序、堆排序l归并排序：归并排序：2-路归并排序路归并排序l基数排序基数排序v稳定排序和不稳定排序稳定排序和不稳定排序待排序列的数据存储类型待排序列的数据存储类型#define MAXSIZE 20typedef int KeyType ;typedef struct KeyType key ;InfoType otherinfo ; RedType ;typedef struct RedType r MAXSIZE + 1 ;/r0/r0闲置闲置int length ; SqList ;10.2 插入排序插入排

3、序49386597761327490 1 2 3 4 5 6 7 8 ( 49 )38 49 ) 65 ) 97 )76 97 )13 38 49 65 76 97 )27 97 ) 76 65 49 38 27 49 97 ) 76 65 4949386597761327490 1 2 3 4 5 6 7 8 ( 49 )38 49 )38 10.2 插入排序插入排序基本思想：将一个记录插入到已排好序的有序表中，得到新基本思想：将一个记录插入到已排好序的有序表中，得到新 的表依然有序。的表依然有序。实现：将序列中第实现：将序列中第1个记录看成是一个有序子序列，从第个记录看成是一个有序子序列，

4、从第2个个记录开始到第记录开始到第n个记录，逐个进行插入，直至整个序列有序个记录，逐个进行插入，直至整个序列有序49 38 65 97 76 13 27 49例：例：void InsertSort ( SqList &L ) for ( i = 2 ; i = L.length ; +i ) if ( LT ( L.r i .key , L.r i 1 .key ) L.r 0 = L.r i ; L.r i = L.r i -1 ; for ( j = i 2 ; LT ( L.r 0 .key , L.r j .key ) ; - j ) L.r j + 1 = L.r j ; L

5、.r j + 1 = L.r 0 ; 1、直接插入排序、直接插入排序算法评价：算法评价：总比较次数：总比较次数：最小值：最小值：Cmin=n-1 n( (正序正序) )最大值：最大值：Cmax=( (逆序逆序) ) n i i=2(n+2)(n-1) 2 = n n2 2 2 2总移动次数：总移动次数：最小值：最小值：Mmin=0( (正序正序) )最大值：最大值：Mmax=( (逆序逆序) ) n (i+1) i=2 n n2 2 2 2平均比较次数：平均比较次数： 1 2 ( + n ) n n2 2 2 2 n n2 2 4 4平均移动次数：平均移动次数： 1 2 ( + 0 ) n n

6、2 2 2 2 n n2 2 4 4时间复杂度：时间复杂度：O(n2)空间复杂度：空间复杂度：O(1) 1个辅助空间个辅助空间稳定排序稳定排序2、其它插入排序、其它插入排序在有序表中查找插入位置时，可采用折半查找方法。在有序表中查找插入位置时，可采用折半查找方法。折半插入排序折半插入排序49386597761327490 1 2 3 4 5 6 7 8271338496576972749lowhighmid271338496576974927移动次数不变，查找位置时比较次数可能减少。移动次数不变，查找位置时比较次数可能减少。2、其它插入排序、其它插入排序折半插入排序折半插入排序void BIn

7、sertSort ( SqList &L ) for ( i = 2 ; i = L.length ; +i ) L.r 0 = L.r i ; low = 1 ; high = i 1 ; while ( low = high + 1 ; - - j ) L.r j + 1 = L.r j ; L.r high + 1 = L.r 0 ; 时间复杂度：时间复杂度：O(n2)空间复杂度：空间复杂度：O(1) 1个辅助空间个辅助空间 2-路插入排序路插入排序为减少移动次数，增加为减少移动次数，增加n个辅助空间个辅助空间空间复杂度为空间复杂度为 O(n)但当首关键字为最大或最小时失去意义但

8、当首关键字为最大或最小时失去意义49 38 65 97 76 13 27 490 1 2 3 4 5 6 7 8493865 97 97761313 2749 65 76 97 表插入排序表插入排序为减少移动次数，先连成一个有序链，再调整成有序序列为减少移动次数，先连成一个有序链，再调整成有序序列存储结构：存储结构： # define SIZE 100typedef struct RcdType rc ; int next ; SLNode ;typedef struct SLNode r SIZE ; int length ; SlinkListType ;增加增加n个辅助空间个辅助空间 n

9、个指针域个指针域MAXINT49386597761327490 1 2 3 4 5 6 7 80112030445262738( (已排序表中元素个数已排序表中元素个数) )总比较次数最大值：总比较次数最大值：Cmax= n-1 i i=1n (n-1) 2 = n n2 2 2 2移动次数为移动次数为 0空间复杂度为：空间复杂度为： O(n)另外需重排另外需重排Cmin=Cmax=i1最小值最小值 Cmin=n-1 n n分析：分析：一趟排序：一趟排序：增加增加n个辅助空间个辅助空间 n个指针域个指针域MAXINT49386597761327490 1 2 3 4 5 6 7 8011203

10、0445262738P=6, i=1-SL.length-1 循环循环134987P=7(6)i=2273821P=2(7)i=3P=7386551P=1 i=4(7)P=6974908P=8 i=5(6)764943P=3(8)i=6P=7976505P=5(7)i=7P=8977604表插入排序重排记录算法表插入排序重排记录算法void Arrange ( SLinkListType &SL ) p = SL.r 0 .next ; for ( i = 1 ; i SL.length ; +i ) while ( p i ) p = SL.r p .next ; q = SL.r

11、p .next ; if ( p != i ) SL.r p SL.r i ; SL.r i .next = p ; p = q ; 希尔排序希尔排序 直接插入排序的时间复杂度为直接插入排序的时间复杂度为O(n2)，但若待排记录为正，但若待排记录为正序时，则时间复杂度为序时，则时间复杂度为O(n)，若，若“基本有序基本有序”，则可提高效，则可提高效率。另外在率。另外在n较小时，算法效率较高且简单。较小时，算法效率较高且简单。取d3=1三趟分组：13 27 48 55 4 49 38 65 97 76三趟排序：4 13 27 38 48 49 55 65 76 97例 初始： 49 38 65

12、97 76 13 27 48 55 4一趟排序：13 27 48 55 4 49 38 65 97 76二趟排序：13 4 48 38 27 49 55 65 97 76取d1=5一趟分组：49 38 65 97 76 13 27 48 55 4取d2=3二趟分组：13 27 48 55 4 49 38 65 97 76增量的选择增量的选择void ShellInsert ( SqList &L , int dk ) for ( i = dk + 1 ; i 0&LT(L.r0.key,L.rj.key) ; j -= dk ) L.r j + dk = L.r j ; L.r

13、 j + dk = L.r 0 ; void ShellSort ( SqList &L , int dlta , int t ) for ( k = 0 ; k t ; +k ) ShellInsert ( L , dlta k ) ;效率：统计数据，比较次数和移动次数约为效率：统计数据，比较次数和移动次数约为n1.310.3 快速排序快速排序1、冒泡排序、冒泡排序基本思想：基本思想： 对对n个记录，依次比较相邻两个关键字，不满足条件，个记录，依次比较相邻两个关键字，不满足条件，则交换则交换-一趟冒泡排序一趟冒泡排序 对前对前n-1个记录作第二趟排序个记录作第二趟排序 重复共作重复共

14、作n-1趟。趟。void sort ( SqList &L ) for ( i = 1 ; i = L.length - 1 ; i + ) flag = FALSE ; for ( j = 1 ; j L.r j + 1 .key ) L.r j L.r j + 1 ; flag = TRUE ; if ( ! flag ) break ; 算法评价：算法评价：初始正序：初始正序： 移动次数为：移动次数为： 0比较次数为：比较次数为： n-1初始逆序：初始逆序： n -1 ( n i ) = i=1比较次数：比较次数： 1 2 n ( n - 1)移动次数：移动次数： 1 2 n (

15、 n - 1)3时间复杂度为时间复杂度为O(n2)稳定排序稳定排序2、快速排序、快速排序基本思想：通过一趟排序，将待排序记录分割成独立的两部基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序则可分别对这两部分记录进行排序，以达到整个序列有序例初始关键字： 49 38 65 97 76 13 27 50 ijPivotkey=49ji 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分别进行快速排序： ( 13)

16、 27 (38) 49 (50 65) 76 (97) 快速排序结束： 13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij初始关键字： 49 38 65 97 76 13 27 50 971365ijPivotkey=49ji27ijijijjiij49ijint Partition ( SqList &L , int low , int high ) L.r 0 = L .r low ; pivotkey = L.r low .key ; while ( low high ) while (low=pivotkey) - - hig

17、h ; L.r low = L.r high ; while (lowhigh&L.rlow.key=pivotkey) + + low ; L.rhigh = L.rlow ; L.r low = L.r 0 ; return low ;void Qsort ( SqList &L , int low , int high ) if ( low high ) pivotloc = Partition ( L , low , high ) ; Qsort ( L , low , pivotloc 1 ) ; Qsort (L , pivotloc + 1 , high ) ;

18、算法评价：算法评价：递归过程，需使用栈递归过程，需使用栈最好情况：最好情况：log2n + 1最坏情况：最坏情况：O(n)时间：有序情况最坏，每趟比较后放在原来位置上时间：有序情况最坏，每趟比较后放在原来位置上总比较次数：总比较次数： n-1 ( n i ) = i=1 1 2 n ( n - 1) n n2 2 2 2另外每次调用正好在中间位置另外每次调用正好在中间位置比较次数：比较次数：C(n) n + 2C(n/2) 2n + 4C(n/4) 3n + 8C(n/8) kn + 2kC(n/2k)令令 n=2k= n log2n + nC(1)O(n log2n )可证明平均比较次数可证

19、明平均比较次数 O(n log2n )而移动次数小于比较次数，所以总时间为而移动次数小于比较次数，所以总时间为 O(n log2n )不稳定排序不稳定排序 例：例： 5 5 110.4 选择排序选择排序1、简单选择排序、简单选择排序 基本思想：每一趟在基本思想：每一趟在n-i+1(i=1,2,n-1)个记录中选择关键个记录中选择关键 字最小的记录作为有序序列中第字最小的记录作为有序序列中第i个记录。个记录。49386597761327490 1 2 3 4 5 6 7 81349273838654997497665977697排序过程排序过程l第第1趟：通过趟：通过n-1次关键字比较，从次关键

20、字比较，从n个记录中找出关键字最小的记个记录中找出关键字最小的记录，将它与第录，将它与第1个记录交换个记录交换l第第2趟：通过趟：通过n-2次比较，从剩余的次比较，从剩余的n-1个记录中找出关键字次小的个记录中找出关键字次小的记录，将它与第记录，将它与第2个记录交换个记录交换l第第i趟：通过趟：通过n-i次比较，从剩余的次比较，从剩余的n-i+1个记录中找出关键字次小的个记录中找出关键字次小的记录，将它与第记录，将它与第i个记录交换个记录交换重复，重复，i由由1.n-1 共进行共进行n-1趟排序后，排序结束趟排序后，排序结束简单选择排序算法简单选择排序算法void SelectSort ( S

21、qList &L ) for ( i =1 ; i L.length ; + i ) j = SelectMinKey ( L , i ) ; if ( i != j ) L.r i L.r j ; 算法评价：算法评价：总比较次数：总比较次数： n-1 ( n i ) = i=1 1 2 n ( n - 1)移动次数：移动次数： 当有序时为当有序时为 0最坏每次交换最坏每次交换3(n-1)总时间复杂度：总时间复杂度：O(n2)空间复杂度为：空间复杂度为：O(1) 交换用交换用1个空间个空间稳定性稳定性 例例 2 2 1不稳定排序不稳定排序49386597761327490 1 2 3

22、4 5 6 7 82、树形选择排序、树形选择排序9749387613652749133813386513277627271327494938384949492、树形选择排序、树形选择排序比较次数：比较次数：第一次第一次 n-1 次次 以后每次以后每次 log2n 次次总比较次数：总比较次数：(n-1) + (n-1)log2n nlog2n移动次数不超过比较次数移动次数不超过比较次数所以时间复杂度为所以时间复杂度为 O(nlog2n)空间增加了空间增加了n-1个结点保存比较结果个结点保存比较结果另外排序结果需另开辟另外排序结果需另开辟n个空间个空间所以共需所以共需 n+n-1 个空间个空间不稳

23、定排序不稳定排序3、堆排序、堆排序堆的定义：堆的定义：n个元素的序列个元素的序列(k1,k2,kn)，当且仅当满足下当且仅当满足下列关系时，称之为堆列关系时，称之为堆或或(i=1,2,. n/2 )ki k2iki k2i+1ki k2iki k2i+1例 （96，83，27，38，11，9） 例 （13，38，27，50，76，65，49，97）962791138831327384965765097 可将堆序列看成完全二叉树，则堆顶元素（完全二叉可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中树的根）必为序列中n n个元素的最小值或最大值个元素的最小值或最大值堆排序：将无序序

24、列建成一个堆，得到关键字最小（或最大）堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的的记录；输出堆顶的最小（大）值后，使剩余的n-1n-1个元素重个元素重又建成一个堆，则可得到又建成一个堆，则可得到n n个元素的次小值；重复执行，得到个元素的次小值；重复执行，得到一个有序序列，这个过程叫堆排序一个有序序列，这个过程叫堆排序堆排序需解决的两个问题：堆排序需解决的两个问题：如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？第

25、二个问题解决方法第二个问题解决方法筛选筛选方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为调整过程为“筛选筛选”例13273849657650979727384965765013输出：132749389765765013输出：139749382765765013输出：13 27

26、3849502765769713输出：13 276549502738769713输出：13 27 38279797274965502738769713输出：13 27 387665502738499713输出：13 27 38 495065762738499713输出：13 27 38 499765762738495013输出：13 27 38 49 506597762738495013输出：13 27 38 49 509765762738495013输出：13 27 38 49 50 657665972738495013输出：13 27 38 49 50 659765762738495013

27、输出：13 27 38 49 50 65 769765762738495013输出：13 27 38 49 50 65 76 97第一个问题解决方法第一个问题解决方法方法：从无序序列的第方法：从无序序列的第 n/2 个元素（即此无序序列对应的完全二叉个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选树的最后一个非终端结点）起，至第一个元素止，进行反复筛选例 含8个元素的无序序列（49，38，65，97，76，13，27，50）49653827137697504965382713765097491338276576509749133827657650971

28、327384965765097typedef SqList HeapType ; void HeapAdjust ( HeapType &H , int s , int m ) rc = H.r s ; for ( j = 2 * s ; j = m ; j * = 2 ) if ( j 0 ; - - i ) HeapAdjust ( H , i , H.length ) ; for ( i = H.length ; i 1 ; - - i ) H.r 1 H.r i ; HeapAdjust ( H , 1 , i 1 ) ; 算法评价：算法评价：比较次数同树形选择排序比较次数同树

29、形选择排序时间为时间为 O(nlog2n)不稳定排序不稳定排序10.5 10.5 归并排序归并排序归并归并: :将两个或两个以上的有序表组合成一个新的有序表将两个或两个以上的有序表组合成一个新的有序表2-2-路归并排序路归并排序排序过程排序过程设初始序列含有设初始序列含有n n个记录，则可看成个记录，则可看成n n个有序的子序列，每个子个有序的子序列，每个子序列长度为序列长度为1 1两两合并，得到两两合并，得到n/2 n/2 个长度为个长度为2 2或或1 1的有序子序列的有序子序列再两两合并，再两两合并，如此重复，直至得到一个长度为如此重复，直至得到一个长度为n n的有序序的有序序列为止列为止

30、例初始关键字： 49 38 65 97 76 13 27一趟归并后： 38 49 65 97 13 76 27二趟归并后： 38 49 65 97 13 27 76三趟归并后： 13 27 38 49 65 76 97void Merge ( RcdType SR , RcdType &TR , int i , int m , int n ) for ( j = m + 1 , k = i ; i = m & j = n ; + k ) if LQ( SR i .key , SR j .key ) TR k = SR i + ; else TR k = SR j + ; if

31、( i = m ) TR k . n = SR i . m ; if ( j = n ) TR k . n = SR j . n ; void MSort ( RcdType SR , RcdType &TR1 , int s , int t ) if ( s = t ) TR1 s = SR s ; else m = ( s + t ) / 2 ; MSort ( SR , TR2 , s , m ) ; MSort ( SR , TR2 , m+1 , t ) ; Merge ( TR2 , TR1 , s , m , t ) ; void MergeSort ( SqList &

32、amp;L ) MSort ( L.r , L.r , 1 , L.length ) ;算法评价：算法评价：2路归并：路归并：第第1趟归并后有序子序列长度为趟归并后有序子序列长度为 2第第2趟归并后有序子序列长度为趟归并后有序子序列长度为 4第第i趟归并后有序子序列长度为趟归并后有序子序列长度为 2i若序列中共有若序列中共有n个元素个元素 设设 n=2i则则 需作需作i趟归并趟归并 即即 需作需作 log2n 趟归并趟归并 而每趟归并所用时间为而每趟归并所用时间为O(n)所以时间复杂度为所以时间复杂度为O(nlog2n)空间需要和待排记录等量的辅助空间空间需要和待排记录等量的辅助空间即空间复杂

33、度为即空间复杂度为O(n)稳定排序稳定排序10.6 基数排序基数排序例例 对对5252张扑克牌按以下次序排序：张扑克牌按以下次序排序： 22 33 AA 22 33 AA 22 33 AA 22 33 A A两个关键字：花色两个关键字：花色（ ） 面值面值（23A23A）并且并且“花色花色”地位高于地位高于“面值面值”多关键字排序多关键字排序多关键字排序方法多关键字排序方法最高位优先法（最高位优先法（MSD)MSD)：先对最高位关键字：先对最高位关键字k1k1（如花色）排（如花色）排序，将序列分成若干子序列，每个子序列有相同的序，将序列分成若干子序列，每个子序列有相同的k1k1值；值；然后让每

34、个子序列对次关键字然后让每个子序列对次关键字k2k2（如面值）排序，又分成（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低若干更小的子序列；依次重复，直至就每个子序列对最低位关键字位关键字kdkd排序；最后将所有子序列依次连接在一起成为排序；最后将所有子序列依次连接在一起成为一个有序序列一个有序序列最低位优先法最低位优先法(LSD)(LSD)：从最低位关键字：从最低位关键字kdkd起进行排序，然后再起进行排序，然后再对高一位的关键字排序，对高一位的关键字排序，依次重复，直至对最高位关键依次重复，直至对最高位关键字字k1k1排序后，便成为一个有序序列排序后，便成为一个有序

35、序列链式基数排序链式基数排序初始状态：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟收集：505008109930063269278083184589二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配008109278930063083184505278008109589269一趟收集：008063083109184269278505589930三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配063083269278505589505008109930063