1、1.4 查找與排序查找與排序查找：查找： 從大量數(shù)據(jù)中找出所需要的數(shù)據(jù)。從大量數(shù)據(jù)中找出所需要的數(shù)據(jù)。排序：排序： 將一組記錄根據(jù)要求按遞增或者將一組記錄根據(jù)要求按遞增或者遞減順序排列，以方便我們對(duì)數(shù)遞減順序排列，以方便我們對(duì)數(shù)據(jù)進(jìn)行處理。據(jù)進(jìn)行處理。一、查找關(guān)鍵字：元素的標(biāo)志，唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。關(guān)鍵字：元素的標(biāo)志，唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。查找：查找一個(gè)關(guān)鍵字等于給定值的數(shù)據(jù)元素，查找：查找一個(gè)關(guān)鍵字等于給定值的數(shù)據(jù)元素，即按關(guān)鍵字查找。即按關(guān)鍵字查找。查找表：待查數(shù)據(jù)元素的集合。查找表：待查數(shù)據(jù)元素的集合。查找方法：順序查找、折半查找、分塊查找、哈查找方法：順序查找、折半查找、分塊查找、哈

2、希查找等。希查找等。查找查找效率：與查找表中數(shù)據(jù)元素的組織形式以及效率：與查找表中數(shù)據(jù)元素的組織形式以及使用的查找方法密切相關(guān)。使用的查找方法密切相關(guān)。評(píng)價(jià)依據(jù)：最多、最少和平均評(píng)價(jià)依據(jù)：最多、最少和平均比較次數(shù)。比較次數(shù)。基本基本思想：從線性表的第一個(gè)數(shù)據(jù)元素開始查找，思想：從線性表的第一個(gè)數(shù)據(jù)元素開始查找，依次將線性表中的元素與被查找元素進(jìn)行比較，若依次將線性表中的元素與被查找元素進(jìn)行比較，若相等則查找成功；若直到線性表結(jié)束都未找到被查相等則查找成功；若直到線性表結(jié)束都未找到被查找元素則查找失敗。找元素則查找失敗。應(yīng)用：無序表，無論順序存儲(chǔ)還是鏈接存儲(chǔ)，都應(yīng)用：無序表，無論順序存儲(chǔ)還是鏈接

3、存儲(chǔ)，都只能用順序查找；有序表鏈接存儲(chǔ)也只能用順序查只能用順序查找；有序表鏈接存儲(chǔ)也只能用順序查找。找。比較次數(shù)：比較次數(shù)：最少最少1次；最多次；最多n次。次。1 1、順序查找、順序查找/*在長度在長度為為length的順序表中順序查找關(guān)鍵字等于的順序表中順序查找關(guān)鍵字等于key的的元素，若找到，返回元素索引號(hào)，否則，返回元素，若找到，返回元素索引號(hào)，否則，返回-1*/int seq_search(int table , int length, int key)int i = 0;while(tablei != key & i length) i+; if ( i = length)

4、i = -1;return( i );順序查找的平均查找長度：順序查找的平均查找長度：= Pi Ci = 2n+1i=1nn：表中元素個(gè)數(shù)：表中元素個(gè)數(shù)Pi：查找第：查找第i個(gè)數(shù)據(jù)元素的概率個(gè)數(shù)據(jù)元素的概率Ci：查到第：查到第i個(gè)數(shù)據(jù)元素時(shí)需進(jìn)行的比較次數(shù)個(gè)數(shù)據(jù)元素時(shí)需進(jìn)行的比較次數(shù)順序查找時(shí)：順序查找時(shí)：查找概率相同，查找概率相同， Pi=查找次數(shù)，查找次數(shù)，Ci = in1基本思想：基本思想：1）先確定待查記錄所在的范圍）先確定待查記錄所在的范圍2）逐步縮小范圍直到查找成功或失?。┲鸩娇s小范圍直到查找成功或失敗給定的給定的key與與km比較：比較：keykm, 取取mid+1, high依

