排序&哈希&查找.ppt

《排序&哈希&查找.ppt》由会员分享，可在线阅读，更多相关《排序&哈希&查找.ppt（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、排序排序&哈希哈希&查找查找直接插入排序过程示例直接插入排序过程示例初始关键字序列3412492831525149*123456780监视哨监视哨i=21234492831525149*12i=31234492831525149*49i=41228344931525149*28i=51228313449525149*31i=61228313449525149*52i=71228313449515249*51i=8122831344949*515249*直接插入排序算法直接插入排序算法v数据结构定义#define MAXSIZE 20typedef int Keytype;/定义关键字类型为整型

2、定义关键字类型为整型typedef struct KeyType key;/关键字项关键字项 InfoType otherinfo;/其他数据项其他数据项RedType;/记录类型记录类型typedef struct RedType rMAXSIZE+1;/r0闲置或用作哨兵闲置或用作哨兵 int length;/顺序表长度顺序表长度SqList;/顺序表类型顺序表类型直接插入排序算法直接插入排序算法v以顺序表作为存储结构的直接插入排序算法void InsertSort(SqList&L)for(i=2;i=L.ength;i+)if(L.ri.key L.ri-1.key)L.r0=L.ri

3、;L.ri=L.i-1;for(j=i-2;L.r0.key L.rj.key;j-)L.rj+1=L.rj;L.rj+1=L.r0;/if/InsertSortv分析直接插入排序算法中关键字的比较次数和记录移动次数分析直接插入排序算法中关键字的比较次数和记录移动次数 for(i=2;i=L.ength;i+)if(L.ri.key L.ri-1.key)L.r0=L.ri;L.ri=L.i-1;for(j=i-2;L.r0.key L.rj.key;j-)L.rj+1=L.rj;L.rj+1=L.r0;/if if(L.ri.key L.ri-1.key)L.r0=L.ri;L.ri=L.i

4、-1;for(j=i-2;L.r0.key L.rj.key;j-)L.rj+1=L.rj;L.rj+1=L.r0;/if最好情况下最好情况下(正序正序)元素的比较次数为元素的比较次数为:n-1 元素的移动次数为元素的移动次数为:0最坏情况下最坏情况下(逆序逆序)元素的比较次数元素的比较次数:(n+2)(n-1)/2元素的元素的移动次数为：移动次数为：(n+4)(n-1)/2 交换排序交换排序1.起泡排序起泡排序(Bubble Sorting)的基本思想是：将相邻位置的关键字进行比较，若为逆序则交换之。第i趟排序过程为从L.r1至L.rn-i+1依次比较相邻两个记录的关键字，并在“逆序”时交换

5、相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。整个排序过程终止的条件是“在一趟排序过程中没有进行过交换记录的操作”起泡排序过程示例起泡排序过程示例初始关键字序列：4938659776132749*1234567838496576132749*97第一趟排序后：第一趟排序后：384965132749*7697第二趟排序后：第二趟排序后：3849132749*657697第三趟排序后：第三趟排序后：3813274949*657697第四趟排序后：第四趟排序后：1327384949*657697第五趟排序后：第五趟排序后：1327384949*657697第六趟

6、排序后：第六趟排序后：起泡排序算法起泡排序算法v以顺序表作为存储结构的起泡排序算法void BubbleSort(SqList&L)for(i=2;i=L.ength;i+)if(L.ri.key L.ri-1.key)L.r0=L.ri;L.ri=L.i-1;for(j=i-2;L.r0.key L.rj.key;j-)L.rj+1=L.rj;L.rj+1=L.r0;/if/BubbleSortv分析起泡排序算法中关键字的比较次数和记录移动次数分析起泡排序算法中关键字的比较次数和记录移动次数 for(i=1,change=TRUE;i L.length&change;+i)if(L.ri.k

7、ey L.ri-1.key)L.r0=L.ri;L.ri=L.i-1;for(j=i-2;L.r0.key L.rj.key;j-)L.rj+1=L.rj;L.rj+1=L.r0;/for /if change=FALSE;for(j=1;j L.rj+1.key)L.r0=L.rj;L.rj=L.rj+1;L.rj+1=L.r0;change=TRUE;/if最好情况下，元素的比较次数为最好情况下，元素的比较次数为:n-1 最坏情况下，交换次数为最坏情况下，交换次数为:n(n-1)/2最好情况下，元素的移动次数为最好情况下，元素的移动次数为:0最坏情况下，交换次数为：最坏情况下，交换次数为：

