严蔚敏数据结构C语言 原PPT课件

1、1数 据 结 构10.1 概述第10章 内部排序排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如：将下列关键字序列52, 49, 80, 36, 14, 58, 61, 23, 97, 75调整为14, 23, 36, 49, 52, 58, 61, 75, 80, 97第1页/共58页2数 据 结 构10.1 概述第10章 内部排序排序的定义：假设含n个记录的序列为 a0, a1, ， an-1 其相应的关键字序列为 K0, K1, ，Kn-1 这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 ： Kp0Kp1Kpn-1按此固有关

2、系将上式记录序列重新排列为 ap0, ap1, ，apn-1 的操作称作排序。第2页/共58页3数 据 结 构10.1 概述第10章 内部排序排序内部排序外部排序整个排序过程不需要访问外存便能完成。若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成。稳定排序不稳定排序排序相同关键字的领先关系在排序过程中未发生变化。相同关键字的领先关系在排序过程中发生变化。第3页/共58页4数 据 结 构10.1 概述第10章 内部排序内部排序的过程：是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无 序 序 列 区有序序列区无 序 序 列 区内部排序的方法第4页/共58页5数 据 结

3、 构10.1 概述第10章 内部排序基于不同的“扩大” 有序序列长度的方法，内部排序方法大致可分下列几种类型：插入类交换类选择类 归并类其它方法第5页/共58页6数 据 结 构10.1 概述第10章 内部排序待排记录的数据类型定义如下:#define MAXSIZE 1000typedef int KeyType; typedef struct KeyType key; OtherType other_data; RecordType; typedef struct RcdType rMAXSIZE+1; int length; SqList; 第6页/共58页7数 据 结 构10.2 插入类

4、排序第10章 内部排序将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。有序序列a1.i-1ai 无序序列 ai.n-1一趟直接插入排序的基本思想：有序序列a1.i无序序列 ai+1.n-1第7页/共58页8数 据 结 构10.2 插入类排序第10章 内部排序实现“一趟插入排序”可分三步进行：3将ai 插入(复制)到aj+1的位置上。2将aj+1.i中的所有记录均后移一个位置；1在a1.i-1中查找ai的插入位置， a1.j.key ai.key aj+1.i.key；第8页/共58页9数 据 结 构10.2 插入类排序第10章 内部排序直接插入排序（基于顺序

5、查找）希尔排序（基于逐趟缩小增量）不同的具体实现方法导致不同的算法描述折半插入排序（基于折半查找）表插入排序（基于链表存储）第9页/共58页10数 据 结 构10.2 插入类排序第10章 内部排序直接插入排序利用顺序查找实现在r1.i-1中查找ri的插入位置4862357755143598第1 趟4862r06235235486237777455556277514143548556277635354855627779898从ri-1起向前进行顺序查找，监视哨设置在r0；r0 = ri; 循环结束表明ri的插入位置为 j +1r0jrifor (j=i-1; r0.keyrj.key; -j);

6、 j=i-1插入位置第10页/共58页11数 据 结 构10.2 插入类排序第10章 内部排序对于在查找过程中找到的那些关键字不小于ri.key的记录，并在查找的同时实现记录向后移动；for (j=i-1; r0.keyrj.key; -j); rj+1 = rj；上述循环结束后可以直接进行“插入” rj+1 = r0；r0jrij=i-1插入位置直接插入排序第11页/共58页12令 i = 2，3，, n, 实现整个序列的排序。for ( i=2; i=n; +i ) if (ri.keyri-1.key) 在 r1.i-1中查找ri的插入位置; 插入ri ; 数 据 结 构10.2 插入类

7、排序第10章 内部排序直接插入排序第12页/共58页13数 据 结 构10.2 插入类排序第10章 内部排序直接插入排序void InsertionSort ( SqList &L ) for ( i=2; i=L.length; +i ) if (L.ri.key L.ri-1.key) L.r0 = L.ri; for ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; L.rj+1 = L.r0; 第13页/共58页14内部排序的时间分析：实现内部排序的基本操作有两个：（2）“移动”记录。（1）“比较”序列中两个关键字的大小；数 据 结 构1

