1、XIANIVERSITY4、查找與排序liuyh廈門大學科學與技術學院XIANIVERSITY接下來，我們進一步提供應用實例說明前面引進的數據結構的用處，并表明對于要處理數據的結構的選擇怎樣深刻地影響著完成給定任務的算法。作為非常重要的基本運算，查找和排序就給出了這樣一個很例子，它們表明了一個任務可以用許多不同的算法來完成，每一種算法都有某些優點和缺點，必須根據具體的應用來衡量。查找的功能是從大量的數據中尋找出所需要的數據來，而排序是將一組按其關鍵字的遞增或遞減的次序排列，以便進行數據的查找和處理。liuyh廈門大學科學與技術學院XIANIVERSITY提綱(1) 查找(2) 排序liuyh廈

2、門大學科學與技術學院XIANIVERSITY(1) 查找liuyh廈門大學科學與技術學院XIANIVERSITY關鍵字(Key)可以標識(識別)一個數據元素若此關鍵字可以唯一，則稱此關鍵字為主關鍵字(Primary Key)(對不地標識一個，其主關鍵字均不同)。反之，稱用以識別若干同的關鍵字為次關鍵字(Secondary Key)。當數據元素只有一個數據項時，其關鍵字即為該數據元素的值。查找(Searching)是根據給定的某個值，在查找表中確定一個其關鍵字等于給定值的的一個數據元素，則稱查找是或數據元素。若在表中這樣的，此時給出數據元素的值，或指示該數據元素在查找表中的位置。若表中不關鍵字等

3、于給定值的數據元素，則稱查找不，此時查找的結果可給出一個“空”或“空”指針。待查數據元素的集合稱為查找表。liuyh廈門大學科學與技術學院XIANIVERSITY順序查找查找表在計算機中可以表示為順序表或線性鏈表。順序查找(Sequential Search)是最基本，也是最簡單的查找技術，其基本思想為：從第一個數據元素開始，逐個把數據元素的 關鍵字值和給定值比較，若某個元素的關鍵字和給定值相等，則查找；否則，如直到最后一個數據元素，也沒有數據元素的關鍵字和給定值相等，則查找失敗。順序查找也適用以鏈式既適用于以順序結構組織的查找表，結構組織的查找表。我們以順序結構為例說明順序查找算法，查找表S

4、類型說明如下：elemtypeSMAXNUM;其中，elemtype 為數據元素數據類型；MAXNUM為可能的數據元素最大個數。liuyh廈門大學科學與技術學院XIANIVERSITYint seq_search(elemtype S, keytype k, int n)在算法中n個待查數據元素放在順序表s0sn-1 中，在其后增加了監視哨sn，關鍵字為k，這樣int i; sn=k; i=0;/* 設置監視哨 */while (si.key!=k) i+;if (i<n)printf(searching success); return(i);使查找是否結的簡單容易，else prin

5、tf(searching failed); return(-1);提高了while語句的執行速度，從而加快了查找速度。liuyh廈門大學科學與技術學院XIANIVERSITY衡量查找算法執行效率的標準是平均查找長度。對于含有n個元素的查找表查找時的平均查找長度為其中，Pi為查找第i個數據元素的概率；Ci為查找第i個數據元素進行的比較次數。對于順序查找算法，假設查找表中每個數據元素的概率相同，即Pi =1/n，查找第i個數據元素進行的比較次數Ci =i，故順序查找算法查找的概率為進行n+1次比較，因此查找效率不而查找不高，僅對短表合適。liuyh廈門大學科學與技術學院XIANIVERSITY二分

6、查找如果查找表中的數據元素是按關鍵字有序的，則可以，即二分查找(Binary Search)方采用一種高效率的查找法。其基本思路是：由于查找表中的數據元素按關鍵字有序(假設遞增有序)，則在查找時可不必逐個順序比較，而采用跳躍的方式：先與“中間位置”的數據元素的關鍵字比較，若相等，則查找；若給定值大于“中間位置”的數據元素的關鍵字，則在查找表的后半部分繼續進行二分查找，否則在前半部分進行二分查找。liuyh廈門大學科學與技術學院XIANIVERSITY二分查找的過程：先確定待查元素所在的區域，然后逐步縮小區域，直到查找或失敗為止。設待查數據元素所在區域的下界為low，上界為hig，則中間位置mi