5、此類推依此類推lowhighmidk1 km key ) high = mid - 1;else if (中間值中間值 = key ) 找到找到;else low = mid + 1;重復(fù)此過重復(fù)此過程，直到程，直到找到或找找到或找不到為止不到為止int binary_search( int list, int length, int key )int low, high, mid;low = 0;high = length 1;while ( low key) high = mid-1; else low = mid + 1;return(-1);/*在長度為在長度為length的順序表中折

6、半查找關(guān)鍵字等于的順序表中折半查找關(guān)鍵字等于key的元素，的元素，若找到，返回元素索引號(hào)，否則，返回若找到，返回元素索引號(hào)，否則，返回-1*/折半查找的平均查找長度：折半查找的平均查找長度：=n1(1+22+43+2k(log2n + 1)log2(n1)1優(yōu)點(diǎn)：優(yōu)點(diǎn)：比較次數(shù)少、查找速度快比較次數(shù)少、查找速度快 適用場合：適用場合：順序順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)的有序有序查找表查找表又稱索引表的順序查找又稱索引表的順序查找索引順序查找索引順序查找 基本思想：基本思想： 1）對(duì)數(shù)據(jù)元素分塊，）對(duì)數(shù)據(jù)元素分塊，塊內(nèi)無序，塊間有序塊內(nèi)無序，塊間有序 2）建立一個(gè)索引表，為每個(gè)塊建立一個(gè)索引項(xiàng)，）建立一

7、個(gè)索引表，為每個(gè)塊建立一個(gè)索引項(xiàng)，指出該塊內(nèi)的最大（或最?。╆P(guān)鍵字以及該塊中第一指出該塊內(nèi)的最大（或最?。╆P(guān)鍵字以及該塊中第一個(gè)數(shù)據(jù)元素在表中的位置個(gè)數(shù)據(jù)元素在表中的位置索引表按關(guān)鍵字有序索引表按關(guān)鍵字有序 3）查找時(shí)，先查索引表確定待查元素所在的塊，）查找時(shí)，先查索引表確定待查元素所在的塊，再在塊內(nèi)順序查找。再在塊內(nèi)順序查找。3 3、分塊查找、分塊查找例：例：17, 23, 15, 9, 21, 28, 34, 40, 54, 25, 90, 60, 72, 58, 86 第第1塊塊 第第2塊塊 第第3塊塊1190654123索引表索引表(index)908625282117table4 4

8、、樹表查找（動(dòng)態(tài)查找）、樹表查找（動(dòng)態(tài)查找） 用二叉排序樹存儲(chǔ)查找表中的數(shù)據(jù)元素用二叉排序樹存儲(chǔ)查找表中的數(shù)據(jù)元素基本思想：基本思想：利用二叉排序樹查找利用二叉排序樹查找1）將給定的）將給定的key先與根結(jié)點(diǎn)比較，若相等則查找成功；先與根結(jié)點(diǎn)比較，若相等則查找成功； 2）若）若給定的給定的key根結(jié)點(diǎn)，則與左子樹根結(jié)點(diǎn)比較根結(jié)點(diǎn)，則與左子樹根結(jié)點(diǎn)比較，反之，反之與右與右子樹子樹根結(jié)點(diǎn)比較。遞歸進(jìn)行根結(jié)點(diǎn)比較。遞歸進(jìn)行直到直到查找成功或失敗。查找成功或失敗。平均查找長度取決于二叉排序樹的深度平均查找長度取決于二叉排序樹的深度最好最好 log2n1最壞最壞 (n + 1)/2又稱散列查找又稱散列查

9、找根據(jù)關(guān)鍵字，進(jìn)行運(yùn)算，直接取得元素存儲(chǔ)位置根據(jù)關(guān)鍵字，進(jìn)行運(yùn)算，直接取得元素存儲(chǔ)位置keyhash(key)元素在線性表元素在線性表中的位置中的位置關(guān)鍵字空間關(guān)鍵字空間hash運(yùn)算運(yùn)算映射映射地址空間地址空間不需任何比較就可直接取得所查元素不需任何比較就可直接取得所查元素平均查找效率：平均查找效率：15 5、哈希查找、哈希查找哈希造表（散列）要解決的關(guān)鍵問題：哈希造表（散列）要解決的關(guān)鍵問題：構(gòu)造一個(gè)哈希函數(shù)。構(gòu)造一個(gè)哈希函數(shù)。進(jìn)行沖突處理，使不同的關(guān)鍵字對(duì)應(yīng)不同的進(jìn)行沖突處理，使不同的關(guān)鍵字對(duì)應(yīng)不同的存儲(chǔ)位置。存儲(chǔ)位置。哈希函數(shù)常用的構(gòu)造方法：哈希函數(shù)常用的構(gòu)造方法：直接定址法：取關(guān)鍵字或

