第三章查找與排序技術1第1頁，課件共64頁，創作于2023年2月第三章查找與排序技術3.1基本查找技術查找：在一個給定的數據結構中查找某個指定的元素。通常，根據不同的數據結構，應該采用不同的查找方法：順序查找；有序表的對分查找；分塊查找。2第2頁，課件共64頁，創作于2023年2月3.1.1順序查找順序查找（順序搜索）：在線性表中順序查找指定的元素。順序查找的基本方法：從線性表的第一個元素開始，依次將線性表中的元素與被查元素進行比較，若有相等則表示找到（查找成功）；若線性表中的所有元素都與被查元素進行了比較但都不相等，則表示線性表中沒有要找到的元素（查找失敗）。3第3頁，課件共64頁，創作于2023年2月舉例說明舉例：設A是n個元素的一維數組。對于指定的輸入x，如果x在數組中，則順序找到它第一次出現處的下標；如果x在數組中，則以下標作為查找結果。否則以-1作為結果4第4頁，課件共64頁，創作于2023年2月#definen5/*n為查找表中元素個數的最大可能值*/#defineMAXLENn+1 intseqsearch(intA[],intk) { inti; i=0; A[MAXLEN-1]=k;while(A[i]!=k) i++; if(i<MAXLEN-1) returni; /*查找成功，返回被查元素在表中的相對位置*/ elsereturn-1;/*查找失敗，返回-1*/ }使用了監視哨，在查找過程中，不用每一步都去判斷是否查找結束。找到：返回元素在線性表中的存儲位置；未找到：返回-1。5第5頁，課件共64頁，創作于2023年2月#include"stdio.h" voidmain(){ intj,a[]={11,21,2,45,90},h=8; j=seqsearch(a,h); printf("%d",j);}6第6頁，課件共64頁，創作于2023年2月順序查找的效率如果線性表中的第一個元素就是被查找元素，只需要做一次比較就查找成功；如果被查的元素是線性表中的最后一個元素，或者被查元素根本不在線性表中，則需要與線性表中的所有元素進行比較（最壞情況）；平均情況：利用順序查找法在線性表中查找一個元素，大約要與線性表中一半的元素進行比較。7第7頁，課件共64頁，創作于2023年2月結論對于大的線性表來說，順序查找的效率是很低的。但在下列兩種情況下也只能采用順序查找：如果線性表為無序表（表中元素的排列是無序的），則不管是順序存儲結構還是鏈式存儲結構，都只能用順序查找表；即使是有序線性表，如果采用鏈式存儲結構，也只能用順序查找。8第8頁，課件共64頁，創作于2023年2月3.1.2有序表的對分查找有序表：線性表中的元素按值非遞減或者非遞增排列。對分查找的過程：將被查找關鍵字與線性表中間的項目進行比較，有三種可能：若被查關鍵字與表中間的項目相等，則查到，過程結束；若被查關鍵字大于表中間的項目，則取表的后半部分作為新表再去查找；若被查關鍵字小于表中間的項目，則取表的前半部分作為新表再去查找。升序降序查找成功！在后半部分查找！在前半部分查找！減半遞推！9第9頁，課件共64頁，創作于2023年2月時間效率分析對分查找是根據每次試探的結果將線性表的規模減半，并有規則地括出可能包含被查項目的部分。最壞情況：對查找需要的比較次數為n為線性表的長度。局限性：只適用于有序表，且只限于順序存儲結構。10第10頁，課件共64頁，創作于2023年2月#definen6/*n為查找表中元素個數的最大可能值*/#defineMAXLENnintbinsearch(intA[],intk) { intlow,mid,high; low=0; high=MAXLEN-1;while(low<=high) { mid=(low+high)/2;if(k==A[mid])returnmid;/*查找成功，返回被查元素在表中的相對位置*/ elseif(k>A[mid]) low=mid+1; else high=mid-1; } return-1; /*查找失敗，返回-1*/ }11第11頁，課件共64頁，創作于2023年2月#include"stdio.h" voidmain(){ intj,a[]={2,11,21,45,77,90},h=90; j=binsearch(a,h); printf("%d",j);}12第12頁，課件共64頁，創作于2023年2月3.1.3分塊查找分塊查找又稱索引查找，是順序查找的一種改進方法，用于在“分塊有序”表中進行查找。“分塊有序”表：將長度為n的線性表L分成m個子表（各子表的長度可以不等，也可以相等），且后一個子表中的每一項均大于前一個子表中的所有項。13第13頁，課件共64頁，創作于2023年2月分塊有序表分塊有序表的結構可以分為兩部分：(1)線性表本身采用順序存儲結構也可以采用鏈式存儲結構。(2)再建立一個索引表。在索引表中，對線性表的每個子表建立一個索引結點，每個結點包括兩個域：一是數據域，用于存放對應子表中的最大元素值；二是指針域，用于指示對應子表的第一個元素在整個線性表中的序號或者地址。14第14頁，課件共64頁，創作于2023年2月12345678910111213141516171815第15頁，課件共64頁，創作于2023年2月分析根據分塊有序表的結構，其查找過程可以分以下兩步進行：(1)首先查找索引表，以便確定被查元素所在的子表。由于索引表數據域中的數據是有序的且順序存儲，因此可以采用對分查找。(2)然后在相應的子表中用順序查找法進行具體的查找。結論：分塊查找的效率介于對分查找和順序查找之間。16第16頁，課件共64頁，創作于2023年2月3.2哈希表技術17第17頁，課件共64頁，創作于2023年2月傳統的查找方法601050302040查找：50比較思考：有沒有不需要比較就可以找到的方法？理想的查找是不經過任何比較，一次存取便能得到所查記錄18第18頁，課件共64頁，創作于2023年2月一種新的想法102030405060123456查找：50A【5】查找：40A【4】需要一種函數，使得F（50）＝5該函數為：F（x）＝xdiv10當我們需要查找30時，先計算：f（30)＝3再直接從A【3]中取出該記錄哈希函數哈希表19第19頁，課件共64頁，創作于2023年2月哈希查找，也稱為散列查找。它既是一種查找方法，又是一種存貯方法，稱為散列存貯。散列存貯的內存存放形式也稱為哈希表或散列表。20第20頁，課件共64頁，創作于2023年2月哈希查找是通過構造哈希函數來得到待查關鍵字的地址，從理論上來說是一種不需要用到比較的一種查找方法。21第21頁，課件共64頁，創作于2023年2月3.2.1哈希表的基本概念1.直接查找技術設表的長度為n。如果存在一個函數i＝i(k)，對于表中的任意一個元素的關鍵字k，滿足以下條件：