7、d=(low+hig)/2，(1)若此元素關鍵字值等于給定值，則查找成功；(2)若此元素關鍵字值大于給定值，則在區域mid+1hig內進行二分查找；(3)若此元素關鍵字值小于給定值，則在區域lowmid-1內進行二分查找。由于二分查找要求數據元素的組織方式應具有隨機存取的特性，所以二分查找只適用于以順序構組織的有序表的查找。結liuyh廈門大學科學與技術學院XIANIVERSITYint bin_search(elemtype S, keytype k, int n)int low,hig,mid; low=0;hig=n-1;while (low<hig)mid=(low+hig)/2

8、; if (Smid.key=k) printf(searching success); return(mid);else if (Smid.key<k)low=mid+1;liuyh廈門大學科學與技術學院XIANIVERSITYelsehig=mid-1;/* while循環結束*/printf(searching failed); return(-1);liuyh廈門大學科學與技術學院XIANIVERSITY的平均查找長度ASLlog2(n+1)-1。二分查找二分查找的優點是比較次數少，查找速度快。對于1000個數據元素組成的查找表，采用順序查找， 平均查找長度為500，而二分查找的

9、平均查找長度為 9。但是，二分查找所要付出的代價是要對數據元素按關鍵字的大小進行排序，這是很費時的。因此， 二分查找適合于數表一經建立就很少變動、可事先進行排序而又經常需要查找的場合。liuyh廈門大學科學與技術學院XIANIVERSITY分塊查找分塊查找又稱索引順序查找，是介于順序查找和二分查找之間的一種查找。它的基本思想是：(1)將所有數據元素分成塊，塊內元素按關鍵字是無序的，但塊間按關鍵字是有序的。即第一塊中的所有元素大于（小于）第二塊中的元素；第二塊中的所有元素大于（小于）第三塊中的元素；依次類推。(2)建立一個塊的最大（小）索引關鍵字表，該表是有序的。(3)具體查找分兩步：首先對索引

10、關鍵字表進行二分查找或順序查找，確定數據元素可能在哪一塊；然后在已確定的那一塊中進行順序查找。liuyh廈門大學科學與技術學院XIANIVERSITY的例子，查找表由12個數據元素構成。按分塊查找的思想：(1)分成三塊；將它(2)建立一個最大順序的索引關鍵字表；(3)根據待查的關鍵字進行查找，設待查的關鍵字為50的數據元素，則從索引關鍵字中查到該50第二塊中，因30<50<65。然后在第二塊中用順序查找法找到關鍵字為50的數據元素。liuyh廈門大學科學與技術學院XIANIVERSITY查找：順序查找、二分查找和分塊查前面所討論的查找找。其中以二分查找的效率最高，但二分查找要求查找

11、表中的數據元素按關鍵字有序，且不能用鏈表作結構。當對查找表中的數據元素進行有序性，勢必要移動很多和刪除時，為了保持查找表的，造成新的時間開銷，當和刪除頻繁時這種額外開銷就會抵消二分查找的優點。為克服這些缺點，可應用，是一種動態查找表，其特點動態生成，即對于給定值是表結構本身可以在查找過Key，若表中其關鍵字等于的Key，則查找，否關鍵字為Key的則。liuyh廈門大學科學與技術學院XIANIVERSITY實際上應用二叉排序樹作為查找表中數據元素的結構，就可以避免二分查找表的不足，同時保留二分查找高效率的優點。二叉排序樹既有利于查找表的動態生成，又具有 較高的查找效率。根據二叉排序樹的定義，在二

