1、查找 排序,查找與排序技術(shù),查找,查找：查找是在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中，根據(jù)給定的條件查找滿足條件的結(jié)點(diǎn)。不同的數(shù)據(jù)結(jié)構(gòu)采用不同的查找方法。查找的效率直接影響數(shù)據(jù)處理的效率。 查找的結(jié)果： 查找成功：找到滿足條件的結(jié)點(diǎn) 查找失?。赫也坏綕M足條件的結(jié)點(diǎn)。,查找的基本概念,關(guān)鍵字:是數(shù)據(jù)元素中可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)，比如學(xué)號(hào)、身份證號(hào)等。 查找:是根據(jù)給定的關(guān)鍵值，在一組數(shù)據(jù)中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素的過(guò)程。 確切定義：給定一個(gè)值K，在含有n個(gè)記錄的文件中進(jìn)行搜索，尋找一個(gè)其關(guān)鍵字等于給定的K值的記錄，如找到，則輸出記錄或記錄在文件中的相對(duì)位置稱查找成功；否則輸出查找不成功的信

2、息稱查找失敗。,查找方法,1.順序查找 2.二分法查找 3.分塊查找 4.散列（HASH）查找,查找方式與特點(diǎn)： 可以采用從前向后查，也可采用從后向前查的方法。 在平均情況下，大約要與表中一半以上元素進(jìn)行比較，效率較低。平均查找長(zhǎng)度較大。 在下面兩種情況下只能采取順序查找： a. 線性表為無(wú)序表（元素排列是無(wú)序的）； b. 即使是有序線性表，但采用的是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。,順序查找（線性查找） 查找過(guò)程： 對(duì)給定的一關(guān)鍵字K，從線性表的一端開始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和K的比較，直到找到關(guān)鍵字等于K的記錄或到達(dá)表的另一端。,1 . 線性表在順序存儲(chǔ)結(jié)構(gòu)下的順序查找 數(shù)據(jù)結(jié)構(gòu)： typedef stru

3、ct int key; float info; SSTable;,順序查找的算法： int Search_seq(SSTable ST , int n, int key) int i=n; ST0.key=key; while(STi.key!=key) i-； /*從表尾往前查*/ return i; ,監(jiān)視哨,使用了監(jiān)視哨，在查找過(guò)程中，不用每一步都去判斷是否查找結(jié)束。 找到：返回元素在線性表中的存儲(chǔ)位置； 未找到：返回0。,根據(jù)上述算法可知： 查找成功時(shí)的平均查找次數(shù)為： ASL=(1+2+3+4+n)/n=(n+1)/2 查找不成功時(shí)的比較次數(shù)為： n+1 則順序查找的平均查找長(zhǎng)度為：