(1)函數值i的范圍為：1≤i≤n；

(2)對于任意的元素關鍵字k1≠k2，恒存在i(k1)≠i(k2)。 則稱此表為直接查找表。其中函數i＝i(k)稱為關鍵字k的映象函數。22第22頁，課件共64頁，創作于2023年2月直接查找技術直接查找表中各元素的關鍵字k與表項序號i之間存在著一一對應的關系；對直接查找表的查找，只需要根據映像函數i=i(k)計算出待查關鍵字項目在表中的序號i即可。23第23頁，課件共64頁，創作于2023年2月2.Hash表Hash表技術是直接查找技術的推廣，其主要目標是提高查找效率。直接查找技術要求映像函數能使得表中任意兩個不同的關鍵字其映像函數值也不同（不允許元素沖突的存在）；但在實際應用中，這一條件很難滿足。對于兩個不同的關鍵字k1≠k2有i(k1)=i(k2)，發生了元素沖突，即兩個不同元素需要存在在同一個存儲單元中。24第24頁，課件共64頁，創作于2023年2月舉例例3.2

將關鍵字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入長度為n＝12的表中。映象函數為i＝INT(k/3)＋1。關鍵字01和02發生沖突：因為兩個數值都想要存放在表的第1項中。關鍵字09和11發生沖突：因為兩個數值都想要存放在表的第4項中。25第25頁，課件共64頁，創作于2023年2月分析顯然，當有元素發生沖突時，是無法進行直接查找的。所以引入Hash表的概念：設表的長度為n。若存在一個映象函數i=i(k)，對于表中任一元素的關鍵字k，滿足1≤i(k)