12、叉排序樹中，樹上所有結點的關鍵字都小于根結點的關鍵字；右子樹上所有結點的關鍵字都大于根結點的關鍵字。因此，二叉排序樹查找的基本思想是: (1)當二叉排序樹不空時，首先將給定的值k與根結點的關鍵字進行比較，若相等則查找。(2)若給定值k小于根結點的關鍵字，則下一次與樹的根結點進行比較，若給定值k大于根結點的關鍵字，則下一次與右子樹的根結點進行比較。如此遞歸地進行下去直到某一次比較相等，查找找失敗。如果一直比較到不等，則查liuyh廈門大學科學與技術學院XIANIVERSITY為方便算法說明，首先給出二叉樹結點數據類型定義和結點的結構類型定義：typedefstructnode_dataTyped

13、efstruct bs_node.keytype.datatypedata;struct bs_node *LC; struct bs_node *RC; bsnode;key; datatype;liuyh廈門大學科學與技術學院XIANIVERSITYbsnode *bs_search(bsnode *t, keytypek)bsnode *s;if (t=NULL) printf(empty tree"); return(t);s=t;if (s->data).key=k) printf(“searching success"); return(s);else i

14、f (s->data).key>k)return (bs_search(s->LC,k); /* 在else樹繼續查找 */return (bs_search(s->RC,k); /* 在右子樹繼續查找 */科學與技術學院liuyh廈門大學XIANIVERSITY實例一組數據元素的關鍵字序列是45,24,53,12,37,95,30,40,80。如圖是依據這些數據生成的二叉排 序樹，如果要查找關鍵字是37的 結點：第一步，37與根結點比較，因37<45，查找樹；第二步，37與樹根結點P2之關鍵字比較，因37>24，查找右子樹；第三步， 37與結點P3之關鍵字

15、比較，因37=37，查找。liuyh廈門大學科學與技術學院XIANIVERSITY如果要查找關鍵字是50P1之關鍵字比較，因50>45，查找P1的右子樹與根結點50與結點P4之關鍵字比較，因50<53，查找P4的樹；第三步，P4的樹為空，查找失敗。上述實例表明：在二叉排序樹中查找時走了一條從根結點到所查結點的路徑。因此，二叉排序樹查找的平均長度取決于二叉排序樹的深度。當二叉排序樹左、右子樹的深度之差不超過1時，其平均查找長度與二分查找相同，ASLlog2n-1，此時二叉排序樹效率最高，但是，由于二叉排序樹是動態生成的，樹的結點隨一棵的先后次序不同而不同，最惡劣的情況是生成，此時，二

16、叉排序樹查找長度與順序查找長度相同，ASL (n+1)/2，效率最低。liuyh廈門大學科學與技術學院XIANIVERSITY查找在前面討論的各種結構(線性表、樹等)中，在結確構中的相對位置是隨機的，和的關鍵字之間不定的，因此，在結構中查找進行一系列和關鍵字的比較。這一類查找建立在“比較”的基礎上。在順序查找時，比較的結果為“”和“”兩種；在二分查找和二叉排序樹查找時，比較的結果為“<”、“=” 和“>”三種可能。查找的效率倚賴于查找過程所進行的比較次數。理想的情況是希望不經過任何比較，一次存取便能得到所查，那就必須在的位置和它的關鍵字之H，使每個關鍵字和一個唯一liuyh間建立一

17、個確定的對應廈門大學科學與技術學院XIANIVERSITY的位置相對應：a因而在查找時，只要根據這個對應H找到給定值k的像，則必定在H(k)H(k)。若結構中關鍵字和k的位置上，由此，不需要進行比較便可直接取得所查。我們稱這個對應H為(Hash)函數（又稱散列函數），按照這個思想建立的表叫做表（散列表），相應的查找技術稱為查找（散列查找）。在大多數情是，函數是一種“壓縮映像”，它把數據元素的關鍵字取值很大的數據集合到一個范圍確定的地址表中。因此，對不同的關鍵字可能得到同一地址，這種現象稱為。具有相同函數值的關鍵字對該函數來說稱為同義詞。liuyh廈門大學科學與技術學院XIANIVERSITY如

18、以學號作為學生數據元素的關鍵字，函數應用學號的后兩位作為地址，可得如下關鍵字和地址對照表：顯然，采用壓縮映像后產生的地址可能會發生沖突，如上表中，關鍵字95125和95225經過函數運算得到的地址都是25。因此，在個計算簡單、地址分布均勻的查找中，既要選擇一函數，以避免或減少沖突的發生；又要在出現時，建立解決的。liuyh廈門大學科學與技術學院addr042509013027022508key951049512595203952019513095127951029522595108.XIANIVERSITY函數的構造構造函數的有很多。在各種之前，首先要明確什么是“合中的任一個關鍵函數。若對于關

19、鍵字集函數映像到地址集合中任何一個地址的概率是相等的，則稱此類函數為均勻的(Uniform)函數。換句話說,就是使關鍵過哈希函數得到一個“隨機地址”，以便使一組關鍵字的哈希地址均勻分布在整個地址空間，從而減少。1直接定址法：取關鍵字或關鍵字的某個線性函數值為地址。即：H(key)=key 或 H(key)=a*key+b其中a和b為常數(這種函數叫做自身函數)。liuyh廈門大學科學與技術學院XIANIVERSITY2數字分析法10為基的十進制數），并且r為基的數（如以表中可能出現的關鍵字都是事先知道的，則可取關鍵字的若干數位組成地址。具體取那幾位，則以盡量避免為原則。3平方取中法：取關鍵字平

20、方后的中間幾位為地址。這是一種較常用的構造函數的，通常在選定函數時不一定能知道關鍵字的全部情況，其中幾位也不一定合適，而一個數平方之后的中間幾位數和數的每一位都相關，由此使隨機分配的關鍵字得到的地址也是隨機的，取的位數由表長決定。liuyh廈門大學科學與技術學院XIANIVERSITY4折疊法一部分的位數可以不同），然后取這幾部分的疊加和（舍folding)去進位）作為地址，這關鍵字位數很多，而且關鍵字中每一位上數字分布大致均勻時，可采用折疊法得到地址。5除留余數法：取關鍵字被某個不大于表長m的數p除后所得余數為地址。即H(key)= key mod p, p<=m這是一種最簡單，也最常

21、用的構造函數的，它不僅可以對關鍵字直接取模，也可在折疊、平方取中等運算 之后取模。具體應用中，對p的選擇很重要，若p選的不好，容易產生同義詞。liuyh廈門大學科學與技術學院XIANIVERSITY6隨機數法函數值為它的地址，即：H(key)=random(key)其中random為隨機函數。通常，當關鍵字長度不等用此法構造函數較恰當。實際工作中需視不同的情況采用不同的函數。通常，考慮的因素有: (1) 計算函數所需時間（硬件指令因素）；(2) 關鍵字的長度；(3)表的大小；(4) 關鍵字的分布情況；(5)的查找頻率。liuyh廈門大學科學與技術學院XIANIVERSITY處理的函數可以減少均

22、勻的，但不能完全避免沖突，因此如何處理是造表不可缺少的另一方面。表的地址集為0（假設字得到的則“處理是指由關鍵地址為j(0 j n-1)的位置上已存有，”就是為該關鍵字的找到另一個“空”的可能得到一個地址序列地址。在處理的過Hi i=1,2,k, (Hi 0, n-1)。即在處理時，若得到另一個地址的，則再求下地址H1仍然發生一個地址H2，若H2仍然，再求H3。依次類推，直至Hk不發生解決為止，則Hk為在表中的地址。常用的有兩種：鏈地址法和開放地址法。liuyh廈門大學科學與技術學院XIANIVERSITY鏈地址法處理想是：將所有具有相同的基本思地址的i個數據元素在同一單鏈表中，應用鏈地址法產

23、生的表的每個單元需增加一個指針域，用來指向下一個具有相同哈希地址的數據元素。如圖是對含有8個元素，a,b, c, d, e, f, g, h，通過某函地址范圍為07，采數得到用鏈地址法得到的表。liuyh廈門大學科學與技術學院XIANIVERSITY開放定址法：開放定址法的基本思想是在發生時，按照某種繼續探測到空位置為止，可以用下式描述：Hi=(H(key)+di) mod mm-1)其中：H(key)為函數，m為表表長，di為增量序列，可有下列三種取法：(1) di=1,2,m-1稱為線性探測再散列；(2) di=12,-12,22,-22,32, ±k2，(km/2)，稱為二次探

