数据结构第十章学习教案

1、会计学1数据结构数据结构(sh j ji u)课件第十章课件第十章第一页，共59页。29.1 9.1 概述概述9.2 9.2 插入排序插入排序9.3 9.3 交换交换(jiohun)(jiohun)排序排序9.4 9.4 选择排序选择排序9.5 9.5 归并排序归并排序9.6 9.6 基数排序基数排序第1页/共59页第二页，共59页。310.1 10.1 概述概述(i (i sh)sh)1 1、排序是计算机内经常进行的一种操作，其目的是将一组、排序是计算机内经常进行的一种操作，其目的是将一组“无序无序”的记录序列的记录序列(xli)(xli)调整为调整为“按关键字有序按关键字有序”的记录序列的

2、记录序列(xli)(xli)。52，49，80，36，14，58，61，23，97，7514，23，36，49，52，58，61，75，80，97一般情况下，一般情况下，假设假设(jish)(jish)含含n n个记录的序列为个记录的序列为R1R1，R2R2，RnRn其相应的关键字序列为其相应的关键字序列为 K1 K1，K2K2，KnKn这些关键字相互之间可以进行比较，这些关键字相互之间可以进行比较，即在它们之间存在这样一个关系：即在它们之间存在这样一个关系：Kp1=Kp2=Kp1=Kp2=Kpn36 )( 42n/2时，表示结点i为叶子结点。第34页/共59页第三十五页，共59页。36234

3、561（大根堆）（大根堆）2345617有序列有序列T1=（08, 25, 49, 46, 58, 67）和序列）和序列T2=（91, 85, 76, 66, 58, 67, 55）,判断它们判断它们(t men)是否是否 “堆堆”？（小根堆）（小根堆）（小顶堆）（小顶堆） （最小堆）（最小堆）（大顶堆）（大顶堆）（最大堆）（最大堆）第35页/共59页第三十六页，共59页。37123456例：关键字序列例：关键字序列(xli)T= (21，25，49，25*，16，08），请建大），请建大根堆。根堆。解：解：为便于理解，先将原始序列画成完全二叉树的形式：为便于理解，先将原始序列画成完全二叉树的

4、形式：注：注：终端结点（即叶子）没有任何子女，无需单独调整。终端结点（即叶子）没有任何子女，无需单独调整。 49大于大于08，不必调整；，不必调整； 25大于大于25*和和16，也不必调整；，也不必调整； 21小于小于25和和49，要调整！，要调整！而且而且21还应当向下比较！还应当向下比较！第36页/共59页第三十七页，共59页。38第37页/共59页第三十八页，共59页。39123456136542第38页/共59页第三十九页，共59页。40123456136542第39页/共59页第四十页，共59页。41123456136542第40页/共59页第四十一页，共59页。4212345613

5、6542第41页/共59页第四十二页，共59页。43123456136542第42页/共59页第四十三页，共59页。44第43页/共59页第四十四页，共59页。45第44页/共59页第四十五页，共59页。46第45页/共59页第四十六页，共59页。47第46页/共59页第四十七页，共59页。48以上两例都是典型的多关键字排序！第47页/共59页第四十八页，共59页。49第48页/共59页第四十九页，共59页。50第49页/共59页第五十页，共59页。51因为(yn wi)有分组，故此算法需递归实现。例：初始关键字序列例：初始关键字序列(xli)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、组，易编程实现！第50页/共59页第五十一页，共59页。5211552164547077027755645402112170775554，6421，117002又称散列过程！又称散列过程！第51页/共59页第五十二页，共59页。53775564540211217070，776454，552111027770645554211102第52页/共59页第五十三页，共59页。54e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9r0f e eifi+1 53079092110

8、1614485215306637738r0第53页/共59页第五十四页，共59页。55e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9530790921101614485215306637738530790921101614485215306637738r0r0第54页/共59页第五十五页，共59页。56530790921101614485215306637738e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530

9、790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9530790921101614485215306637738r0r0第55页/共59页第五十六页，共59页。57第56页/共59页第五十七页，共59页。58简单排序简单排序 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）稳定稳定 第57页/共59页第五十八页，共59页。59答：对基本答：对基本(jbn)(jbn)有序的情况，可选用堆排序、冒泡排序有序