≤n

，則稱此表為Hash表。并稱i(k)為關鍵字k的Hash碼。Hash表中允許沖突存在。如果在Hash表中沒有沖突存在，則Hash表就成為直接查找表。26第26頁，課件共64頁，創作于2023年2月處理表中元素的主要工作：

(1)構造合適的Hash碼，以便盡量減少表中元素沖突的次數。

(2)當表中元素發生沖突時，要進行適當的處理。3.Hash碼的構造查找關鍵字為k的元素時，計算Hash碼i(k)的工作量是影響效率的重要因素。在實際構造Hash碼時，要考慮如下兩方面的因素：(1)使各關鍵字盡可能均勻地分布在Hash表中，即Hash碼的均勻性要好，以便減少沖突發生的機會。(2)Hash碼的計算要盡量簡單。27第27頁，課件共64頁，創作于2023年2月一些簡單的Hash碼構造方法截段法分段疊加法除法乘法28第28頁，課件共64頁，創作于2023年2月⑴截段法截取法：選取與關鍵字對應的數字串中的一段（一般選取低位數）作為關鍵字的Hash碼。⑵分段疊加法將關鍵字的編碼串分割成若干段，然后把它們疊加后再進行截段。兩種疊加處理的方法：移位疊加：將分割后的幾部分低位對齊相加；間界疊加：從一端沿分割界來回折送，然后對齊相加。此法適于關鍵字的數字位數特別多的情況。29第29頁，課件共64頁，創作于2023年2月有80個記錄，關鍵字為8位十進制數，哈希地址為2位十進制數。8134653281372242813874228130136781322817813389678136853781419355…..…..

分析：只取8只取1只取3、4只取2、7、5數字分布近乎隨機所以：取任意兩位或兩位與另兩位的疊加作哈希地址⑴截段法：選取與關鍵字對應的數字串中的一段（一般選取低位數）作為關鍵字的Hash碼。30第30頁，課件共64頁，創作于2023年2月舉例:關鍵字為0442205864，哈希地址位數為4586442200410088H(key)=0088移位疊加5864022404

6092H(key)=6092間界疊加⑵分段疊加法將關鍵字分割成若干段，然后把它們疊加后再進行截段。兩種疊加處理的方法：移位疊加：將分割后的幾部分低位對齊相加；間界疊加：從一端沿分割界來回折送，然后對齊相加。31第31頁，課件共64頁，創作于2023年2月⑶除法i＝mod(k，n)其中k為關鍵字，n為Hash表的長度，而mod為求余運算符；當mod(k，n)=0時，取i=n（本節規定）。⑷乘法i＝mod(k*φ，n)

φ一般取0.618033988747，或0.6125423371，或0.6161616161。32第32頁，課件共64頁，創作于2023年2月3.2.2幾種常用的Hash表1.線性Hash表線性表是一種最簡單的Hash表。設線性Hash表的長度為m，則對線性Hash表的查找過程如下：33第33頁，課件共64頁，創作于2023年2月⑴線性Hash表的填入將關鍵字k及有關信息填入線性Hash表的步驟如下：1)計算關鍵字k的Hash碼i＝i(k)。2)檢查表中第i項的內容：若第i項為空，則將關鍵字k及有關信息填入該項；若第i項不空，則令i＝mod(i＋1，n)，轉2)繼續檢查。只要Hash表尚未填滿，最終總可以找到一個空項，將關鍵字k及有關信息填入到Hash表中。線性Hash表的沖突處理。34第34頁，課件共64頁，創作于2023年2月⑵線性Hash表的取出要在線性Hash表中取出關鍵字k的元素，其步驟如下：

1)計算關鍵字k的Hash碼i＝i(k)。