8、n(n-1)/238 65 97 13 27 49 551234567849049pivotij快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分快速排序中的一趟划分 38 65 97 13 27 49 551234567804949pivotijaj与与pivot比较，比较，aj小则小则ajai快速排序中的一趟划分快速排序中的一趟划分 38 65 97 13 27 49 551234567804949pivotij快速排序中的一趟划分快速排序中的一趟划分 38 65 97 13 27 49 551234567804949pivotijai与与pivot比较，比较，ai大则大则ai

9、aj；否；否则则i增增1快速排序中的一趟划分快速排序中的一趟划分 38 65 97 13 27 49 551234567804949pivotijai与与pivot比较，比较，ai大则大则ai aj；否；否则则i增增1快速排序中的一趟划分快速排序中的一趟划分 3897 13 27 49 55123456780465949pivotij快速排序中的一趟划分快速排序中的一趟划分 3897 13 27 49 55123456780465949pivotijaj与与pivot比较，比较，aj小则小则aj ai;否则，利用否则，利用j向前扫描向前扫描快速排序中的一趟划分快速排序中的一趟划分 3897 1

10、3 27 49 55123456780465949pivotijaj与与pivot比较，比较，aj小则小则aj ai;否则，利用否则，利用j向前扫描向前扫描快速排序中的一趟划分快速排序中的一趟划分 3897 13 27 49 55123456780465949pivotijaj与与pivot比较，比较，aj小则小则aj ai;否则，利用否则，利用j向前扫描向前扫描快速排序中的一趟划分快速排序中的一趟划分 38 27 97 1349 55123456780465949pivotijai与与pivot比较，比较，ai大则大则ai aj;否则，利用否则，利用i向后扫描向后扫描快速排序中的一趟划分快速

11、排序中的一趟划分 38 27 97 1349 55123456780465949pivotij利用利用i向后扫描向后扫描ai与与pivot比较，比较，ai大则大则ai aj;快速排序中的一趟划分快速排序中的一趟划分 38 2713 97 49 55123456780465949pivotij利用利用j向前扫描向前扫描快速排序中的一趟划分快速排序中的一趟划分 38 2713 97 49 55123456780465949pivotijaj与与pivot比较，比较，aj小则小则aj ai;否则，利用否则，利用j向前扫描向前扫描快速排序中的一趟划分快速排序中的一趟划分 38 27 1397 49 5

12、5123456780465949pivotijai与与pivot比较，比较，ai大则大则ai aj;否则，利用否则，利用i向后扫描向后扫描快速排序中的一趟划分快速排序中的一趟划分 38 27 1397 49 55123456780465949pivotij快速排序中的一趟划分快速排序中的一趟划分 38 27 1397 49 55123456780465949pivoti ji与与j相等时，完成一次划分相等时，完成一次划分快速排序中的一趟划分快速排序中的一趟划分 38 27 13 49 97 49 551234567804659int Partition(SqList&L,int low,int

13、 high)L.r0=L.rlow;pivot key=L.r0.key;i=low;j=high;while(ij)while(i=pivot key)j-;L.ri=L.rj;while(ij&L.ri.key=pivot key)i+;L.rj=L.ri;L.ri=L.r0;return i;/Partition快速排序快速排序int Partition(SqList&L,int low,int high).return i;/返回枢轴元素的位置返回枢轴元素的位置/Partitionvoid QSort(SqList&L,int low,int high)/对对L.rlowL.rhigh

14、的元素进行快速排序的元素进行快速排序 if(low high)pivotloc=Partition(L,low,high);/一趟划分一趟划分 QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);/if/QSort选择排序选择排序1.简单选择排序简单选择排序的基本思想是：第一趟在n个记录中选取最小记录作为有序序列的第一个记录，第二趟在n-1个记录中选取最小记录作为有序序列的第二个记录，第i趟在n-i+1个记录中选取最小的记录作为有序序列多中的第i个记录。简单选择排序过程示例简单选择排序过程示例初始关键字序列3412492831525149*1234