10、取關(guān)鍵字的某個(gè)線性函數(shù)直接定址法：取關(guān)鍵字或取關(guān)鍵字的某個(gè)線性函數(shù)值為哈希地址。值為哈希地址。即：即： hashk= k 或或hashk= ak+b地址集合等于關(guān)鍵字地址集合等于關(guān)鍵字集合，不會(huì)發(fā)生沖突集合，不會(huì)發(fā)生沖突實(shí)際中很少應(yīng)用實(shí)際中很少應(yīng)用截段法：從關(guān)鍵字中截取一段作為哈希地址截段法：從關(guān)鍵字中截取一段作為哈希地址 例：關(guān)鍵字為學(xué)號(hào)，可從關(guān)鍵字中截取后三位例：關(guān)鍵字為學(xué)號(hào)，可從關(guān)鍵字中截取后三位作為元素在表格中的存放位置（哈希地址）。作為元素在表格中的存放位置（哈希地址）。平方取中法：平方取中法：關(guān)鍵字平方后取中間幾位為哈希地址。關(guān)鍵字平方后取中間幾位為哈希地址。取的位數(shù)由表長決定。取

11、的位數(shù)由表長決定。例：關(guān)鍵字例：關(guān)鍵字key:11052501 11052502 01110525 02110525 表長表長m = 1000則：則： 11052501 平方后等于平方后等于122157778355001，取中間三位取中間三位778為哈希地址。為哈希地址。除留余數(shù)法：除留余數(shù)法： 選擇數(shù)選擇數(shù)n哈希表長哈希表長m，取關(guān)鍵字被數(shù)，取關(guān)鍵字被數(shù) n 除后所除后所得余數(shù)為哈希地址，得余數(shù)為哈希地址，hashk = k mod n, n m 最簡單、最常用最簡單、最常用折疊法：折疊法： 將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分位數(shù)可不同），然后

12、取這幾部分的疊加和為哈希分位數(shù)可不同），然后取這幾部分的疊加和為哈希地址。地址。沖突處理：沖突處理： 沖突：指不同的關(guān)鍵字映射到同一地址，即：沖突：指不同的關(guān)鍵字映射到同一地址，即：hash(key1)=hash(key2) 沖突處理：為發(fā)生沖突的關(guān)鍵字找到另一個(gè)空沖突處理：為發(fā)生沖突的關(guān)鍵字找到另一個(gè)空閑的哈希地址。閑的哈希地址。大范圍大范圍元素元素key小范圍小范圍元素地址元素地址哈希函數(shù)哈希函數(shù)映射映射地址沖突地址沖突hash(k1)=hash(k2)hash(k3)=hash(k6)=hash(k8)常用的沖突處理方法：常用的沖突處理方法：鏈地址法：（鏈表結(jié)構(gòu)）鏈地址法：（鏈表結(jié)構(gòu)）

13、將所有哈希地址相同的元素用鏈表連接起來將所有哈希地址相同的元素用鏈表連接起來k10k31k42k53k74k6k2k8ASL = (5+2*2+3)/8 = 1.5開放地址法：開放地址法： 當(dāng)哈希地址沖突時(shí)，按某個(gè)序列改變地址，直當(dāng)哈希地址沖突時(shí)，按某個(gè)序列改變地址，直到在哈希表中找到一個(gè)空閑地址為止。到在哈希表中找到一個(gè)空閑地址為止。 hashi(k)=(hash(k) + di) mod m關(guān)鍵字關(guān)鍵字k的直接哈的直接哈希地址希地址探測時(shí)的探測時(shí)的地址增量地址增量哈希表的哈希表的長度長度di可有不同的取法，如：可有不同的取法，如：di= 1，2，3，4，5，di= -1，-2，-3，-4，

14、-5， 哈希查找時(shí)，當(dāng)發(fā)現(xiàn)當(dāng)前哈希查找時(shí)，當(dāng)發(fā)現(xiàn)當(dāng)前hash地址里存放的不是地址里存放的不是所需元素，就按照構(gòu)造哈希表時(shí)選取的序列改變地址，所需元素，就按照構(gòu)造哈希表時(shí)選取的序列改變地址，逐個(gè)探測，直到找到所需元素。逐個(gè)探測，直到找到所需元素。例：例： 對(duì)對(duì)di=1，2，3，4， 序列序列例：例： 一組關(guān)鍵字與其對(duì)應(yīng)的哈希地址如下所示：一組關(guān)鍵字與其對(duì)應(yīng)的哈希地址如下所示：key:ab cd ef de hi gh mlhash(key): 4 6 1 4 7 6 5選取序列選取序列di= -1，-2，-3，-4， 構(gòu)造哈希表構(gòu)造哈希表構(gòu)造過程：構(gòu)造過程：12345678ab12345678c