2)檢查表中第i項的內容：若第i項登記著關鍵字k，則取出該項元素即可；若第i項為空，則表示在Hash表中沒有該關鍵字的信息；若第i項不空，且登記的不是關鍵字k，則令i＝mod(i＋1，n)轉2)繼續檢查。35第35頁，課件共64頁，創作于2023年2月例3.3

將關鍵字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入長度為n＝12的線性Hash表中。設Hash碼為i＝INT(k/3)＋1。表3.2線性Hash表36第36頁，課件共64頁，創作于2023年2月分析線性表的優點：簡單。線性Hash表的缺點：⑴在線性Hash表填入的過程中，當發生沖突時，首先考慮的是下一項，因此，當Hash碼的沖突較多時，在線性Hash表中會存在“堆聚”現象，即許多關鍵字被連續登記在一起，從而會降低查找效率。⑵在線性Hash表的填入過程中，處理沖突時會帶來新的沖突。線性Hash表的填入方法是不顧后效的。37第37頁，課件共64頁，創作于2023年2月在Hash表填入過程中不顧后效，從而在填入過程中其沖突的機會在不斷增多；當Hash表填滿時，不能正常地進行查找。解決方法：將沖突的元素安排在另外的空間內，而不占用Hash表本身的空間，則就不會產生新的沖突。38第38頁，課件共64頁，創作于2023年2月3.溢出Hash表溢出Hash表包括Hash表和溢出表兩部分。在Hash表的填入過程中，將沖突的元素順序填入溢出表，而當查找過程中發現沖突時，就在溢出表中進行順序查找。溢出表是一個順序查找表。39第39頁，課件共64頁，創作于2023年2月溢出Hash表的填入將關鍵字k及有關信息填入溢出Hash表的步驟如下：1)計算關鍵字k的Hash碼i＝i(k)。2)檢查表中第i項的內容：

若第i項為空，則將關鍵字k及有關信息填入該項；

若第i項不空，則將關鍵字k及有關信息依次填入溢出表中的自由項。40第40頁，課件共64頁，創作于2023年2月溢出Hash表的取出要在溢出Hash表中取出關鍵字k的元素，其步驟如下：1)計算關鍵字k的Hash碼i＝i(k)。2)檢查表中第i項的內容：

若第i項登記著關鍵字k，則取出該項元素即可；

若第i項為空，則表示在Hash表中沒有該關鍵字

信息；

若第i項不空，且登記的不是關鍵字k，則轉入在溢出表中進行順序查找。41第41頁，課件共64頁，創作于2023年2月例3.5

