数据结构课件第十章

1、1数据结构课程的内容数据结构课程的内容29.1 9.1 概述概述9.2 9.2 插入排序插入排序9.3 9.3 交换排序交换排序9.4 9.4 选择排序选择排序9.5 9.5 归并排序归并排序9.6 9.6 基数排序基数排序310.1 10.1 概述概述1 1、排序是计算机内经常进行的一种操作，其目的是将一、排序是计算机内经常进行的一种操作，其目的是将一组组“无序无序”的记录序列调整为的记录序列调整为“按关键字有序按关键字有序”的记录序的记录序列。列。52，49，80，36，14，58，61，23，97，7514，23，36，49，52，58，61，75，80，97一般情况下，一般情况下，假设

2、含假设含n n个记录的序列为个记录的序列为r1r1，r2r2，rnrn其相应的关键字序列为其相应的关键字序列为 k1k1，k2k2，knkn这些关键字相互之间可以进行比较，这些关键字相互之间可以进行比较，即在它们之间存在这样一个关系：即在它们之间存在这样一个关系：kp1=kp2=kp1=kp2=kpn36 )( 42n/2时，表示结点i为叶子结点。36234561（大根堆）（大根堆）2345617有序列有序列t1=（08, 25, 49, 46, 58, 67）和序列）和序列t2=（91, 85, 76, 66, 58, 67, 55）,判断它们是否判断它们是否 “堆堆”？（小根堆）（小根堆）

3、（小顶堆）（小顶堆） （最小堆）（最小堆）（大顶堆）（大顶堆）（最大堆）（最大堆）37123456例：例：关键字序列关键字序列t= (21，25，49，25*，16，08），请建），请建大根堆大根堆。解：解：为便于理解，先将原始序列画成完全二叉树的形式：为便于理解，先将原始序列画成完全二叉树的形式：注：注：终端结点（即叶子）没有任何子女，无需单独调整。终端结点（即叶子）没有任何子女，无需单独调整。 49大于大于08，不必调整；，不必调整； 25大于大于25*和和16，也不必调整；，也不必调整； 21小于小于25和和49，要调整！，要调整！而且而且21还应当向下比较！还应当向下比较！383912

4、345613654240123456136542411234561365424212345613654243123456136542449.5 9.5 归并排序归并排序关键字序列关键字序列t= （21，25，49，25*，93，62，72，08，37，16，54），请给出归并排序的具体实），请给出归并排序的具体实现过程。现过程。4546因为在递归的归并排序算法中，函数因为在递归的归并排序算法中，函数merge( )做一趟两路归并做一趟两路归并排序，需要调用排序，需要调用merge ( )函数函数 n/(2*len) o(n/len) 次，函数次，函数merge( )调用调用merge( )正好

5、正好 log2n 次，而每次次，而每次merge( )要执行比要执行比较较o(len)次，所以算法总的时间复杂度为次，所以算法总的时间复杂度为o(nlog2n)。因为需要一个与原始序列同样大小的辅助序列（因为需要一个与原始序列同样大小的辅助序列（tr）。这正）。这正是此算法的缺点。是此算法的缺点。479.6 9.6 基数排序基数排序 48以上两例都是典型的多关键字排序！495051因为有分组，故此算法需递归实现。是借用是借用msdmsd方式来排序呢，还是借用方式来排序呢，还是借用lsdlsd方式？方式？例：例：初始关键字序列初始关键字序列t=（32, 13, 27, 32*, 19，33），请

6、分别），请分别用用msd和和lsd进行排序，并讨论其优缺点。进行排序，并讨论其优缺点。法法1（msd）：）：原始序列：原始序列：32, 13, 27, 32*, 19， 33 先按高位先按高位 排序：排序：（13, 19）, 27, （32, 32*，33） 再按低位再按低位排序排序 ： 13, 19 ， 27, 32, 32*, 33法法2（lsd）：）： 原始序列：原始序列： 32, 13, 27, 32*, 19 ，33 先按低位先按低位排序：排序： 32, 32*, 13, 33, 27, 19 再按高位再按高位排序：排序： 13, 19 , 27, 32, 32*, 33无需分组，易

7、编程实现！5211552164547077027755645402112170775554，6421，117002又称散列过程！又称散列过程！53排序时经过了反复的排序时经过了反复的“分配分配”和和“收集收集”过程。当对关过程。当对关键字所有的位进行扫描排序后，整个序列便从无序变为有序键字所有的位进行扫描排序后，整个序列便从无序变为有序了。了。775564540211217070，776454，55211102777064555421110254e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f

8、5 f6 f7 f8 f9r0f e eifi+1 530790921101614485215306637738r055e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9530790921101614485215306637738eifi+1 530790921101614485215306637738r0r056530790921101614485215306637738e0 e1 e2 e3 e4 e5 e6 e7 e8 e961473892148563710121

9、5530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9eifi+1 530790921101614485215306637738r0r05758各种内部排序方法的比较各种内部排序方法的比较 (教材教材p289）简单排序简单排序 o(n)o(n2) o(n2) o(1） 稳定稳定 快速排序快速排序o(nlgn )o(nlgn) o(n2) o(lgn) 不稳定不稳定 堆排序堆排序 o(nlgn )o(nlgn ) o(nlgn) o(1）不稳定不稳定 归并排序归并排序 o(nlgn ) o(nlgn ) o(nlgn) o(n）稳定稳定基数排序基数排序o(d(n+rd) o(d(n+rd) o(d(n+rd) o(rd)稳定稳定 简单选择简单选择 o(n2) o(n2) o(n2) o(1） 不稳定不稳定 直接插入直接插入 o(n) o(n2) o(n2) o(1）稳定稳定 折半插入折半插入o(nlgn )o(nlgn )o(nlgn )o(1）稳定稳定冒泡冒泡 o(n) o(n2) o(n2) o(1）稳定稳定 59讨论：讨论：若初始记录基本无序，则选用哪些排序方法比较适若初始记录基本无序，则选用哪些排序方法比较适合？若初始记录基本无序，则最好选用哪些排序方法？合？若初始记