15、d12345678ef12345678de12345678de與與ab沖突，地址減一，探測沖突，地址減一，探測hi12345678gh與與cd沖突，地址減一，探測沖突，地址減一，探測gh12345678ml12345678ASL = (4+2*2+4)/7 = 12/7二、排 序排序：排序：又稱分類，是將一組元素按照它們的排序又稱分類，是將一組元素按照它們的排序碼大小進(jìn)行遞增或遞減排列的運(yùn)算方法。碼大小進(jìn)行遞增或遞減排列的運(yùn)算方法。排序碼：排序碼：排序的依據(jù)，不一定是關(guān)鍵字，是元素排序的依據(jù)，不一定是關(guān)鍵字，是元素中的一個(gè)或多個(gè)字段，不同元素排序碼可以相同。中的一個(gè)或多個(gè)字段，不同元素排序碼可

16、以相同。排序算法的穩(wěn)定性：排序算法的穩(wěn)定性： 對(duì)具有相同排序碼的元素，若排序后元素的相對(duì)具有相同排序碼的元素，若排序后元素的相對(duì)位置保持不變，則算法是穩(wěn)定的。否則，算法不對(duì)位置保持不變，則算法是穩(wěn)定的。否則，算法不穩(wěn)定。穩(wěn)定。！算法是否穩(wěn)定有時(shí)與具體實(shí)現(xiàn)有關(guān)。算法是否穩(wěn)定有時(shí)與具體實(shí)現(xiàn)有關(guān)。內(nèi)部排序：內(nèi)部排序：整個(gè)排序過程在計(jì)算機(jī)內(nèi)存中進(jìn)行；整個(gè)排序過程在計(jì)算機(jī)內(nèi)存中進(jìn)行； 外部排序：外部排序：既使用內(nèi)存，同時(shí)又使用外存的排序。既使用內(nèi)存，同時(shí)又使用外存的排序。衡量衡量排序算法的效率：排序算法的效率： 對(duì)內(nèi)部排序：開銷在元素的比較和移動(dòng)上；對(duì)內(nèi)部排序：開銷在元素的比較和移動(dòng)上； 對(duì)外部排序：開

17、銷不僅在元素的比較和移動(dòng)上，對(duì)外部排序：開銷不僅在元素的比較和移動(dòng)上，更多的開銷在對(duì)外存的訪問上。更多的開銷在對(duì)外存的訪問上?；舅枷牖舅枷耄翰粩嘣诖判蛐蛄校o序區(qū)）中按不斷在待排序序列（無序區(qū)）中按排排序碼序碼遞增（或遞減）遞增（或遞減）依依次選擇記錄，放入有序區(qū)中，次選擇記錄，放入有序區(qū)中，逐漸擴(kuò)大有序區(qū)，直到整個(gè)記錄均有序?yàn)橹埂Ｖ饾u擴(kuò)大有序區(qū)，直到整個(gè)記錄均有序?yàn)橹埂＿^程：過程： 直接在原表中操作：從表中選出最小的元素與表直接在原表中操作：從表中選出最小的元素與表首元素互換，再從剩下的表中選出最小的元素與第首元素互換，再從剩下的表中選出最小的元素與第二個(gè)元素互換，依此類推。二個(gè)元素互

18、換，依此類推。1、簡單選擇排序、簡單選擇排序設(shè)序列：設(shè)序列： 5, 4, 12, 20, 27, 3, 1 排序過程為：排序過程為：i=0： 5，4，12，20，27，3，1 i=1： 1，4，12，20，27，3，5 i=2： 1，3，12，20，27，4，5 i=3： 1，3，4，20，27，12，5 i=4： 1，3，4，5，27，12，20 i=5： 1，3，4，5，12，27，20 結(jié)果：結(jié)果： 1，3，4，5，12，20，27 算法描述算法描述：先在無序表中找到最小元素先在無序表中找到最小元素最小元素與無序表表首元素交換位置最小元素與無序表表首元素交換位置無序表：無序表：i+1，