24、測再散列；(3) di=偽隨機數序列，稱為偽隨機探測再散列。用這種構造表時，首先計算出關鍵字的直接地址H(k)，若該單元已被其他數據元素占用，繼續查 看地址為H(k)+d1的單元，如仍被占用，再繼續查看H(k)+d2的單元，直到發現某個單元為空，將關鍵字為k的到該單元中。存放liuyh廈門大學科學與技術學院XIANIVERSITY在長度為11的表中已填有關鍵字分別為17，60，29函數H(key)= key mod 11），現有第四個的（，。(b)、其關鍵字為38，由函數得到地址為5，產生(c)、(d)分別為線性、二次和偽隨機數（偽隨機數為9,）探測再散沖0處的31245678910(a)(b

25、)6,7,86,4(c)3(d)廈門大學liuyh科學與技術學院386017293860172960172938601729XIANIVERSITY從上述線性探測再散列的過象：當表中i、i+1和i+地址為i、i+1、i+2和i+可以看到一個現時，下一個都將填入i+3的位置，這種在處理過發生的兩個第一個地址不地址的現象稱做“二次聚又添加了非同義詞的沖同的爭奪同一個后繼集”，即在處理同義詞的過突，顯然這種現象對查找不利，但另一方面，用線性探測再散列處理可以保證做到：只要表未填滿，總能找到一個不發生的地址，而二次探測再表長m為形如4j+3(j為整數)的素數時散列只有在才可能，隨機探測再散列，則取決于