8、0.2 插入类排序第10章 内部排序直接插入排序第14页/共58页15对于直接插入排序最好的情况（关键字在记录序列中顺序有序）：“比较”的次数：最坏的情况（关键字在记录序列中逆序有序）：“比较”的次数：112nni02) 1)(4() 1(2nnini“移动”的次数：“移动”的次数：2) 1)(4() 1(2nnini数 据 结 构10.2 插入类排序第10章 内部排序直接插入排序第15页/共58页16数 据 结 构10.2 插入类排序第10章 内部排序折半插入排序因为 r1.i-1 是一个按关键字有序的有序序列，则可以利用折半查找实现“在r1.i-1中查找ri的插入位置”，如此实现的插入排序

9、为折半插入排序。14 36 49 52 58 61 80 23 97 75ilowhighmhighmhighmlow例如:插入位置L.r第16页/共58页17数 据 结 构10.2 插入类排序第10章 内部排序折半插入排序void BiInsertionSort ( SqList &L ) 在 L.r1.i-1中折半查找插入位置；for ( i=2; i=low; -j ) L.rj+1 = L.rj; L.rlow = L.r0; 第17页/共58页18数 据 结 构10.2 插入类排序第10章 内部排序折半插入排序low = 1; high = i-1;while (low=high)

10、m= (low+high)/2; if (L.r0.key L.rm.key) high = m-1; else low = m+1; 在 L.r1.i-1中折半查找插入位置；第18页/共58页19数 据 结 构10.2 插入类排序第10章 内部排序希尔排序基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是，“跳跃式”的插入排序。（又称缩小增量排序）第19页/共58页20将记录序列分成若干子序列，分别对每个子序列进行插入排序。其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。例如：将 n 个记录分成 d 个子序列： R1，R1+d

11、，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 数 据 结 构10.2 插入类排序第10章 内部排序希尔排序（又称缩小增量排序）具体做法为：第20页/共58页21数 据 结 构10.2 插入类排序第10章 内部排序希尔排序（又称缩小增量排序）4655134294170570d1=4465513429417057017550513d2=2461705429455137005134694d3=1051713424655947013177094第21页/共58页22数 据 结 构10.2 插入类排序第10章 内部排序希尔排序（又称缩小增

12、量排序）void ShellInsert ( SqList &L, int dk ) for ( i=dk+1; i=n; +i ) if ( L.ri.key0&(L.r0.keyL.rj.key); j-=dk) L.rj+dk = L.rj; L.rj+dk = L.r0; 第22页/共58页23数 据 结 构10.2 插入类排序第10章 内部排序希尔排序（又称缩小增量排序）void ShellSort (SqList &L, int dlta, int t) for (k=0; kt; +t) ShellInsert(L, dltak); 第23页/共58页24数 据 结 构10.3

13、交换类排序第10章 内部排序基本思想：通过交换逆序元素进行排序的方法。冒泡排序（相邻比逆法）快速排序通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。第24页/共58页25数 据 结 构10.3 交换类排序第10章 内部排序冒泡排序（相邻比逆法）思想：在扫描的过程中顺次比较相邻的两个 元素的大小，若逆序就交换位置。48623577551435982240第1趟35625577 14773577229840989次483562551435772240第2趟7735485514356222408次第n-1趟排序结束n-i次

14、第i 趟第25页/共58页26数 据 结 构10.3 交换类排序第10章 内部排序冒泡排序（相邻比逆法）void BubbleSort(RecordType r ,int length) n=length; for(i=1; i=n-1; i+) for(j=1;jrj+1.key) x=aj;rj=rj+1;rj+1=x; 第26页/共58页27数 据 结 构10.3 交换类排序第10章 内部排序冒泡排序时间分析:情况情况序列序列起泡次数起泡次数 比较次数比较次数最最好好有有序序1n-1最最坏坏逆逆序序n-1n(n-1)/2第27页/共58页28数 据 结 构10.3 交换类排序第10章 内

15、部排序快速排序改进冒泡排序中一次交换只能消除一个逆序的缺点，即实现一次交换消除多个逆序。思想：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，凡其关键字大于枢轴的记录均移动至该记录之后。即对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。第28页/共58页29数 据 结 构10.3 交换类排序第10章 内部排序快速排序一次划分（一趟快速排序）4862357755143598r048lowhighhigh35low62high14lowlow77highhigh48第29页/共58页30数 据 结 构10.3 交换类排序第10章

16、 内部排序快速排序int QKpass (RecordType r , int low, int high) r0 = rlow; while (lowhigh) while(low= r0.key) - high; rlow = rhigh;while (lowhigh & rlow.key= r0.key) + low; rhigh = rlow;rlow = r0; return low;一趟快速排序算法第30页/共58页31void QKSort(RecordType r ,int low,int high) r0=rlow; if(lowhigh) pos=QKpass(r,low,

17、high); QKSort(r,low,pos-1); QkSort(r,pos+1,high);数 据 结 构10.3 交换类排序第10章 内部排序快速排序算法第31页/共58页32数 据 结 构10.4 选择类排序第10章 内部排序从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。简单选择排序堆排序树型选择排序第32页/共58页33数 据 结 构10.4 选择类排序第10章 内部排序简单选择排序4862357755143598i第 1 趟kjjkjjj kjj14482ikj35623356244877555662777778

18、98void SelectSort(RecordType r ,int n) n=length; for(i=1;i=n-1;i+) k=i; for(j=i+1;j=n; +j) if(rj.keyrk.key) k=j; if(k!=i) x=ri;ri=rk;rk=x; 第33页/共58页34数 据 结 构10.4 选择类排序第10章 内部排序树型选择排序是一种按锦标赛的思想进行排序的方法。49382765977649133865132738131376132727274949383849494949654949766565979776769797第34页/共58页35数 据 结 构10

19、.4 选择类排序第10章 内部排序堆排序对树型排序的进一步改进。堆是满足下列性质的数列r1, r2, ，rn：或堆的定义:12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49例如:是小顶堆12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49不是堆(小顶堆)(大顶堆)122iiiirrrr122iiiirrrr第35页/共58页36rir2i r2i+1 若将该数列视作完全二叉树，则 r2i 是 ri 的左孩子；r2i+1 是 ri 的右孩子。例如:数 据 结 构10.4 选择类排序第10章 内部排序堆排序12, 36, 27, 6

20、5, 40, 34, 98, 81, 73, 55, 4912362765403498817355491414是小顶堆不第36页/共58页37堆排序即是利用堆的特性对记录序列进行排序。例如：建大顶堆 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 交换 98 和 12重新调整为大顶堆 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 经过筛选数 据 结 构10.4 选择类排序第10章

21、 内部排序堆排序第37页/共58页381、如何由一个无序序列“建初堆”？堆排序的两个问题: 2、输出堆顶后，如何“筛选”？数 据 结 构10.4 选择类排序第10章 内部排序堆排序所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树也成为一个堆。第38页/共58页39数 据 结 构10.4 选择类排序第10章 内部排序堆排序48983577551435624898776248第39页/共58页40数 据 结 构10.4 选择类排序第10章 内部排序堆排序例如： 48, 62, 35, 77, 55, 14, 35, 984862357755143598显然不是一个

22、堆调整如何建初堆？第40页/共58页414862357755143598数 据 结 构10.4 选择类排序第10章 内部排序堆排序987798776298776248第41页/共58页429877356255143548数 据 结 构10.4 选择类排序第10章 内部排序堆排序9848987762487735776255356262145548145555354835484814351435353535351414第42页/共58页43时间复杂度分析1. 对深度为k的堆，“筛选”所需进行的关键字 比较的次数至多为2(k-1)；3. 调整“堆顶”n-1次，总共进行的关键字比较的次数 不超过 2(

23、log2(n-1)+log2(n-2)+ +log22)2n(log2n) 因此，堆排序的时间复杂度为O(nlogn)。2. 对n个关键字，建成深度为h(=log2n+1)的堆， 所需进行的关键字比较的次数至多4n；数 据 结 构10.4 选择类排序第10章 内部排序堆排序第43页/共58页44数 据 结 构10.5 归并类排序第10章 内部排序通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列归并为一个记录的有序序列。有 序 序 列 rl.n有序子序列 rl.m有序子序列 rm+1.n第44页/

24、共58页45数 据 结 构10.5 归并类排序第10章 内部排序例如：19，13，05，27，01，26，31，1613，1905，2701，2616 ，3105，13，19，2701，16，26，3101，05，13，16，19，26，27，31很少进行内排序，主要用于外排序。第45页/共58页46数 据 结 构10.6 基数排序第10章 内部排序主要利用分配和收集两种基本操作。典型的就是基数类排序。多关键字的排序链式基数排序第46页/共58页47数 据 结 构10.6 基数排序第10章 内部排序多关键字的排序最低位优先LSD法最高位优先MSD法先对K0进行排序，并按 K0 的不同值将记录序

25、列分成若干子序列之后，分别对 K1 进行排序，.， 依次类推，直至最后对最次位关键字排序完成为止。先对 Kd-1 进行排序，然后对 Kd-2 进行排序，依次类推，直至对最主位关键字 K0 排序完成为止。排序过程中不需要根据 “前一个” 关键字的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)子序列。第47页/共58页48例如:学生记录含三个关键字:系别、班号和班内的序列号，其中以系别为最主位关键字。 无序序列对K2排序对K1排序对K0排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,

26、2,153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30LSD的排序过程如下:数 据 结 构10.6 基数排序第10章 内部排序多关键字的排序第48页/共58页49数 据 结 构10.6 基数排序第10章 内部排序链式基数排序假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配-收集”的方法，其好处是不需要进行关键字间的比较。对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配-收集”的办法进行排序，称作基数排序法。第49页/共58页50例如：对下列这组关键字 209, 3

27、86, 768, 185, 247, 606, 230, 834, 539 首先按其 “个位数” 取值分别为 0, 1, , 9 “分配” 成 10 组，之后按从 0 至 9 的顺序将 它们 “收集” 在一起；然后按其 “十位数” 取值分别为 0, 1, , 9 “分配” 成 10 组，之后再按从 0 至 9 的顺序将它们“收集”在一起；最后按其“百位数”重复一遍上述操作。数 据 结 构10.6 基数排序第10章 内部排序链式基数排序第50页/共58页51在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序。具体作法为： 待排序记录以指针相链，构成一个链表；“分配” 时，按当前“关键字位”所取值，将记 录分配到不同的 “链队列” 中，每个队列中记 录的 “关键字位” 相同；“收集”时，按当前关键字位取值从小到大将 各队列首尾相链成一个链表;对每个关键字位均重复 2) 和 3) 两步。数 据 结 构10.6 基数排序第10章 内部排序链式基数排序第51页/共58页52例如：p369367167239237138230139进行第一次分配进行第一次收集f0 r0f7 r7f8 r8f9 r9p230230367 167 237367167237 138 369239139369 23