19、，n-1 有序表：有序表：0， ，i /*在無序表中找最小元素的算法：在無序表中找最小元素的算法：*/ small=i;j=i+1;while(jlistj)small=j;j+; /*small為最小元素的下標(biāo)為最小元素的下標(biāo)*/void straight_select_sort(int list, int n) int i, j, small; for(i=0; in-1; i+) small=i; for(j=i+1; jlistj) small=j; if(small!=i)temp=listsmall; listsmall=listi; listi=temp; /*需需n-1趟選擇排

20、序趟選擇排序*/*最小元素最小元素與無序表中與無序表中第一個(gè)元素第一個(gè)元素互換位置互換位置*/算法分析算法分析算法由兩層循環(huán)構(gòu)成，外層循環(huán)表示共需進(jìn)算法由兩層循環(huán)構(gòu)成，外層循環(huán)表示共需進(jìn)行行n-1n-1趟排序，內(nèi)層循環(huán)表示每進(jìn)行一趟排序趟排序，內(nèi)層循環(huán)表示每進(jìn)行一趟排序需要進(jìn)行的記錄排序字間的比較。需要進(jìn)行的記錄排序字間的比較。 比較次數(shù)：比較次數(shù)：n(n-1)/2n(n-1)/2 移動(dòng)次數(shù)：最壞情況下為移動(dòng)次數(shù)：最壞情況下為3(n-1)3(n-1)所以總的時(shí)間復(fù)雜度為：所以總的時(shí)間復(fù)雜度為：O(nO(n2 2) )空間復(fù)雜度為：空間復(fù)雜度為：O(1) O(1) 交換記錄用交換記錄用穩(wěn)定性：穩(wěn)

21、定性：不穩(wěn)定不穩(wěn)定基本思想：基本思想：從原表中取一個(gè)元素插入到已排好序從原表中取一個(gè)元素插入到已排好序的表中，得到一個(gè)新的、元素個(gè)數(shù)增的表中，得到一個(gè)新的、元素個(gè)數(shù)增1的有序表的有序表。算法描述：算法描述：將原表分為已排序表和未排序表：將原表分為已排序表和未排序表：已排序表：已排序表：R1 R2 Ri-1未排序表：未排序表：Ri Ri+1 Rn 每次從未排序表中取出表頭元素按排序關(guān)每次從未排序表中取出表頭元素按排序關(guān)系插入到排序表中；當(dāng)未排序表為空時(shí)，排序結(jié)束。系插入到排序表中；當(dāng)未排序表為空時(shí)，排序結(jié)束。 需進(jìn)行（需進(jìn)行（n-1）趟插入排序）趟插入排序2、直接插入排序、直接插入排序 插入運(yùn)算

22、為從后向前比較：先取插入運(yùn)算為從后向前比較：先取Ri與與Ri-1比比較，若較，若RiRi-1，則，則Ri-1后移一個(gè)位置，再取下一個(gè)后移一個(gè)位置，再取下一個(gè)元素元素Ri-2與與Ri比較，依此類推，直到找到比較，依此類推，直到找到 插入位置，插入位置，就在該位置插入元素。就在該位置插入元素。temp=datai;while(temp =0)dataj+1=dataj;j-;dataj+1=temp;/*找插入位置找插入位置*/*元素后移一個(gè)位置元素后移一個(gè)位置*/*取下一個(gè)元素比較取下一個(gè)元素比較*/*插入元素插入元素*/void linear_insert_sort(int list, int

23、 n) int i, j, temp; for(i=1; in; i+) j=i-1; temp=listi; while( temp = 0) listj+1=listj; j-; listj+1=temp; /*從第二個(gè)元素開始，每從第二個(gè)元素開始，每循環(huán)一次插入一個(gè)元素循環(huán)一次插入一個(gè)元素*/例：待排序列：例：待排序列： 54 34 17 28 63 92 48 82 75n-1趟排序依次為：趟排序依次為：初始狀態(tài)：初始狀態(tài)：54 34 17 28 63 92 48 82 75(i=1,34) 34 54 17 28 63 92 48 82 75(i=2,17)17 34 54 28 6

24、3 92 48 82 75(i=3,28)17 28 34 54 63 92 48 82 75(i=4,63)17 28 34 54 63 92 48 82 75(i=5,92)17 28 34 54 63 92 48 82 75(i=6,48)17 28 34 48 54 63 92 82 75(i=7,82)17 28 34 48 54 63 82 92 75(i=8,75)17 28 34 48 54 63 75 82 92算法特點(diǎn)：算法特點(diǎn)： 簡單，容易實(shí)現(xiàn)，適于待排元素簡單，容易實(shí)現(xiàn)，適于待排元素n 很少或基本很少或基本有序的情況。有序的情況。穩(wěn)定性：穩(wěn)定性：穩(wěn)定穩(wěn)定排序效率：排序效