15、56780i=11234492831525149*i=21228493431525149*i=31228313449525149*i=41228313449525149*i=51228313449525149*i=6122831344949*5152i=7122831344949*5152return简单选择排序算法简单选择排序算法v以顺序表作为存储结构的简单选择排序算法void SelectSort(SqList&L)/对顺序表作简单选择排序对顺序表作简单选择排序 for(i=1;i L.ength;i+)for(k=i,j=i;k=L.length;k+)if (L.rk.key L.rj

16、.key)j=k;if(j!=i)L.ri L.rj;/for/SelectSortv分析简单选择排序算法中关键字的比较次数和记录移动次数分析简单选择排序算法中关键字的比较次数和记录移动次数 for(i=1;i L.ength;i+)for(k=i,j=i;k=L.length;k+)if (L.rk.key L.rj.key)j=k;if(j!=i)L.ri L.rj;/for /if for(k=i+1,j=i;k=L.length;k+)if (L.rk.key 1)MergeSort(待排序列的前半区间待排序列的前半区间)；MergeSort(待排序列的后半区间待排序列的后半区间)；已

17、排好序的前半区间和已排好序的后半区间合并成一个有序序列；已排好序的前半区间和已排好序的后半区间合并成一个有序序列；/if/MergeSortv采用顺序存储结构，对于由下标采用顺序存储结构，对于由下标st界定的一个序列，前界定的一个序列，前半区间为半区间为s (s+t)/2，后半区间为，后半区间为(s+t)/2+1 tvoid MergeSort(SqList&L,int s,int t)/归并排序归并排序 if(s t)m=(s+t)/2;MergeSort(L,s,m)；MergeSort(L,m+1,t)；Merge(L,s,m,t);/合并合并L.rsL.rm与与L.rm+1L.rt /

18、if/MergeSort二二路归并算法路归并算法v以顺序表作为存储结构void Merge(SqList&L,int i,int m,int n)/两路归并两路归并 /引入辅助空间引入辅助空间temp/Merge b=i;for(j=m+1,k=1;i=m&j=n;+k)/for/ifi if(L.ri.key L.rj.key)temp.rk=L.ri+;else temp.rk=L.rj+;for(;i=m;)temp.rk+=L.ri+;for(;j=n;)temp.rk+=L.rj+;for(i=b,k=1;i=n;)L.ri+=temp.rk+;哈希哈希 由元素的key值直接算出元素