將關鍵字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入長度為n＝12的溢出Hash表中。設Hash碼為i＝INT(k/3)＋1。表3.4Hash表和其溢出表沖突的元素被填入溢出表的自由項42第42頁，課件共64頁，創作于2023年2月3.3基本排序技術排序：將一個數據元素（或記錄）的任意序列，重新排列成一個按關鍵字有序的序列。43第43頁，課件共64頁，創作于2023年2月3.3.1冒泡排序與快速排序（互換排序）定義：所謂互換排序是指借助數據元素之間的互換進行排序的一種方法。冒泡排序（BubbleSort）是一種最簡單的互換排序，它是通過相鄰兩項目的比較，按一定次序互換，使表格逐步達到有序化。快速排序（QuickSort）是對冒泡排序的一種改進。44第44頁，課件共64頁，創作于2023年2月1.冒泡排序基本思想：首先對具有n個項目的無序表進行掃描，比較相鄰兩個元素的大小，若發現逆序則進行互換，由此可以使n個項目中的最大者沉到表的最后；然后對剩下的未排序好的項目再進行掃描，使它們之中的最大者又沉到表的最后；以此類推，直到將表全部排序好為止。大數在前，小數在后！45第45頁，課件共64頁，創作于2023年2月將第一個記錄的關鍵字與第二個記錄的關鍵字進行比較，若為逆序r[1].key>r[2].key，則交換；然后比較第二個記錄與第三個記錄；依次類推，直至第n-1個記錄和第n個記錄比較為止——第一趟冒泡排序，結果關鍵字最大的記錄被安置在最后一個記錄上冒泡排序46第46頁，課件共64頁，創作于2023年2月對前n-1個記錄進行第二趟冒泡排序，結果使關鍵字次大的記錄被安置在第n-1個記錄位置重復上述過程，直到“在一趟排序過程中沒有進行過交換記錄的操作”為止冒泡排序47第47頁，課件共64頁，創作于2023年2月#include”stdio.h”voidmain(){inta[10],i,j,temp;printf(”Inputl0integernumbers:”);for(i=0;i<10;i++)scanf(”%d”,&a[i]);for(i=0;i<9;i++)for(j=0;j<9-i;j++)if(a[j]>a[j+1]){temp=a[j];a[j]=a[j+1];a[j+1]=temp;}for(i=0;i<10;i++)printf(”%d”,a[i]);}48第48頁，課件共64頁，創作于2023年2月2.快速排序在冒泡排序中，每經過一次數據元素的互換只能移掉一個逆序。如果在排序過程中，每經過一次比較，使元素移動不止一個位置，這就有可能同時移掉多個逆序，達到加速排序的目的。基本思想：通過一趟分割將線性表分成兩部分，其中前一部分的所有元素值均不大于后一部分中的每一個元素值；然后對每一部分再進行分割，直到整個線性表有序為止。49第49頁，課件共64頁，創作于2023年2月具體做法從線性表中選取一個元素，設為T。然后將線性表后面小于T的元素移到前面，而前面大于T的元素移動到后面，結果就將線性表分成了兩部分（兩個子表），而T插入到其分界線的位置處。該過程被稱為線性表的分割。對分割后的各子表再按上述原則進行分割，直到所有子表為空為止，則此時的線性表就變成了有序表。50第50頁，課件共64頁，創作于2023年2月首先，在表的第一個、中間一個與最后一個元素中選取中項，設為L(k)，并將L(k)賦給T，再將表中的第一個元素與L(k)交換。然后設置兩個指針i和j分別指向表的起始與最后的位置。反復作以下兩步：

(1)將j逐漸減小，并逐次比較L(j)與T，直到發現一個L(j)＜T為止，將L(j)移到L(i)的位置上。

(2)將i逐漸增大，并逐次比較L(i)與T，直到發現一個L(i)＞T為止，將L(i)移到L(j)的位置上。上述兩個操作交替進行，直到指針i與j指向同一個位置（即i＝j）為止。51第51頁，課件共64頁，創作于2023年2月快速排序的過程2108254925*16初始關鍵字Tij08254925*1621一次交換ij08254925*1621二次交換ij08254925*1621三次交換ij08254925*1621四次交換ij08254925*1621完成一趟排序ij52第52頁，課件共64頁，創作于2023年2月例初始關鍵字：4938659776132750ijTji完成一趟排序：(273813)49(76976550)分別進行快速排序：(13)

27

（38)49(5065)

76

(97)快速排序結束：13

27

3849

5065

76

974927ijijij4965ji1349ij4997ij53第53頁，課件共64頁，創作于2023年2月3.3.2簡單插入排序與希爾排序基本思想：依次將線性表中的每一個元素插入到一個已經有序的子表中。方法：將線性表中，只包含第1個元素的子表顯然可以看成是有序表；從線性表的第2個元素開始直到最后一個元素，逐次將其中的每一個元素插入到前面已經有序的子表中；一般來說，假設線性表中前j-1個元素已經有序，現在要將線性表中第j個元素插入到前面的有序子表中。54第54頁，課件共64頁，創作于2023年2月有序1.簡單插入排序55第55頁，課件共64頁，創作于2023年2月演示有序56第56頁，課件共64頁，創作于2023年2月例49386597761327i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj977665493827

(13273849657697)排序結果：57第57頁，課件共64頁，創作于2023年2月voidinsort(intp[],intn){intj,k;Tt;for(j=1;j<