25、率：共進(jìn)行共進(jìn)行n-1次循環(huán)排序，每次可能搬移多個(gè)元素。次循環(huán)排序，每次可能搬移多個(gè)元素。最好情況：比較次數(shù)最好情況：比較次數(shù)n-1；移動(dòng)次數(shù)；移動(dòng)次數(shù)2(n-1)最壞情況：比較最壞情況：比較n(n-1)/2；移動(dòng)；移動(dòng)平均：約平均：約n2/4 O(n2) (i+2) i=1n-1基本思想：基本思想： 從表首元素開始，兩兩比較，若從表首元素開始，兩兩比較，若 RiRi+1 ，則，則兩個(gè)元素交換。經(jīng)過一趟冒泡排序后，具有最大兩個(gè)元素交換。經(jīng)過一趟冒泡排序后，具有最大排序碼的數(shù)據(jù)元素就移到了最后，而具有排序碼的數(shù)據(jù)元素就移到了最后，而具有小小排序排序碼碼的的數(shù)據(jù)元素?cái)?shù)據(jù)元素則像氣泡一樣逐漸上浮則像

26、氣泡一樣逐漸上?。?再對(duì)前再對(duì)前n-1個(gè)數(shù)據(jù)元素冒泡排序，依此類推，個(gè)數(shù)據(jù)元素冒泡排序，依此類推，直到在一趟冒泡排序過程中沒有進(jìn)行過交換元素直到在一趟冒泡排序過程中沒有進(jìn)行過交換元素的操作，整個(gè)排序過程結(jié)束。的操作，整個(gè)排序過程結(jié)束。3、冒泡排序（、冒泡排序（bubble sort）冒泡排序例：冒泡排序例：初始狀態(tài)初始狀態(tài)65 97 76 13 27 49 58第第1趟趟65 76 13 27 49 58 97 第第2趟趟65 13 27 49 58 76 97第第3趟趟13 27 49 58 65 76 97第第4趟趟13 27 49 58 65 76 97第第5趟趟13 27 49 58

27、65 76 97第第6趟趟13 27 49 58 65 76 97算法算法描述描述：1）逐個(gè)比較、交換：）逐個(gè)比較、交換：for ( i=0; i datai+1) datai datai+1 2）設(shè)交換標(biāo)志）設(shè)交換標(biāo)志change表示在一趟排序中有否進(jìn)行表示在一趟排序中有否進(jìn)行過交換：過交換：change =10元素交換過元素交換過元素沒有交換過元素沒有交換過3）多趟冒泡排序的框架：）多趟冒泡排序的框架：while( bound0 & change= =1 )void bubble_sort( int list, int n )int change =1; int bound=n 1

28、; while( bound0 & change=1) change = 0; for(i=0; i listi+1) temp = listi; listi = listi+1; listi+1 = temp; change = 1; bound=bound-1; /*交換*/ 算法也可寫成：算法也可寫成： BubbSort(int list, int n) int i, j, temp; for (i=0;in-1;i+) for (j=i+1;jlistj) temp = listi; listi = listj; listj = temp; 排序效率排序效率： 在一趟冒泡排序中

29、同時(shí)完成了較小元素的上冒在一趟冒泡排序中同時(shí)完成了較小元素的上冒和較大元素的下沉，效率稍高。和較大元素的下沉，效率稍高。 比較次數(shù)：最壞情況下為比較次數(shù)：最壞情況下為 n(n-1)/2 時(shí)間復(fù)雜度為：時(shí)間復(fù)雜度為：O(n2) 空間復(fù)雜度為：空間復(fù)雜度為：O(1) 穩(wěn)定性：穩(wěn)定性：穩(wěn)定穩(wěn)定基本思想：基本思想：從待排序的從待排序的n個(gè)數(shù)據(jù)元素中任意選一個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素中任意選一個(gè)數(shù)據(jù)元素xi作為基準(zhǔn)元素；作為基準(zhǔn)元素；調(diào)整該序列中各個(gè)數(shù)據(jù)元素的位置，使得調(diào)整該序列中各個(gè)數(shù)據(jù)元素的位置，使得xi之之前的數(shù)據(jù)元素的排序碼都小于前的數(shù)據(jù)元素的排序碼都小于xi的排序碼，的排序碼，xi之之后的數(shù)據(jù)元素的

30、排序碼都大于后的數(shù)據(jù)元素的排序碼都大于xi的排序碼，從而的排序碼，從而確定了確定了xi在該序列中的位置；在該序列中的位置；此時(shí)，該序列被分割成此時(shí)，該序列被分割成2個(gè)個(gè)獨(dú)立的無序子獨(dú)立的無序子序列序列，其中前一子其中前一子序列序列中所有元素中所有元素排序碼排序碼均不大于后一子均不大于后一子序列序列中元素中元素排序碼排序碼。然后。然后再對(duì)這再對(duì)這2個(gè)個(gè)子子序列分別進(jìn)序列分別進(jìn)行快速排序，最后達(dá)到整個(gè)序列有序。行快速排序，最后達(dá)到整個(gè)序列有序。4、快速排序、快速排序舉例：設(shè)序列為舉例：設(shè)序列為46,55,13,42,94,5,17,7046,55,13,42,94,5,17,70 j ji i46