4、 ASL=(n+1)/2+n+1)/2=(n+1)3/4 順序查找的優(yōu)點(diǎn)：算法簡(jiǎn)單，無(wú)需排序，采用順序和鏈?zhǔn)酱鎯?chǔ)均可。 缺點(diǎn)：平均查找長(zhǎng)度較大。,2. 線性表在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的順序查找 struct node int data; struct node *next; ; int searlb(struct node *h,int x) struct node *m; m=h; while(m-next!=NULL ,折半查找（二分法查找） 思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。 前提：必須在具有順序存儲(chǔ)結(jié)構(gòu)的有序表中進(jìn)行。,查找過(guò)程： 1）若中間項(xiàng)

5、的值等于x,則說(shuō)明已查到。 2）若x小于中間項(xiàng)的值，則在線性表的前半部分查找。 3）若x大于中間項(xiàng)的值，則在線性表的后半部分查找。 特點(diǎn)：比順序查找方法效率高。最壞的情況下，需要比較log2n次。,查找23和79的過(guò)程如下圖：,mid=(low+high)/2 （只舍不入）,( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08,

6、14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),折半查找的算法程序： int Search_Bin( SSTable ST , int n, int key) int low, high,mid; low=1; high=n; while(low=high) mid=(low+high)/2; if(STmid.key=key) return(mid); /*查找成功*/ else if(keySTmid.key) hig

7、h=mid-1; /*在前半?yún)^(qū)間繼續(xù)查找*/ else low=mid+1; /*在后半?yún)^(qū)間繼續(xù)查找*/ return (0); /*查找不成功*/ ,主程序：在數(shù)組中存放學(xué)生的學(xué)號(hào)和姓名，程序根據(jù)輸入學(xué)號(hào)，使用折半查找法查找學(xué)生信息。 #include typedef struct int no; char name10; Sstable; main( ) int no, j; int Search_Bin( Sstable ST , int n, int key) ; Sstable pp5=0,”0”,1,“趙剛”,2,“錢紅”,3,“孫波”, 4,“李朋”; /*pp0未用*/ sca

8、nf(“%d”, /*查找不成功*/,運(yùn)行： 輸入：3 結(jié)果：The name is 孫波 輸入：5 結(jié)果： No number,分塊查找,要求文件中記錄關(guān)鍵字“分塊有序”,即前一塊中最大關(guān)鍵字小于后一塊中最小關(guān)鍵字,而塊內(nèi)的關(guān)鍵字不一定有序。 分塊查找的基本思想 ：先抽取各塊中的最大關(guān)鍵字構(gòu)成一個(gè)索引表，由于文件中的記錄按關(guān)鍵字分塊有序，則索引表呈遞增有序狀態(tài)。查找分兩步進(jìn)行:第一步先對(duì)索引表進(jìn)行二分查找或順序查找，以確定待查記錄在哪一塊，第二步在已限定的那一塊中進(jìn)行順序查找。 用分塊查找的文件不一定分成大小相等的若干塊，塊大小及其分法可根據(jù)文件的特征來(lái)定。分塊查找不僅適用于順序方式存儲(chǔ)的順

9、序表，也適用于線性鏈表方式存儲(chǔ)的文件。,索引表,塊中的最大關(guān)鍵字,塊內(nèi)第一個(gè)記錄位置的指針,分塊查找分兩步進(jìn)行：先查索引表（索引表表長(zhǎng)較短用順序查找，較長(zhǎng)可用折半查找）確定記錄在哪一塊。然后在相應(yīng)的塊中查找。例:查找12，由索引表的第一項(xiàng)知，記錄要么在第一塊中，要么不存在，由此取到第一塊中第一個(gè)記錄位置。接著在第一塊中進(jìn)行順序查找。分塊查找效率高于順序查找，但低于折半查找。,散列（HASH）查找 直接查找技術(shù) 直接查找技術(shù)的含義： 設(shè)表的長(zhǎng)度為n，如果存在一個(gè)函數(shù)i=i(k),對(duì)于表中的任意一個(gè)元素的關(guān)鍵字k，滿足以下條件： （1）1in。 （2）對(duì)于任意的元素關(guān)鍵字k1k2，恒存在i(k1)

10、i(k2)。 則稱此表為直接查找表。其中函數(shù)i=i(k)稱為關(guān)鍵字k的映像函數(shù)。 2. 直接查找表的操作： （1）直接查找表的填入 （2）直接查找表的取出 3.直接查找表中各元素的存儲(chǔ)地址: 直接查找表的首地址（i1）m 其中：m是各元素在存儲(chǔ)空間中所占的字節(jié)。 i=i(k)。,例： 將關(guān)鍵字序列（09，31，26，19，01，13，02，11，27，16，05，21）依次填入長(zhǎng)度為n12的表中。設(shè)映像函數(shù)為i=INT(K/3)+1,其中INT為取整符。,結(jié)論：為了有效地使用散列技術(shù)，需要解決以下兩方面的問(wèn)題 構(gòu)造好的哈希函數(shù)，使沖突的現(xiàn)象盡可能的少。 設(shè)計(jì)有效的解決沖突的方法。,散列（HAS

11、H）查找 查找思想： 根據(jù)關(guān)鍵字的值，利用某個(gè)函數(shù)直接計(jì)算出元素所在的位置（也稱雜湊） 。 2. 基本概念 哈希函數(shù)：根據(jù)關(guān)鍵字而直接計(jì)算出元素所在位置的函數(shù),常用H表示。 沖突：兩個(gè)不同的關(guān)鍵字K1和K2計(jì)算出相同的存儲(chǔ)位置的現(xiàn)象稱為沖突， K1和K2互為同義詞。 哈希表：哈希表是一種存儲(chǔ)結(jié)構(gòu)，叫散列存儲(chǔ)。是通過(guò)哈希函數(shù)和解決沖突的辦法把鍵值存放在哈希表中。 3. 主要目標(biāo): 是提高查找效率，即縮短查表和填表的時(shí)間。,構(gòu)造哈希函數(shù)的方法 （1） 直接定址法取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址，即 H（K）=K 或 H（K）=A*K+B；（其中A、B為常數(shù)） 例：某公司一險(xiǎn)種投保費(fèi)交納表

12、（20年），將年份作關(guān)鍵字，哈希函數(shù)取關(guān)鍵字本身，若查找第3年應(yīng)交納的保費(fèi)，只要查找表的第3項(xiàng)即可。,（2）平方取中法取關(guān)鍵字平方后的中間幾位為哈希函數(shù)。 如：K=308，K2=94864，H（K）=486,（3） 除后余數(shù)法取關(guān)鍵字被不大于散列表表長(zhǎng)m的數(shù)p除后所得的余數(shù)為哈希地址。 即 H（K）=K MOD p （pm）,處理沖突的方法 （1） 開放定址法,設(shè)散列函數(shù) H（k）=k MOD m （m為表長(zhǎng), 設(shè)m=11) 若發(fā)生沖突，設(shè)發(fā)生沖突的地址為 p , 則沿著一個(gè)探查序列逐個(gè)探查，那么，探查的地址序列為 P+1, P+2, P+3 , m-1 , 0, 1, , P-1.,例如 :

13、 在長(zhǎng)度為11的散列表中，已填有關(guān)鍵字分別為60、17、29的記錄，現(xiàn)填入第四個(gè)記錄，其關(guān)鍵字為38。 由散列函數(shù)得散列地址為5，沖突，經(jīng)過(guò)探測(cè)，比較，最后得到地址為8。38被填到哈希表中共比較了四次，探測(cè)了三次。,按開放地址法所建的散列表的散列查找算法： #define M 100 int h(int k) return (k%97); int SearchHase(int t ,int k) int i,j=0; i=h(K); /*求得哈希地址*/ while(jM /*查找不成功*/,缺點(diǎn)：關(guān)鍵字的不同散列函數(shù)值造成探測(cè)次數(shù)多，刪除運(yùn)算較難，溢出處理復(fù)雜。因此，在處理動(dòng)態(tài)變化的表時(shí)最好

14、采用鏈地址法。,(2)鏈地址法 方法：把具有相同散列地址的鍵值存放在同一個(gè)鏈表中，稱為同義詞鏈表。 優(yōu)點(diǎn)：插入、刪除方便；缺點(diǎn)：占用存儲(chǔ)空間多。,例：一組關(guān)鍵字為（21，14，19，58，65，32，72） H(K)=K MOD 11,排 序概 述,1、排序的功能：將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排成一個(gè)按關(guān)鍵字有序的序列。 2、排序過(guò)程： 首先比較兩個(gè)關(guān)鍵字的大??； 然后將記錄從一個(gè)位置移動(dòng)到另一個(gè)位置。 3、方法： 內(nèi)排序 ：指當(dāng)文件的數(shù)據(jù)量不太大時(shí)，全部信息放在內(nèi)存中處理的排序方法。 外排序：當(dāng)文件的數(shù)據(jù)量較大時(shí)，排序過(guò)程中需要在內(nèi)、外存之間不斷地進(jìn)行數(shù)據(jù)交換才能達(dá)到排序的目的。

15、,假設(shè)待排序的記錄存放在地址連續(xù)的一組存儲(chǔ)單元中，那么這種存儲(chǔ)方式下的數(shù)據(jù)類型可描述為：,MAX,0,1,2,3,4,key,info,#define MAX 20 typedef struct int key; float otherinfo; RedType;,基本的排序方法,1、交換排序 2、插入排序 3、選擇排序 4、歸并排序與基數(shù)排序 5、排序小結(jié),插入排序,基本思想是：每步將一個(gè)待排序的記錄，按關(guān)鍵碼值的大小插入到前面已排序的適當(dāng)位置上，直到全部插完為止。 1. 直接插入排序：在排好的序列中用順序法查找插入位置，找到后將其后記錄后移一個(gè)位置，插入新記錄。排序n個(gè)記錄的文件，關(guān)鍵碼比

16、較次數(shù)為n2量級(jí)，記錄移動(dòng)個(gè)數(shù)也為n2量級(jí)。 2. 二分法插入排序：在已排好序的序列中使用二分法查找插入位置，找到后移動(dòng)其后記錄插入新記錄。關(guān)鍵字比較次數(shù)降為nlog2n量級(jí)，記錄移動(dòng)個(gè)數(shù)仍為n2量級(jí)。 3.希爾排序：將整個(gè)無(wú)序序列分割成若干小的子序列分別進(jìn)行插入排序。,直接插入排序,該算法適合于n 較小的情況，時(shí)間復(fù)雜度為O(n2).,待排元素序列：53 27 36 15 69 42 第一次排序： 27 53 36 15 69 42 第二次排序： 27 36 53 15 69 42 第三次排序： 15 27 36 53 69 42 第四次排序： 15 27 36 53 69 42 第五次排序

17、： 15 27 36 42 53 69 直接插入排序示例,對(duì)于有n個(gè)數(shù)據(jù)元素的待排序列，插入操作要進(jìn)行n-1次,void InsertSort(RedType L , int n) int i , j; for(i=2; i=n; i+) if(Li.keyLi-1.key) L0=Li; /* 作為監(jiān)視哨*/ for( j=i-1;L0.keyLj.key; j) Lj+1=Lj; /* 記錄后移*/ Lj+1=L0; /* 插入 */ ,插入算法如下： 方法:Ki與Ki-1,K i-2,K1依次比較,直到找到應(yīng)插入的位置。,折半插入排序（二分法插入排序）,(highlow ，查找結(jié)束，插入

18、位置為low 或high+1 ),( 4236 ),( 4253 ),例如，待排元素的關(guān)鍵字序列為： 15，27，36，42，53，69，80，30 在前7個(gè)記錄都已排好序的基礎(chǔ)上，利用折半插入法插入第8個(gè)記錄的排序過(guò)程： 15 27 36 42 53 69 80 30 low mid high low mid high low mid high high low 15 27 30 36 42 53 69 80,( 30 42 ),( 30 27 ),( 30 36 ),(highlow ，查找結(jié)束，插入位置為low 或high+1 ),void BInsertSort(RedType L ,

19、int n) int i, low, high, mid; for(i=2; i=high+1; j ) Lj+1=Lj; /* 記錄后移*/ Lhigh+1=L0; /* 插入*/ ,折半插入排序減少了關(guān)鍵字的比較次數(shù)，但記錄的移動(dòng)次數(shù)不變，其時(shí)間復(fù)雜度與直接插入排序相同。,/*折半后的位置*/,O(n2),選擇排序,簡(jiǎn)單選擇排序基本思想是：每次從待排序的記錄中選出關(guān)鍵字最小(或最大)的記錄，順序放在已排序的記錄序列的最后，直到全部排完為止。 堆排序的基本思想：通過(guò)調(diào)整建堆的方法，實(shí)現(xiàn)無(wú)序序列的排序過(guò)程。,1、簡(jiǎn)單選擇排序 思想：首先從1n個(gè)元素中選出關(guān)鍵字最小的記錄交換到第一個(gè)位置上。然后

20、再?gòu)牡? 個(gè)到第n個(gè)元素中選出次小的記錄交換到第二個(gè)位置上，依次類推。 時(shí)間復(fù)雜度為O(n2)， 適用于待排序元素較少的情況。,初態(tài),8 3 9 1 6,8 3 9 1 6,8 3 9 1 6,8 3 9 1 6,1 3 9 8 6,1 3 9 8 6,1 3 9 8 6,簡(jiǎn)單選擇排序的算法如下： void SelectSort( RedType L , int n) int i, j, k, t; for (i=1; i=n; +i） /*選擇第i小的元素，并交換到位*/ k=i； for(j=i+1; j=n; +j) if ( Lj.keyLk.key) k=j; /*Lk 中存放的是第

21、i小的元素*/ if(k!=i) t=Li;Li=Lk; Lk=t ; /*交換*/ ,2、堆排序：也是一種選擇排序。是具有特定條件的順序存儲(chǔ)的完全二叉樹，其特定條件是：任何一個(gè)非葉子結(jié)點(diǎn)的關(guān)鍵字大于等于（或小于等于）子女的關(guān)鍵字的值。 (1) 堆的示例,(a):堆頂元素取最大值,(b):堆頂元素取最小值,(2) 實(shí)現(xiàn)堆排序需解決兩個(gè)問(wèn)題： 如何由一個(gè)無(wú)序序列建成一個(gè)堆？ 輸出堆頂元素后，如何將剩余元素調(diào)整成一個(gè)新的堆？,(3) 輸出堆頂元素并調(diào)整建新堆的過(guò)程 ( 篩選 ),把自堆頂至葉子的調(diào)整過(guò)程稱為“篩選”。從一個(gè)無(wú)序序列建堆的過(guò)程就是一個(gè)反復(fù)“篩選”的過(guò)程。,（4）由無(wú)序序列建初始堆的過(guò)

22、程,(c): 49被篩選后的狀態(tài),(d): 56被篩選后的狀態(tài),(e): 被篩選之后建成堆,(25, 56, 49, 78, 11, 65, 41, 36),交換排序 基本思想是：兩兩比較待排序記錄的關(guān)鍵碼，并交換不滿足順序要求的偶對(duì)，直至全部滿足為止。 交換排序的特點(diǎn)在于交換。有冒泡和快速排序兩種。 起泡排序：將待排序的記錄按從后向前的順序順次兩兩比較，若為逆序則進(jìn)行交換。將序列照此方法從頭到尾處理一遍稱作一趟起泡，一趟起泡的效果是將關(guān)鍵碼值最小的記錄交換到了最前位置，即該記錄的順序起始位置。若某一趟起泡過(guò)程中沒有任何交換發(fā)生，則排序過(guò)程結(jié)束。 快速排序：對(duì)冒泡排序的改進(jìn),交 換 排 序冒泡

23、排序,思想：小的浮起，大的沉底。從左端開始比較。 第一趟：第1個(gè)與第2個(gè)比較，大則交換；第2個(gè)與第3個(gè)比較，大則交換，關(guān)鍵字最大的記錄交換到最后一個(gè)位置上； 第二趟：對(duì)前n-1個(gè)記錄進(jìn)行同樣的操作，關(guān)鍵字次大的記錄交換 到第n-1個(gè)位置上； 依次類推，則完成排序。 正序：時(shí)間復(fù)雜度為O(n) 逆序：時(shí)間復(fù)雜度為O(n2) 適合于數(shù)據(jù)較少的情況。 排序n個(gè)記錄的文件最多需要n-1趟冒泡排序。,第 六 趟 排 序 后,第 五 趟 排 序 后,第 四 趟 排 序 后,第 三 趟 排 序 后,第 二 趟 排 序 后,第 一 趟 排 序 后,初 始 關(guān) 鍵 字,思想：小的浮起，大的沉底。,最 終 結(jié) 果

24、,冒泡排序的C程序段： Void BubbleSort ( RedType L , int n ) int i, x, j=1, k=1; while (j0); k=0; for (i=1; i=n-j; i+) if (Li+1.keyLi.key) k+;x=Li; Li=Li+1; Li+1=x; /*交換*/ j+; ,思想：通過(guò)一趟排序?qū)⒋判蛄蟹殖蓛刹糠?，使其中一部分記錄的關(guān)鍵字均比另一部分小，再分別對(duì)這兩部分排序，以達(dá)到整個(gè)序列有序。 關(guān)鍵字通常取第一個(gè)記錄的值為基準(zhǔn)值。 做法：附設(shè)兩個(gè)指針low和high ，初值分別指向第一個(gè)記錄和最后一個(gè)記錄，設(shè)關(guān)鍵字為 key ，首先從

25、high所指位置起向前搜索，找到第一個(gè)小于基準(zhǔn)值的記錄與基準(zhǔn)記錄交換，然后從low 所指位置起向后搜索，找到第一個(gè)大于基準(zhǔn)值的記錄與基準(zhǔn)記錄交換，重復(fù)這兩步直至low=high為止。 時(shí)間復(fù)雜度：O(nlog2n),交 換 排 序快速排序,快速排序過(guò)程示意圖：,有序序列 6 18 23 52 67,key,初始序列 23 52 6 67 18,low,high,一次交換 18 52 6 67 23,low,high,二次交換 18 23 6 67 52,high,三次交換 18 6 23 67 52 / 完成一趟排序后分別進(jìn)行快速排序,low,high,2318,交換,2352,交換,2367, high=high-1,Low、high,low=low+1,high=high-1,236,交換,low=low +1,例題,歸并排序,初始序列 23 52 67 6 18 10 一趟歸并后 23 52