排序哈希查找

1、排序&哈希&查找1排序的基本概念(续)内部排序外部排序 插入排序（直插排序、二分排序、希尔排序） 交换排序（冒泡排序、快速排序） 选择排序 （直选排序、树型排序、堆排序） 归并排序（二路归并排序、多路归并排序） 分配排序 （多关键字排序、基数排序） 多路平衡归并排序 置换选择排序 最佳归并树排序2直接插入排序过程示例初始关键字序列3412492831525149*123456780监视哨i=21234492831525149*12i=31234492831525149*49i=41228344931525149*28i=51228313449525149*31i=612283134495251

2、49*52i=71228313449515249*51i=8122831344949*515249*3直接插入排序算法数据结构定义#define MAXSIZE 20typedef int Keytype; / 定义关键字类型为整型typedef struct KeyType key; / 关键字项 InfoType otherinfo; / 其他数据项RedType; / 记录类型typedef struct RedType rMAXSIZE+1; / r0闲置或用作哨兵 int length; / 顺序表长度SqList; / 顺序表类型4直接插入排序算法以顺序表作为存储结构的直接插入排序

3、算法void InsertSort(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 / InsertSort分析直接插入排序算法中关键字的比较次数和记录移动次数 for(i = 2; i = L.ength; i+) if (L.ri.key L.ri-1.key) L.r0 = L.ri; L.ri = L.i-1;

4、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-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 5交换排序1. 起泡排序起泡排序(

5、Bubble Sorting)的基本思想是：将相邻位置的关键字进行比较，若为逆序则交换之。第i趟排序过程为从L.r1至L.rn-i+1依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。整个排序过程终止的条件是“在一趟排序过程中没有进行过交换记录的操作”6起泡排序过程示例初始关键字序列：4938659776132749*1234567838496576132749*97第一趟排序后：384965132749*7697第二趟排序后：3849132749*657697第三趟排序后：3813274949*657697第四

6、趟排序后：1327384949*657697第五趟排序后：1327384949*657697第六趟排序后：7起泡排序算法以顺序表作为存储结构的起泡排序算法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 / BubbleSort分析起泡排序算法中关键字的比较次数和记录移动次数 for(i =

7、 1, change = TRUE; i L.length & change; +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; /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 最坏情况

8、下，交换次数为: n(n-1)/2最好情况下，元素的移动次数为:0最坏情况下，交换次数为：n(n-1)/28386597132749551234567849049pivotij快速排序中的一趟划分9快速排序中的一趟划分 386597132749551234567804949pivotijaj与pivot比较，aj小则ajai10快速排序中的一趟划分 386597132749551234567804949pivotij11快速排序中的一趟划分 386597132749551234567804949pivotijai与pivot比较，ai大则ai aj；否则i增112快速排序中的一趟划分 3865

9、97132749551234567804949pivotijai与pivot比较，ai大则ai aj；否则i增113快速排序中的一趟划分 389713274955123456780465949pivotij14快速排序中的一趟划分 389713274955123456780465949pivotijaj与pivot比较，aj小则aj ai; 否则，利用j向前扫描15快速排序中的一趟划分 389713274955123456780465949pivotijaj与pivot比较，aj小则aj ai; 否则，利用j向前扫描16快速排序中的一趟划分 38971327495512345678046594

10、9pivotijaj与pivot比较，aj小则aj ai; 否则，利用j向前扫描17快速排序中的一趟划分 382797134955123456780465949pivotijai与pivot比较，ai大则ai aj; 否则，利用i向后扫描18快速排序中的一趟划分 382797134955123456780465949pivotij利用i向后扫描ai与pivot比较，ai大则ai aj;19快速排序中的一趟划分 382713974955123456780465949pivotij利用j向前扫描20快速排序中的一趟划分 382713974955123456780465949pivotijaj与pi

11、vot比较，aj小则aj ai; 否则，利用j向前扫描21快速排序中的一趟划分 382713974955123456780465949pivotijai与pivot比较，ai大则ai aj; 否则，利用i向后扫描22快速排序中的一趟划分 382713974955123456780465949pivotij23快速排序中的一趟划分 382713974955123456780465949pivotiji与j相等时，完成一次划分24快速排序中的一趟划分 382713499749551234567804659int Partition(SqList &L,int low,int high) L.r0

12、= 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;/Partition25快速排序int Partition(SqList &L,int low,int high) . return i; /返回枢轴元素的位置/Partitionvoid QSort(SqList &L, int low, int hi

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

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

15、y L.rj.key) j = k; if (j != i) L.ri L.rj; /for / SelectSort分析简单选择排序算法中关键字的比较次数和记录移动次数 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(待排序列的

16、后半区间)； 已排好序的前半区间和已排好序的后半区间合并成一个有序序列； /if / MergeSort采用顺序存储结构，对于由下标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 /if / MergeSort31二路归并算法以顺序表作为存储结构void Mer

17、ge(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+;32哈希 由元素的key值直接

18、算出元素的位置，这就是哈希的思想。33哈希下面简单介绍一下常用的哈希函数和解决冲突的办法， Hash(key)=key mod p (p是一个整数)特点：以关键码除以p的余数作为哈希地址。关键：如何选取合适的p？技巧：若设计的哈希表长为m，则一般取pm且为质数 （也可以是不包含小于20质因子的合数）冲突的定义：key值不同，但经过hash函数映射后的hash值相同，即它们的hash地址相同。除留余数法34解决冲突办法 开放定址法（开地址法） 设计思路：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。 具体实现：Hi=(Hash(key)+di) m

19、od m ( 1i m ) 其中： Hash(key)为哈希函数 m为哈希表长度 di 为增量序列 1，2，m-1，且di=i 线性探测法含义：一旦冲突，就找附近（下一个）空地址存入。35关键码集为 47，7，29，11，16，92，22，8，3，设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11； 拟用线性探测法处理冲突。建哈希表如下：解释： 47、7（以及11、16、92）均是由哈希函数得到的没有冲突的哈希地址；0 1 2 3 4 5 6 7 8 9 10477 例：291116922283 Hash(29)=7，哈希地址有冲突，需寻找下一个空的哈希地址：由H1

20、=(Hash(29)+1) mod 11=8，哈希地址8为空，因此将29存入。 另外，22、8、3同样在哈希地址上有冲突，也是由H1找到空的哈希地址的。其中3 还连续移动了两次（二次聚集）362、链地址法(拉链法）基本思想：将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。 设 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 的哈希函数为：Hash(key)=key mod 11，用拉链法处理冲突，则建表如右图所示。 例： 0 1 2 3 4 5 6 7 8 91022118934737922971650810注：有冲突的元素可以插在表尾,也可以插在表头37链地址法的静态链表实现 由于在ACM中不鼓励使用动态分配空间的方法，我们可以用静态链表实现一个哈希表，定义一个结构体Node struct Node int val;/变量值 int count;/变量出现次数 in