26、偽隨機數列。liuyh廈門大學科學與技術學院XIANIVERSITY查找算法建立了表，相應的Typedefstructchain查找算法就很簡單，基本思想為：根據k值求出其直接哈希地址，若該單元為空，則 查找失敗；若該單元不為空，將k與該單元的關鍵字相比較，/* 關鍵字類型說明*/elemtypedata;/* 數據元素類型說明*/structchain*next;若二者相等，則查找否則按照所采用的構造， chainnode;表的，繼續在“下一個地址”中查找。liuyh廈門大學科學與技術學院XIANIVERSITYchainnode *hash_search(chainnode *a, key

27、type k)chainnode *p; int i;i=H(k);p=ai;while (p!=NULL && p->key!=k) p=p->next;if (p=NULL) printf (“searching failed); return(NULL);else printf (searching success"); return(p);liuyh廈門大學科學與技術學院XIANIVERSITY查找是一種直接計算地址的，在查找過所需的比較次數較少。由查找算法可以看出，在進行查找時，首先要由函數、解決的方查法以及關鍵字值計算出地址，因此在考慮找的效率

28、時，不但要考慮查找時所需的比較次數，還要考慮求得地址所需時間。查找的效率分析比較復雜，不再繼續深入討論。liuyh廈門大學科學與技術學院XIANIVERSITY(2) 排序liuyh廈門大學科學與技術學院XIANIVERSITY排序(sorting)，有稱為，是計算機程序設計中的一種重要操作，它的功能是將一個數據元素（或的任意序列，重新排列成一個按關鍵字有序的序列。）通過對查找算法的討論，我們知道，為了查找的方便，通常希望計算機中的表是按關鍵字有序的，因為有序的順序表可以采用查找效率較高的二分查找法，而無序的順序表只能進行順序查找，效率較低。另外，二叉排序樹的生成過程本身就是一個排序的過程。因

29、此，學習和研究各種排序題之一。仍然是程序設計中一個重要的課liuyh廈門大學科學與技術學院XIANIVERSITY假設含有n個R1 , R2 ,其相應的關鍵字序列為，K1 , K2 , , Kn需確定1 , 2, , n的一種排列p1 , p2 , , pn，使其相應的關鍵字滿足如下的非遞減（或非遞增）Kp1Kp2 Kpn即使原序列成為一個按關鍵字有序的序列Rp1 , Rp2 , , Rpn 這樣一種操作稱為排序。liuyh廈門大學科學與技術學院XIANIVERSITYRi (i=1,2,n) 的主關排序定義中的關鍵字可以是Ri的次關鍵字，甚至是若干數據項的集鍵字，也可以是合。若Ki是主關鍵字

30、，則任何一個的無序序列經排序后得到的結果是唯一的；若Ki是次關鍵字，則排序的結果不唯一，因為待排序的序列中可能兩個或兩個以上關鍵字相等的。假設Ki =Kj (1 i n, 1 j n, i j)，且在排序前的序列中Ri領先于Rj (即i<j)。若在排序后的序列中Ri 仍領先于Rj，則稱所用的排序是的；反之，若可能使排序后的序列中，Rj領先于Ri，則稱所用的排序定的。是不穩liuyh廈門大學科學與技術學院XIANIVERSITY由于待排序的器不同，可將排序指的是待排序數量不同，使得排序過內部排序，器中進行的排序 的數量很大，尚需對外過程；另一類是外部排序以致內存一次不能容納全部存進行的排序

31、過程。衡量內部排序算法和外部排序算法的效率的是不同的。因為對內部排序而言，時間的主要開銷花在數據元素的比較和移動上，可用算法執行時要進行的比較次數來衡量；而對外部排序而言，既要進行數據元素的比較和移動，還要不斷地讀、寫外部器，讀、寫外部器的速度是很慢的，因此，外部排序的時間代價更主要的是用讀、寫外部器的次數來衡量。liuyh廈門大學科學與技術學院XIANIVERSITYTypedef struct待排序的序列既可以選取鏈.keytype.式結構作為其在內存中的存儲方式，也可選key; /*/關鍵字類型取順序結構作為其在內存中的方式。為elemtype; /*類型說明*/*/簡單起見，我們采用后

32、者來說明算法。ElemtypexMAXNUM; /*序列liuyh廈門大學科學與技術學院XIANIVERSITY簡單排序簡單直接排序的基本思想：把n個數據元素的序列分為兩部分，R1, Ri-1 為已排有序的部分，Ri,Ri+1, Rn 為未排序的部分。這時把未排序部分的第一個元素Ri依次與R1 , Ri-1比較，并到有序部分的合適位置上，使得R1, Ri 變為新的有序部分。初始時，令i=2，因為一個元素自然有序，故R1自然成為一個有序的部分，未排序部分是R2 , Rn ， 然后依次將R2 ,R3 , Rn插到有序部分中去就可得整個有序序列。簡單排序算法是的，它改變原序列中關鍵字相同的元素的相對

33、次序。liuyh廈門大學科學與技術學院XIANIVERSITY181210123016初始狀態i=2121810123016i=3101218123016i=4101212183016i=51012121830 16101212163830i=6liuyh廈門大學科學與技術學院XIANIVERSITYinsertsort(elemtype x, int n)int i,j; elemtypea;for (i=0;i<n-1; i+)a=xi+1; j=i;/* 在局部變量a中暫存將要的元素 */while (j>-1 && a.key<xj.key) xj+1

34、=xj; j-;xj+1=a;科學與技術學院liuyh廈門大學XIANIVERSITY簡單選擇排序簡單選擇排序(simple selection sort)的基本思想是：第一趟排序是在無序的R1 ,R2 , Rn 中按關鍵字選出最小的元素，將它與R1交換；第二趟排序是在無序的R ,R , Rn 中選出最小的元素，將它與R2交換；而第i趟排序時R1 ,R2 , Ri-1 已排好序，在當前無序的Ri , Rn 中再選出最小的元素，將它與Ri交換，使R1 ,R2 , Ri 成為有序。因為每趟排序都使有序區中增加了一個數據元素，且有序區中的數據元素的關鍵字均不大于無序區中元素的關鍵字，所以經過n-1趟

35、排序后，整個數據元素序列就遞增有序。簡單選擇排序有可能改變關鍵字相同的數據元素的相對位置，因而是一種不的排序算法。liuyh廈門大學科學與技術學院XIANIVERSITYliuyh廈門大學科學與技術學院XIANIVERSITYselectsort(elemtype x, int n)int i,j,small; elemtype swap;for (i=0; i<n-1; i+)small=i;for (j=i+1; j<n; j+) /* 找出關鍵字最小的元素 if (xj.key<xsmall.key) small=j;*/if (small!=i)/* 與無序區第一個元

36、素交換*/ swap=xi;xi=xsmall; xsmall=swap;科學與技術學院liuyh廈門大學XIANIVERSITY冒泡排序冒泡排序(bubble sort)本思想是：從R1開始，兩兩比較，它的基1,2, 的位置，第的關鍵字的大小,若Ki > Ki+1則交換一趟全部比較完畢后Rn是序列最大的數據元素。再從R1 開始，兩兩比較Ri和Ri+1(i=1,2, , n-2)的關鍵字的大小, 若Ki > Ki+1則交換Ri和Ri+1的位置，第二趟全部比較完畢后Rn-1是序列最大的數據元素。如此反復，進行n-1趟冒泡排序后所有待排序的n個元素序列按關鍵字有序。在排序過，關鍵字較小

37、的數據元素好比水中氣泡逐趟向上漂浮，而關鍵字較大的數據元素則好比石塊往下沉， 每一趟有一塊“最大”的石頭沉到水底。liuyh廈門大學科學與技術學院XIANIVERSITY656565977613761327132749274958495876589797初始狀態第1趟(j=16) 第2趟(j=15)第3趟(j=14)13274958657697第4趟(j=13)第5趟(j=12)131313 272727494949585858656565767676979797第6趟(j=1)liuyh廈門大學科學與技術學院XIANIVERSITYbubblesort(elemtype x, int n)i

38、nt i,j,flag; elemtype swap;for (i=0; i<n-1; i+) flag=0;for (j=0; j<n-i; j+ )if (xj.key>xj+1.key) flag=1; swap=xj; xj=xj+1; xj+1=swap;if (flag=0)return;科學與技術學院liuyh廈門大學XIANIVERSITY在上述冒泡排序算法中使用了一個標記變量flag，用于標記在每一趟執行時是否有數據元素交換，如果有一趟冒泡排序“空跑”，表示此時數據元素序列已經有序，應結束排序過程。冒泡排序的。對于加標記變量flag的冒泡排序能算法是“判別”

39、數據元素序列的狀態，所以當待排序序列是基本有序的。用冒泡排序的效率是很高liuyh廈門大學科學與技術學院XIANIVERSITY快速排序快速排序(quick sort)又叫做分區交換排序，是目前已知的平均速度較快的一種排序,它是對冒泡排序的一種改進。它的基本思想：通過一趟排序將待排數據元素分割成兩個的部分，其中一部分數據元素的關鍵字均比另一部分數據元素的關鍵字小，然后分別對這兩部分數據元素繼續進行快速排序，以達到整個序列有序。具體來說，首先從待排序的n個數據元素中任意選取 一個元素Ri(通常選取無序序列中的第一個元素)作標準， 調整序列中各個元素的位置，使排在Ri前面的元素的關鍵 字都小于Ri

40、 .key，排在Ri后面的元素的關鍵字都大于Ri .key,通常這樣的一個過程稱作一次快速排序，在第一次快速排liuyh廈門大學科學與技術學院XIANIVERSITY序中，確定了元素Ri最終在序列中的排列位置，同時也把剩余的數據元素分成了兩個子序列。對兩個子序列再進行快速排序，又確定了兩個元素在序列中的位置，并將剩余元素分成了四個子序列，如此重復下去，當各個子序列的長度為1時，全部元素排序完畢。可見，快速排序中的基本操作是子序列的劃分操作。設當前處理的元素序列的下界是low，上界是high，劃分 操作的步驟如下：(1) 讓兩個指針i , j分別指向序列的第一個元素和最后一個元素(即i=low

41、, j=high)，并將第一個元素的關鍵字k中。保liuyh廈門大學科學與技術學院XIANIVERSITY(2) 用k與jk Rj.key，則繼續與j的前一個數據元素 j=j-1)的關鍵字相比較，否則將Ri和Rj互換位置，此過程又稱為從右向左掃描過程。(3) 用k與i指向的數據元素的關鍵字相比較，若k Ri.key，則繼續與i的后一個數據元素(i=i+1)的關鍵字相比較，否則將Ri和Rj互換位置，此過程又稱為從掃描過程。(4) 比較i和j，若i<j，則重復上面的(2)、(3)操作， 直到i=j時，劃分操作結束。liuyh廈門大學科學與技術學院XIANIVERSITYliuyh廈門大學科學

