《数据结构与算法 教学课件 ppt 作者 王曙燕 chapter9 排序》由会员分享，可在线阅读，更多相关《数据结构与算法 教学课件 ppt 作者 王曙燕 chapter9 排序（58页珍藏版）》请在金锄头文库上搜索。
1、1,9.1 概述,9.2 插入类排序,9.4 选择类排序,9.3 交换类排序,9.5 归并排序,9.6 分配类排序,9.7 外部排序,9.8 算法总结,2,排序是计算机内经常进行的一种操作，其目的是将 一组“无序”的记录序列调整为“有序”的记录序列。,例如：将下列关键字序列,52, 49, 80, 36, 14, 58, 61, 23, 97, 75,调整为,14, 23, 36, 49, 52, 58, 61, 75, 80, 97,9.1 概述,3,排序的定义： 假设含n个记录的序列为 a0, a1, ， an-1 其相应的关键字序列为 K0, K1, ，Kn-1 ,这些关键字相互之间可以
2、进行比较，即在 它们之间存在着这样一个关系 ： Kp0Kp1Kpn-1,按此固有关系将上式记录序列重新排列为 ap0, ap1, ，apn-1 的操作称作排序。,9.1 概述,4,排序,内部排序,外部排序,整个排序过程不需要访问外存便能完成。,若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成。,稳定排序,不稳定排序,排序,相同关键字的领先关系在排序过程中未发生变化。,相同关键字的领先关系在排序过程中发生变化。,9.1 概述,5,内部排序的过程： 是一个逐步扩大记录的有序序列长度的过程。,经过一趟排序,有序序列区,无 序 序 列 区,有序序列区,无 序 序 列 区,内部排序的方法,
3、9.1 概述,6,基于不同的“扩大” 有序序列长度的方法，内部排序方法大致可分下列几种类型：,插入类,交换类,选择类,归并类,其它方法,9.1 概述,7,待排记录的数据类型定义如下:,#define MAXSIZE 1000 typedef int KeyType; typedef struct KeyType key; OtherType other_data; RecordType; typedef struct RcdType rMAXSIZE+1; int length; SqList;,9.1 概述,8,9.2 插入类排序,将无序子序列中的一个或几个记录“插入”到有 序序列中，从而增
4、加记录的有序子序列的长度。,有序序列a1i-1,ai,无序序列 ain-1,一趟直接插入排序的基本思想：,有序序列a1i,无序序列 ai+1n-1,9,9.2 插入类排序,实现“一趟插入排序”可分三步进行：,3将ai 插入(复制)到aj+1的位置上。,2将aj+1i中的所有记录均后移一个位置；,1在a1i-1中查找ai的插入位置， a1j.key ai.key aj+1i.key；,10,9.2 插入类排序,直接插入排序（基于顺序查找）,希尔排序（基于逐趟缩小增量）,不同的具体实现方法导致不同的算法描述,折半插入排序（基于折半查找）,表插入排序（基于链表存储）,11,9.2 插入类排序,直接插
5、入排序,利用顺序查找实现在r1i-1中查找ri的插入位置,48,62,35,77,55,14,35,98,第1 趟,48,62,r0,62,35,2,35,48,62,3,77,77,4,55,55,62,77,5,14,14,35,48,55,62,77,6,35,35,48,55,62,77,7,98,98,从ri-1起向前进行顺序查找，监视哨设置在r0；,r0 = ri;,循环结束表明ri的插入位置为 j +1,r0,j,ri,for (j=i-1; r0.keyrj.key; -j);,j=i-1,插入位置,12,9.2 插入类排序,对于在查找过程中找到的那些关键字不小于ri.key的
6、记录，并在查找的同时实现记录向后移动；,for (j=i-1; r0.keyrj.key; -j); rj+1 = rj；,上述循环结束后可以直接进行“插入” rj+1 = r0；,直接插入排序,13,令 i = 2，3，, n, 实现整个序列的排序。,for ( i=2; i=n; +i ) if (ri.keyri-1.key) 在 r1i-1中查找ri的插入位置; 插入ri ; ,9.2 插入类排序,直接插入排序,14,9.2 插入类排序,直接插入排序,void InsertionSort ( SqList +i ) if (L.ri.key L.ri-1.key) ,L.r0 = L.
7、ri; for ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; L.rj+1 = L.r0;,时间复杂度：O(n2),15,9.2 插入类排序,折半插入排序,因为 r1i-1 是一个按关键字有序的有序序列，则 可以利用折半查找实现“在r1i-1中查找ri的插 入位置”，如此实现的插入排序为折半插入排序。,i,low,high,m,high,m,high,m,low,例如:,插入 位置,L.r,16,数 据 结 构,9.2 插入类排序,第 9 章 内部排序,折半插入排序,void BiInsertionSort ( SqList &L ) ,在
8、L.r1i-1中折半查找插入位置；,for ( i=2; i=L.length; +i ) ,L.r0 = L.ri;,for ( j=i-1; j=low; -j ) L.rj+1 = L.rj;,L.rlow = L.r0;,17,9.2 插入类排序,折半插入排序,low = 1; high = i-1; while (low=high) ,m= (low+high)/2;,if (L.r0.key L.rm.key) high = m-1; else low = m+1;,在 L.r1i-1中折半查找插入位置；,18,9.2 插入类排序,希尔排序,基本思想： 对待排记录序列先作“宏观”调
9、整，再作“微观”调整。,所谓“宏观”调整，指的是，“跳跃式”的插入排序。,（又称缩小增量排序）,19,将记录序列分成若干子序列，分 别对每个子序列进行插入排序。,其中，d 称为增量，它的值在排序过程中从 大到小逐渐缩小，直至最后一趟排序减为1。,例如：将 n 个记录分成 d 个子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d ,9.2 插入类排序,希尔排序,（又称缩小增量排序）,具体做法为：,20,9.2 插入类排序,希尔排序,（又称缩小增量排序）,d1=4,17,55,05,13,d2=2,05,13,46
10、,94,d3=1,13,17,70,94,21,9.2 插入类排序,希尔排序,（又称缩小增量排序）,void ShellInsert ( SqList ,22,9.2 插入类排序,希尔排序,（又称缩小增量排序）,void ShellSort (SqList ,23,9.3 交换类排序,基本思想：,通过交换逆序元素进行排序的方法。,冒泡排序（相邻比逆法）,快速排序,通过“交换”无序序列中的记录从而得到其中关键字 最小或最大的记录，并将它加入到有序子序列中， 以此方法增加记录的有序子序列的长度。,24,9.3 交换类排序,冒泡排序（相邻比逆法）,思想：在扫描的过程中顺次比较相邻的两个 元素的大小，
11、若逆序就交换位置。,第1趟,35,62,55,77,14,77,35,77,22,98,40,98,9次,第2趟,77,35,48,55,14,35,62,22,40,8次,第n-1趟,排序结束,n-i次,第i 趟,25,9.3 交换类排序,冒泡排序（相邻比逆法）,void BubbleSort(RecordType r ,int length) n=length; for(i=1; irj+1.key) x=aj;rj=rj+1;rj+1=x; ,i+),change=1;,change=0;,change=1;,26,9.3 交换类排序,冒泡排序,时间分析:,27,9.3 交换类排序,快速
12、排序,改进冒泡排序中一次交换只能消除一个逆序 的缺点，即实现一次交换消除多个逆序。,思想： 找一个记录，以它的关键字作为“枢轴”，凡其关键字 小于枢轴的记录均移动至该记录之前，凡其关键字 大于枢轴的记录均移动至该记录之后。 即对无序的记录序列进行“一次划分”，,之后分别对分割所得两个子序列“递归”进行快速排序。,28,9.3 交换类排序,快速排序,一次划分（一趟快速排序）,r0,48,low,high,high,35,low,62,high,14,low,low,77,high,high,48,29,9.3 交换类排序,快速排序,int QKpass (RecordType r , int l
13、ow, int high) ,r0 = rlow;,while (lowhigh) ,while(low= r0.key) - high;,rlow = rhigh;,while (lowhigh ,rhigh = rlow;,rlow = r0; return low;,一趟快速排序算法,30,void QKSort(RecordType r ,int low,int high) r0=rlow; if(lowhigh) pos=QKpass(r,low,high); QKSort(r,low,pos-1); QkSort(r,pos+1,high); ,9.3 交换类排序,快速排序,算法,
14、31,9.3 交换类排序,快速排序,时间性能,假设一次划分所得枢轴位置 i=k，则对n 个记录进 行快排所需时间：,其中 Tpass(n)为对 n 个记录进行一次划分所需时间。,若待排序列中记录的关键字是随机分布的， 则 k 取 1 至 n 中任意一值的可能性相同。,T(n) = Tpass(n) + T(k-1) + T(n-k),设 Tavg(1)b,则可得结果：,O(nlogn),由此可得快速排序所需时间的平均值为：,32,9.4 选择类排序,从记录的无序子序列中“选择”关键字最小或 最大的记录，并将它加入到有序子序列中， 以此方法增加记录的有序子序列的长度。,简单选择排序,堆排序,树型选择排序,33,9.4 选择类排序,简单选择排序,i,第 1 趟,k,j,j,k,j,j,j,k,j,j,14,48,2,i,k,j,35,62,3,35,62,4,48,77,5,55,6,62,77,7,77,8,98,void 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; ,34,9.4 选择类
