排序哈希查找

1、排序&哈希&查找1排序的基本概念(續(xù))內部排序外部排序 插入排序（直插排序、二分排序、希爾排序） 交換排序（冒泡排序、快速排序） 選擇排序 （直選排序、樹型排序、堆排序） 歸并排序（二路歸并排序、多路歸并排序） 分配排序 （多關鍵字排序、基數排序） 多路平衡歸并排序 置換選擇排序 最佳歸并樹排序2直接插入排序過程示例初始關鍵字序列3412492831525149*123456780監(jiān)視哨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(待排序列的前半區(qū)間)； MergeSort(待排序列的

16、后半區(qū)間)； 已排好序的前半區(qū)間和已排好序的后半區(qū)間合并成一個有序序列； /if / MergeSort采用順序存儲結構，對于由下標st界定的一個序列，前半區(qū)間為s (s+t)/2，后半區(qū)間為 (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 還連續(xù)移動了兩次（二次聚集）362、鏈地址法(拉鏈法）基本思想：將具有相同哈希地址的記錄鏈成一個單鏈表，m個哈希地址就設m個單鏈表，然后用一個數組將m個單鏈表的表頭指針存儲起來，形成一個動態(tài)的結構。 設 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鏈地址法的靜態(tài)鏈表實現 由于在ACM中不鼓勵使用動態(tài)分配空間的方法，我們可以用靜態(tài)鏈表實現一個哈希表，定義一個結構體Node struct Node int val;/變量值 int count;/變量出現次數 in