42、與技術學院XIANIVERSITYquicksort(elemtype x, int l, int r)int i,j; elemtype swap; i=l; j=r; swap=xl; while (i<j)while (i<j && swap.key <=xj.key)j-;if (i<j)/* 從右向左掃描*/ xi=xj; i+;科學與技術學院liuyh廈門大學XIANIVERSITYwhile (i<j && swap.key >=xi.key)i+;if (i<j)/* 從掃描 */xj=xi; j-;xi

43、=swap;if (l<i) quicksort(x,l,i-1); if (i<r) quicksort(x,i+1,r);liuyh廈門大學科學與技術學院XIANIVERSITY上述算法中，待排序數據元素序列順序存放在xl，xl+1， ，xr中，局部變量i,j指示左右兩端當前掃描到的數據元素的序號，swap用于存放當前標準元素。該算法使用了遞歸來實現。快速排序是不的排序，并且對于同一待排序列，如果選取不同的基準元素的話，其排序速度可能不同。如果選擇的基準元素恰好是序列中所有元素的中位數，則所劃分的前后兩個子序列的元素數目近乎相等，這時排序速度最快。liuyh廈門大學科學與技術學

44、院XIANIVERSITY歸并排序歸并排序(merging sort)又稱為表排序，是又一類不。“歸并”的含義是將兩個或兩個以上的有一個新的有序表。若是對兩個序列進行歸并同的排序序表組又稱2-路歸并。利用歸并的思想容易實現排序，基本思路是：假設初始序列含有n個數據元素，則可以看成是n 個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到n/2個長度為2或1的有序子序列；再兩兩歸 并，如此重復，直至得到一個長度為n的有序序稱為2-路歸并排序。列為止，這種liuyh廈門大學科學與技術學院XIANIVERSITYliuyh廈門大學科學與技術學院XIANIVERSITY通過上述分析可以看出：在歸并排序的過，最基本的問題是如何把兩個位置相鄰的有序子序列合并成一個有序子序列。設兩個有序序列在一維數組R中，有序子序列1是(R1, R2, , Rm)，有序子序列2是(Rm+1 , , Rr)。歸并后產生的有序序列存放在另一個數組x中，該有序序列是(x1, x2, , xr)。歸并為：(1)設置三個變量i1、i2和j。其中i1 和i2分別表示序列1和2中當前要比較的位置（下標），初始值分別為1和m+1；j表示數組x中當前元素應放置的位置號(下標)，初始值為1。liuyh廈門大學科學與技術學院XIANIVERSITY(2)反復比較Ri1和Ri