31、 55 13 42 94 5 17 7046 55 13 42 94 5 17 70 起始狀態(tài)，起始狀態(tài)，46key46key，4646為基準(zhǔn)元素為基準(zhǔn)元素j ji i17 55 13 42 94 5 17 7017 55 13 42 94 5 17 70 移動(dòng)移動(dòng)j j，17ri17rij ji i17 55 13 42 94 5 55 7017 55 13 42 94 5 55 70 移動(dòng)移動(dòng)i i，55rj55rjj ji i17 5 13 42 94 5 55 7017 5 13 42 94 5 55 70 移動(dòng)移動(dòng)j j，5ri5rij ji i17 5 13 42 94 9417

32、5 13 42 94 94 55 70 55 70 移動(dòng)移動(dòng)i i，94rj94rjj ji i17 5 13 42 46 94 55 7017 5 13 42 46 94 55 70 移動(dòng)移動(dòng)j j，i=ji=j，keyrikeyri一趟排序結(jié)束一趟排序結(jié)束算法分析：算法分析：1）設(shè)兩個(gè)變量，分別從表的兩端開始比較：）設(shè)兩個(gè)變量，分別從表的兩端開始比較：i：從左向右找大于基準(zhǔn)元素的元素：從左向右找大于基準(zhǔn)元素的元素 j：從右向左找小于基準(zhǔn)元素的元素：從右向左找小于基準(zhǔn)元素的元素找到后兩元素交換位置。找到后兩元素交換位置。2）當(dāng)）當(dāng)i與與j相遇時(shí)，基準(zhǔn)元素與該位置元素互換。此相遇時(shí)，基準(zhǔn)元素與

33、該位置元素互換。此時(shí)，形成兩個(gè)子表，一個(gè)子表的元素時(shí)，形成兩個(gè)子表，一個(gè)子表的元素基準(zhǔn)元素，另基準(zhǔn)元素，另一個(gè)子表的元素一個(gè)子表的元素基準(zhǔn)元素基準(zhǔn)元素3）遞歸調(diào)用，對(duì)每一個(gè)子表分別再快速排序，最后，）遞歸調(diào)用，對(duì)每一個(gè)子表分別再快速排序，最后，當(dāng)每個(gè)子表都只有一個(gè)元素時(shí)，排序結(jié)束。當(dāng)每個(gè)子表都只有一個(gè)元素時(shí)，排序結(jié)束。void quick_sort(int table, int low, int high)if( low high ) i=low; j=high;key = tablelow; while( i j ) while( i=key ) j- -; if(ij) tablei=ta

34、ble j; i+; while( ij & tablei=key ) i+ +; if(ij) tablej=table i; j-; tablei = key; quick_sort( table, low, i-1); quick_sort( table, i+1, high); /*基準(zhǔn)元素基準(zhǔn)元素*/排序效率排序效率：1 1）若基準(zhǔn)元素關(guān)鍵字為最大（或最?。?，退化）若基準(zhǔn)元素關(guān)鍵字為最大（或最?。?，退化成冒泡排序，效率不高；成冒泡排序，效率不高； 若基準(zhǔn)元素關(guān)鍵字為中間值，則效率高（排若基準(zhǔn)元素關(guān)鍵字為中間值，則效率高（排序趟數(shù)少，每一趟中交換的元素少）序趟數(shù)少，每一趟中交換

35、的元素少）2 2）可用棧消去遞歸（不支持遞歸的系統(tǒng)無法實(shí)）可用棧消去遞歸（不支持遞歸的系統(tǒng)無法實(shí)現(xiàn)遞歸運(yùn)算）現(xiàn)遞歸運(yùn)算）3 3）表的規(guī)模越大越能體現(xiàn)快速性）表的規(guī)模越大越能體現(xiàn)快速性時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O(nlognO(nlogn) )空空間復(fù)雜度：間復(fù)雜度：O(lognO(logn) ) 穩(wěn)定性：穩(wěn)定性：不穩(wěn)定不穩(wěn)定歸并歸并：（：（merging）將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。考慮一種特殊情形：考慮一種特殊情形：設(shè)一個(gè)線性表設(shè)一個(gè)線性表list由兩個(gè)由兩個(gè)有序子表有序子表lista和和listb組組成，現(xiàn)將這兩個(gè)子表歸并成一個(gè)