19、的位置，这就是哈希的思想。哈希哈希下面简单介绍一下常用的哈希函数和解决冲突的办法，Hash(key)=key mod p (p (p是一个整数是一个整数)特点：以关键码除以特点：以关键码除以p的余数作为哈希地址。的余数作为哈希地址。关键：如何选取合适的关键：如何选取合适的p？技巧：若设计的哈希表长为技巧：若设计的哈希表长为m，则一般取，则一般取pm且为且为质数质数 （也可以是不包含小于（也可以是不包含小于20质因子的合数）质因子的合数）冲突的定义冲突的定义：keykey值不同，但经过值不同，但经过hashhash函数映射后的函数映射后的hashhash值相同，即它们的值相同，即它们的hashh

20、ash地址相同。地址相同。除留余数法除留余数法除留余数法除留余数法解决冲突办法解决冲突办法 开放定址法（开地址法）开放定址法（开地址法）开放定址法（开地址法）开放定址法（开地址法）设计思路：有冲突时就去寻找下一个空的哈希地址，设计思路：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。到，并将数据元素存入。具体实现：具体实现：Hi=(Hash(key)+di)mod m (1i m)其中：其中：Hash(key)为哈希函数为哈希函数 m为哈希表长度为哈希表长度 di 为增量序列为增量序列 1，2，m-1，且，且di

21、=i 线性探测法线性探测法线性探测法线性探测法含义：一旦冲突，就找附近（下一个）空地址存入。含义：一旦冲突，就找附近（下一个）空地址存入。含义：一旦冲突，就找附近（下一个）空地址存入。含义：一旦冲突，就找附近（下一个）空地址存入。关键码集为关键码集为 47，7，29，11，16，92，22，8，3，设：哈希表表长为设：哈希表表长为m=m=11；哈希函数为哈希函数为Hash(key)=key mod 11；拟用拟用线性探测法线性探测法线性探测法线性探测法处理冲突。建哈希表如下：处理冲突。建哈希表如下：解释：解释：47、7（以以及及11、16、92）均均是是由由哈哈希希函函数数得得到到的的没没有有

22、冲冲突突的的哈希地址；哈希地址；0 1 2 3 4 5 6 7 8 9 10477 例：例：291116922283 Hash(29)=7，哈希地址有冲突，需寻找下一个空的哈希地址：由，哈希地址有冲突，需寻找下一个空的哈希地址：由H1=(Hash(29)+1)mod 11=8，哈希地址哈希地址8为空，因此将为空，因此将29存入。存入。另外，另外，22、8、3同样在哈希地址上有冲突，也是由同样在哈希地址上有冲突，也是由H1找到空找到空的哈希地址的。的哈希地址的。其中其中其中其中3 3 3 3 还连续移动了两次（二次聚集）还连续移动了两次（二次聚集）还连续移动了两次（二次聚集）还连续移动了两次（二

23、次聚集）2 2 2 2、链地址法、链地址法、链地址法、链地址法(拉链法）拉链法）拉链法）拉链法）基本思想：将具有相同哈希地址的记录链成一个单链表，基本思想：将具有相同哈希地址的记录链成一个单链表，m m个个哈希地址就设哈希地址就设m m个单链表，然后用一个数组将个单链表，然后用一个数组将m个单个单链表的表头指针存储起来，形成一个动态的结构。链表的表头指针存储起来，形成一个动态的结构。设设 47,7,29,11,16,92,22,8,3,50,37,89 的哈希函的哈希函数为：数为：Hash(key)=key mod 11，用用拉拉链链法法处处理理冲冲突突，则则建建表表如右图所示。如右图所示。例

24、：例：0 1 2 3 4 5 6 7 8 91022118934737922971650810 注：有冲突的元素可以插注：有冲突的元素可以插在表尾在表尾,也可以插在表头也可以插在表头链地址法的静态链表实现 由于在ACM中不鼓励使用动态分配空间的方法，我们可以用静态链表实现一个哈希表，定义一个结构体Node struct Node int val;/变量值 int count;/变量出现次数 int next;/指向下一个哈希值相同的元素的下标 ;#define MAX_SIZE 101 Node HashMAX_SIZE;二分查找二分查找 二分查找就是先给数据排序（例如按升序排好），形成有序表

25、，然后再将key与正中元素相比，若key小，则缩小至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。将二分查找应用于枚举，衍生出了二分枚举，当所求解的函数满足单调的性质时，可以用二分枚举加快枚举速度。运算步骤运算步骤：(1)low=1,high=11,mid=6(1)low=1,high=11,mid=6，待查范围是，待查范围是 1,11 1,11；(2)(2)若若 ST.elemmid.key key ST.elemmid.key key ST.elemmid.key key，说明，说明keykey low,mid-1low,mid-1，则令：则令：high=mi

26、d1;high=mid1;重算重算 mid mid；(4)(4)若若 ST.elem mid.key=key ST.elem mid.key=key，说明查找成功，元素序号，说明查找成功，元素序号=mid;=mid;结束条件：结束条件：（1 1）查找成功）查找成功 ：ST.elemmid.key=key ST.elemmid.key=key （2 2）查找不成功）查找不成功 ：highlow highlow（意即区间长度小于（意即区间长度小于0 0）解：解：先设定先设定3个辅助标志个辅助标志:low,high,midlow,high,mid，LowLow指向待查元素指向待查元素所在区间的下界所在区间的下界highhigh指向待查元素所指向待查元素所在区间的上界在区间的上界midmid指向待查元素所在指向待查元素所在区间的中间位置区间的中间位置 已知如下已知如下11个元素的有序表：个元素的有序表：（05 13 19 21 37 56 64 75 80 88 92）,请查找关键字为请查找关键字为21 和和85的数据元素。的数据元素。显然有：显然有：mid=(low+high)/2 练习题排序：hdu1040，hdu1106，pku2388,hdu1872归并：pku1007，pku2299枚举：pku3273，hdu1551