36、有序表。成，現(xiàn)將這兩個(gè)子表歸并成一個(gè)有序表。list： ( alowamid amid+1ahigh) 無序無序lista：(alowamid )有序有序listb：(amid+1ahigh)有序有序子表a子表b5、歸并排序、歸并排序算法分析：算法分析：1）開辟一個(gè)空間等于已知線性表的空間）開辟一個(gè)空間等于已知線性表的空間2）設(shè)三個(gè)變量：）設(shè)三個(gè)變量：i，j，k，其初始狀態(tài)分別指向，其初始狀態(tài)分別指向兩個(gè)子表的首部及新空間的首部兩個(gè)子表的首部及新空間的首部ilow；jmid+1； klow3）從兩個(gè)子表中逐個(gè)取出元素，比較后插入新表）從兩個(gè)子表中逐個(gè)取出元素，比較后插入新表4）將未取空的表中剩

37、余元素依次放入新表空間的）將未取空的表中剩余元素依次放入新表空間的后面后面5）將新表空間的元素復(fù)制到原表）將新表空間的元素復(fù)制到原表list中中算法實(shí)現(xiàn)：算法實(shí)現(xiàn)：/*兩個(gè)有序表合并成一個(gè)有序表兩個(gè)有序表合并成一個(gè)有序表*/void merge(int list, int low, int mid, int high, int listm)i=low; j=mid+1; k=low;while(i=mid & j=high) if(listi = listj) listmk=listi; i+;k+; else listmk=listj; j+; k+; if(i=mid)for(t=

38、i; i=mid; i+)listmk = listt; k+; if(j=high)for(t=j; j=high; j+)listmk = listt; k+; for(i=low; i=high; i+) listi=listmi;/*取取a表剩余元素表剩余元素*/*取取b表剩余元素表剩余元素*/2路歸并排序基本思想：路歸并排序基本思想：將一個(gè)長度為將一個(gè)長度為n的待排序列，看成的待排序列，看成n個(gè)長度為個(gè)長度為1的有序序列的有序序列將相鄰的兩個(gè)子序列兩兩歸并，產(chǎn)生將相鄰的兩個(gè)子序列兩兩歸并，產(chǎn)生 個(gè)長度為個(gè)長度為2或或1的有序序列的有序序列對(duì)這對(duì)這 個(gè)有序序列兩兩歸并，依此類推，個(gè)有序

39、序列兩兩歸并，依此類推，直到得到一個(gè)長度為直到得到一個(gè)長度為n的有序序列。的有序序列。n / 2n / 2例：例：(19) (13) (6) (25) (2) (20) (32) (15) (30)(13 19) (6 25) (2 20) (15 32) (30)(6 13 19 25) (2 15 20 32) (30)(2 6 13 15 19 20 25 32) (30)(2 6 13 15 19 20 25 30 32) 算法分析：算法分析：1）先把線性表分成）先把線性表分成n個(gè)長度為個(gè)長度為1的子表，進(jìn)行兩兩歸的子表，進(jìn)行兩兩歸并排序，第一趟：并排序，第一趟：子表元素個(gè)數(shù)：子表元素

40、個(gè)數(shù)： m=1跳步數(shù)：跳步數(shù)：step=2m=2待排待排序的兩個(gè)子表：序的兩個(gè)子表：low, mid mid=low+m-1;mid+1, high high=low+2m-1low=1，取第，取第1，2兩個(gè)子表兩個(gè)子表low=low+step=3，取第，取第3，4兩個(gè)子表兩個(gè)子表2）再對(duì)元素個(gè)數(shù)為）再對(duì)元素個(gè)數(shù)為2的子表兩兩歸并排序，第二趟：的子表兩兩歸并排序，第二趟：子表元素個(gè)數(shù)：子表元素個(gè)數(shù)： m=2跳步數(shù)：跳步數(shù)：step=2m=4待排待排序的兩個(gè)子表：序的兩個(gè)子表：low, mid mid=low+m-1;mid+1, high high=low+2m-1low=1，取第，取第1，2兩個(gè)子表兩個(gè)子表low=low+step=5，取第，取第3，4兩個(gè)子表兩個(gè)子表3）依此類推，每一趟排序后，）依此類推，每一趟排序后，m加倍加倍4）每一趟歸并排序中，如何取得兩個(gè)子表的元素？）每一趟歸并排序中，如何取得兩個(gè)子表的元素？子表子表1：low, mid子表子表2：mid+1, high考慮特殊情況：每個(gè)子表的元素個(gè)數(shù)都相同考慮特殊情況：每個(gè)子表的元素個(gè)數(shù)都相同=m，則，則兩兩歸并從第一個(gè)元素開始兩兩歸并從第一個(gè)元素開始for(low