計算機(jī)軟件技術(shù)基礎(chǔ)-welcometonginx!

1、計算機(jī)軟件技術(shù)基礎(chǔ),教 師：曾曉東電 話：13679007201E_mail: zengxiaodong@263.net,5.2 排序,一、基本概念二、選擇排序三、插入排序四、交換排序五、歸并排序六、各種排序算法的比較,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,一、基本概念,1. 排序設(shè)有含n個記錄的序列為{ R1,R2,…,Rn }，其相應(yīng)的關(guān)鍵字序列為{ K1,K2,...,Kn }?，F(xiàn)要求確定一種排序p1,p2,...

2、pn, 使其關(guān)鍵字滿足遞增（或遞減）的關(guān)系：Kp1≤Kp2≤???≤Kpn（或Kp1≥Kp2≥ ???≥Kpn）使原序列成為一個按關(guān)鍵字有序的序列：{ Rp1,Rp2,…Rpn },計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,一、基本概念,2.排序方法的穩(wěn)定性若Ki=Kj(1≤i≤n ,1≤j≤n ,i≠j)，在排序前Ri領(lǐng)先于Rj ，排序后Ri仍領(lǐng)先于Rj ，則稱此排序方法是穩(wěn)定的；反之稱為不穩(wěn)定的。3. 排序的分類若排序

3、時待排序記錄存放在內(nèi)存中進(jìn)行排序，則稱為內(nèi)部排序；若待排序記錄數(shù)量很大，在內(nèi)存中一次不能容納全部記錄，需要在排序過程中對外存進(jìn)行訪問，則稱為外部排序。4.基本操作1）對記錄中關(guān)鍵字大小進(jìn)行比較；2）將記錄從一個位置移到另一個位置。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,一、基本概念,5. 排序的時間開銷: 排序的時間開銷是衡量算法好壞的最重要的標(biāo)志。排序的時間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動次數(shù)來衡量。算法運行時間

4、代價的大略估算一般都按平均情況進(jìn)行估算。對于那些受對象排序碼序列初始排列及對象個數(shù)影響較大的，需要按最好情況和最壞情況進(jìn)行估算。5. 算法執(zhí)行時所需的附加存儲 評價算法好壞的另一標(biāo)準(zhǔn)。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,一、基本概念,7. 待排序的數(shù)據(jù)表使用順序存儲結(jié)構(gòu)存儲其數(shù)據(jù)類型定義如下：記錄結(jié)點的類型定義：typedef struct{keywordtype key;datatype data;}RE

5、CORDNODE;待排序的數(shù)據(jù)表是RECORDNODE類型的數(shù)組struct RECORDNODE a[MaxSize];,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,二、選擇排序,選擇排序是不斷在待排序序列（無序區(qū)）中按記錄關(guān)鍵字遞增（或遞減）次序選擇記錄，放入有序區(qū)中，逐漸擴(kuò)大有序區(qū)，直到整個記錄區(qū)為有序區(qū)為止。其基本思想是: 每一趟 (例如第 i 趟, i = 1, 2, …, n-1) 在后面 n-i 個待排序?qū)ο笾羞x出排序碼最小的對

6、象, 作為有序?qū)ο笮蛄械牡?i 個對象。待到第 n-1 趟作完, 待排序?qū)ο笾皇Ｏ?個, 就不用再選了。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,二、選擇排序,直接選擇排序過程：在當(dāng)前無序序列中選擇一個關(guān)鍵字最小的記錄，并將它和最前端的記錄交換。重復(fù)上述過程，使記錄區(qū)的前端逐漸形成一個由小到大的有序區(qū)。2) 基本步驟(1)在一組對象 a[i]～a[n] 中選擇具有最小關(guān)鍵字的對象；(2)若它不是這組對象中的第一個對象, 則將它與這

7、組對象中的第一個對象對調(diào);(3)在這組對象中剔除這個具有最小關(guān)鍵字的對象。在剩下的對象a[i+1]～a[n]中重復(fù)執(zhí)行第(1)、(2)步, 直到剩余對象只有一個為止。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,最小者 08交換21,08,最小者 16交換25,16,最小者 21交換49,21,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,最小者 25*無交換,最小者 25無交換,各趟排序后的結(jié)果,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,1. 直接選擇排序,

8、3）算法void SelectSort(RECORDNODE a[],int n){/*對記錄數(shù)組a[1:n]進(jìn)行直接選擇排序*/int i,j,small;RECORDNODE swap;for (i=1;ia[j].key) small=j;if (small!=i){/*交換*/swap=a[small]; a[small]=a[i]; a[i]=swap;}}},計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,1

9、. 直接選擇排序,4）算法分析算法由兩層循環(huán)構(gòu)成，外層循環(huán)表示共需進(jìn)行n-1趟排序，內(nèi)層循環(huán)需進(jìn)行n-I次比較，也許會做一次交換，即記錄移動次數(shù)最多為3。總的時間性能為① 比較次數(shù)：n(n-1)/2② 移動次數(shù)：最壞情況下為3(n-1)所以總的時間復(fù)雜度為：O(n2)空間復(fù)雜度為：O(1) 交換記錄時用直接選擇排序是一種不穩(wěn)定的排序算法,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,二、選擇排序,2. 堆排序1) 堆設(shè)有序列

10、{ k1,k2,…,kn }，若滿足：,則稱該序列構(gòu)成的完全二叉樹是一個堆。 例如，有序列：{ 96，83，27，38，11，9 } 構(gòu)成的完全二叉樹如上圖所示,它是一個堆。 易知堆頂元素為所有元素中的最小值或最大值,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 堆排序,2）堆排序的過程由兩部分組成：① 將現(xiàn)有的序列構(gòu)成一個堆② 輸出堆頂元素，重新調(diào)整元素，構(gòu)成新的堆，直到堆空為止。3）堆的構(gòu)造：① 由所給序列生成對應(yīng)

11、的完全二叉樹；② 設(shè)完全二叉樹a[1..n]中結(jié)點a[k]的左右子樹均為堆，為構(gòu)成以a[k]為根結(jié)點的堆，需進(jìn)行調(diào)整。方法是將a[k]的值與其左右子樹的根結(jié)點進(jìn)行比較，若不滿足堆的條件，則將a[k]與其左右子樹中根結(jié)點大的交換，繼續(xù)進(jìn)行比較，直到所有子樹均滿足堆的定義為止。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,建立初始的最大堆,,,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,,,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 堆排序,最大堆的向下調(diào)整算法v

12、oid createHeap(RECORDNODE a[],int p,int n){/*將a[p:n]建立為以a[p]為根的最大堆*/int i,j,k;i=p; j=2*i;a[0]=a[i];/*a[i]暫存到a[0]中*/while(j<=n){if(j<n&&a[j].key<a[j+1].key) j++;/*選兩子女的較大者*/if(a[0].key<a[j].

13、key){/*a[j]移向堆頂*/a[i]=a[j];i=j;j=2*i;} else break;}a[i]=a[0];},計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 堆排序,③ 對于一個無序序列a[1..n]構(gòu)成的完全二叉樹，只要從它最后一個非終端結(jié)點：(n/2)開始直到根結(jié)點為止，逐步進(jìn)行上述調(diào)整，即可將該完全二叉樹調(diào)整為堆。 算法為：int p=n/2,i;for (i=p;i>=1;i--)

14、createHeap(a,i,n);,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 堆排序,4）堆排序由以下兩個步驟進(jìn)行：① 由給定的無序序列構(gòu)造最大堆；② 最大堆堆頂a[1]具有最大的關(guān)鍵字,將a[1]與a[n]對調(diào),把具有最大關(guān)鍵字的對象交換到最后,再對前面的n-1個對象,使用堆的調(diào)整算法Sieve(a,1,n-1),重新建立最大堆,具有次最大關(guān)鍵字的對象又上浮到a[1]位置。再對調(diào)a[1]和a[n-1],調(diào)用Sieve(

15、a,1,n-2),對前n-2個對象重新調(diào)整，…。如此反復(fù)執(zhí)行，最后得到全部排序好的對象序列。這個算法即堆排序算法。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,,,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,,,,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,,,,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,,,,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,,,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 堆排序,堆排序的算法Void HeapSort(RECORDNODE a[],int n){/

16、*使用堆排序算法對記錄數(shù)組a[1:n]按關(guān)鍵字遞增排序*/int i;for(i=n/2;i>=1;i--) createHeap(a,i,n);/*建立初始最大堆*/for(i=n;i>=2;i--){a[0]=a[1]; a[1]=a[i];a[i]=a[0];/*交換a[1]和a[I]*/createHeap (a,1,i-1);/*重建最大堆*/}},計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序

17、,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 堆排序,5) 算法分析若設(shè)堆中有 n 個結(jié)點, 且 2k-1 ? n ? 2k, 則對應(yīng)的完全二叉樹有 k 層。在第 i 層上的結(jié)點數(shù) ? 2i-1 (i = 1, 2, …, k)。在第一個形成初始堆的 for 循環(huán)中對每一個非葉結(jié)點調(diào)用了一次堆調(diào)整算法createHeap(),因此該循環(huán)所用的計算時間為：,其中, i 是層序號, 2i-1 是第 i 層的最大結(jié)點數(shù), (k-i)是

18、第 i 層結(jié)點能夠移動的最大距離。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 堆排序,第二個for循環(huán)中調(diào)用了n-1次createHeap( )算法, 該循環(huán)的計算時間為O(nlog2n)。因此, 堆排序的時間復(fù)雜性為O(nlog2n)。該算法的附加存儲主要是在第二個for循環(huán)中用來執(zhí)行對象交換時所用的一個臨時對象。因此，該算法的空間復(fù)雜性為O(1)。堆排序是一個不穩(wěn)定的排序方法。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,三、插入排序,插入排序

19、是將當(dāng)前無序區(qū)中最前端的記錄插入到有序區(qū)中，逐漸擴(kuò)大有序區(qū)，直到所有記錄都插入到有序區(qū)中為止。1. 直接插入排序1)基本思想是 : 當(dāng)插入第i (i ? 1) 個對象時, 前面的a[0], a[1] , … , a[i-1]已經(jīng)排好序。這時, 用a[i]的排序碼與a[i-1], a[i-2], …的關(guān)鍵碼順序進(jìn)行比較, 找到插入位置即將a[i]插入, 原來位置上的對象向后順移。 為了減少查找關(guān)鍵碼時的比較次數(shù)，可在有序區(qū)的前端a

20、[0]處設(shè)一個監(jiān)視哨，存放當(dāng)前要插入的關(guān)鍵字。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,,,各趟排序結(jié)果,21,25,49,25*,16,08,1 2 3 4 5 6,,0 1 2 3 4 5 6,21,25,49,25*,16,08,25,i = 2,0 1 2

21、 3 4 5 6,,21,25,49,25*,16,08,49,i = 3,,,,,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,,,21,25,49,25*,16,08,,21,25,49,25*,16,08,i = 5,,21,25,49,25*,16,08,i = 6,,,,,i = 4,25*,,,,16,,,,,08,,,,,,0 1 2 3

22、 4 5 6,0 1 2 3 4 5 6,0 1 2 3 4 5 6,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,,16,,49,16,16,,,21,25,49,25*,16,08,1 2 3 4 5

23、 6,21,25,49,25*,08,i = 4 時的排序過程,21,25,49,25*,完成,16,,08,16,,i = 5j = 4,i = 5j = 3,0 1 2 3 4 5 6,0 1 2 3 4 5 6,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,,25

24、,,25*,16,,16,,21,25,49,25*,08,21,49,25*,08,21,25,49,25*,16,08,16,,16,25,21,,,i = 5j = 2,i = 5j = 1,i = 5j = 0,,16,0 1 2 3 4 5 6,0 1 2 3 4 5

25、 6,0 1 2 3 4 5 6,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,三、插入排序,2）函數(shù)實現(xiàn)void straightInsert(RECORDNODE r[],int n){/*使用直接插入排序法對數(shù)組a(1:n)排序*/for (i=2;i<=n;i++){a[0]=a[i]; /*設(shè)置監(jiān)視哨*/ j=i-1;while

26、(a[0].key<a[j].key){a[j+1]=a[j];j--;}a[j+1]=a[0];}},計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,三、插入排序,3) 算法分析設(shè)待排序?qū)ο髠€數(shù)為n, 則該算法的while循環(huán)執(zhí)行n-1趟。關(guān)鍵碼比較次數(shù)和對象移動次數(shù)與對象關(guān)鍵碼的初始排列有關(guān)。最好情況下, 排序前對象已按關(guān)鍵碼從小到大有序, 每趟只需與前面有序?qū)ο笮蛄械淖詈笠粋€對象比較1次, 移動2次對象,

27、總的關(guān)鍵碼比較次數(shù)為 n-1, 對象移動次數(shù)為 2(n-1)。最壞情況下, 第 i 趟時第 i 個對象必須與前面 i 個對象都做關(guān)鍵碼比較, 并且每做1次比較就要做1次數(shù)據(jù)移動。則總關(guān)鍵碼比較次數(shù)KCN和對象移動次數(shù)RMN分別為,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,三、插入排序,在平均情況下的排序碼比較次數(shù)和對象移動次數(shù)約為 n2/4。因此，直接插入排序的時間復(fù)雜度為 o(n2)。直接插入排序是一種穩(wěn)定的排序方法。,計算機(jī)軟件技術(shù)基礎(chǔ),

28、查找與排序,三、插入排序,2. 折半插入排序1）與直接插入排序相比，除了采用的是折半查找尋找插入的位置外，其它類似。2）算法void BinarySort(RECORDNODE a[],int n){for (i=2;i=low;j--) r[j+1]=r[j];r[low]=r[0];}},計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,三、插入排序,3) 算法分析折半查找比順序查找查找快, 所以折半插入排序就平均性能來說比直接

29、插入排序要快。它所需的關(guān)鍵碼比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o關(guān), 僅依賴于對象個數(shù)。在插入第 i 個對象時, 需要經(jīng)過 ?log2i? +1 次關(guān)鍵碼比較, 才能確定它應(yīng)插入的位置。因此, 將 n 個對象(為推導(dǎo)方便, 設(shè)為 n=2k )用折半插入排序所進(jìn)行的排序碼比較次數(shù)為：,其記錄移動的數(shù)目與直接插入排序相同因此，此算法的時間復(fù)雜度為O(n2)折半插入排序是一個穩(wěn)定的排序算法,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,三、插入排序,

30、3. 希爾排序1) 希爾排序方法又稱為縮小增量排序。2) 該方法的基本思想是 : 設(shè)待排序?qū)ο笮蛄杏?n 個對象, 首先取一個整數(shù) gap < n 作為間隔, 將全部對象分為 gap 個子序列, 所有距離為 gap 的對象放在同一個子序列中,在每一個子序列中分別施行直接插入排序。然后縮小間隔 gap, 例如取 gap = ?gap/2?，重復(fù)上述的子序列劃分和排序工作。直到最后取 gap = 1, 將所有對象放在同一個序列

31、中排序為止。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,開始時 gap 的值較大, 子序列中的對象較少, 排序速度較快; 隨著排序進(jìn)展, gap 值逐漸變小, 子序列中對象個數(shù)逐漸變多, 由于前面工作的基礎(chǔ), 大多數(shù)對象已基本有序, 所以排序速度仍然很快。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,3.希爾排序,3）函數(shù)實現(xiàn)Void shellSort(RECORDNODE s[],

32、int n){/*對記錄數(shù)組s[1:n]進(jìn)行希爾排序*//* d1=n/2,di=di-1/2 */int i,j,d;d=n/2;/*d是間隔*/while(d){/*循環(huán)直到d為0*/for(i=d+1;id;j=j-d)if(s[j].key>s[0].key) s[j]=s[j-d]else break;s[j]=s[0];}d=d/2;}},計算機(jī)

33、軟件技術(shù)基礎(chǔ),查找與排序,3.希爾排序,4) 算法分析Gap的取法有多種。最初 shell 提出取 gap = ?n/2?，gap = ?gap/2?，直到gap = 1。knuth 提出取 gap = ?gap/3? +1。對特定的待排序?qū)ο笮蛄?，可以?zhǔn)確地估算排序碼的比較次數(shù)和對象移動次數(shù)。想要弄清排序碼比較次數(shù)和對象移動次數(shù)與增量選擇之間的依賴關(guān)系，并給出完整的數(shù)學(xué)分析，還沒有人能夠做到。 Knuth利用大量實驗統(tǒng)計資料得

34、出 : 當(dāng) n 很大時，排序碼平均比較次數(shù)和對象平均移動次數(shù)大約在 n1.25 到 1.6n1.25 的范圍內(nèi)。這是在利用直接插入排序作為子序列排序方法的情況下得到的。希爾排序是一種不穩(wěn)定的排序方法,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,四、交換排序,交換排序是根據(jù)序列中兩個結(jié)點關(guān)鍵字的比較結(jié)果，來對換在序列中的位置。算法的特點是將關(guān)鍵字較大的結(jié)點向序列的尾部移動，關(guān)鍵字較小的結(jié)點向序列的前部移動?；舅枷胧莾蓛杀容^待排序?qū)ο蟮呐判虼a,

35、如發(fā)生逆序(即排列順序與排序后的次序正好相反)，則交換之。直到所有對象都排好序為止。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,四、交換排序,1. 冒泡排序基本方法：設(shè)待排序?qū)ο笮蛄兄械膶ο髠€數(shù)為 n。最多作 n-1 趟, i = 1, 2, ?, n-1。在第 i 趟中從后向前，j = n, n-1, ?, i，順次兩兩比較a[j-1]和a[j]。如果發(fā)生逆序，則交換a[j-1]和a[j]。1）過程：對無序表進(jìn)行掃描，當(dāng)發(fā)現(xiàn)相鄰兩個記錄關(guān)

36、鍵字逆序時就進(jìn)行交換，第一次掃描后就將最大關(guān)鍵字記錄沉到底部，而關(guān)鍵字較小的記錄則像氣泡一樣逐漸上浮。然后對剩下的記錄再進(jìn)行掃描，直到某次掃描時不發(fā)生交換，則排序完成。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,1. 冒泡排序,2)算法void BubbleSort(RECORDNODE a[],int n){/*使用冒泡排序算法，對記錄數(shù)組a[1:n}排序*/int i,j;int exchange =

37、1;/*標(biāo)志，記錄是否有交換*/for(i=1;ii;j--)if(a[j-1].key>a[j].key){/*逆序*/a[0]=a[j];a[j]=a[j-1];a[j-1]=a[0];/*交換*/ exchange = 1;/*標(biāo)志置為1,有交換*/}}},計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,1. 冒泡排序,算法也可寫成：void BubbSort(R

38、ECORDNODE a[],int n){int i;for (i=0;ia[j].key){ t=a[i]; a[i]=a[j]; a[j]=t; }},計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,1. 冒泡排序,3) 算法分析第i趟對待排序?qū)ο笮蛄衋[i],a[I+1],?,a[n]進(jìn)行排序, 結(jié)果將該序列中排序碼最小的對象交換到序列的第一個位置(i), 其它對象也都向排序的最終位置移動。在個別情形

39、, 對象可能在排序中途向相反的方向移動。最多做n-1趟冒泡就能把所有對象排好序。在對象的初始排列已經(jīng)按關(guān)鍵字從小到大排好序時,此算法只執(zhí)行一趟起泡,做n-1次關(guān)鍵字比較,不移動對象。這是最好的情形。最壞的情形是算法執(zhí)行n-1趟起泡,第i趟 (1? i? n) 做 n- i 次關(guān)鍵字比較, 執(zhí)行 n-i 次對象交換。這樣在最壞情形下總的關(guān)鍵字比較次數(shù)KCN和對象移動次數(shù)RMN為：,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,1. 冒泡排序,冒泡

40、排序的平均時間復(fù)雜度為O(n2)起泡排序需要一個附加對象以實現(xiàn)對象值的對換。起泡排序是一個穩(wěn)定的排序方法。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,四、交換排序,2. 快速排序1）基本思想快速排序是對冒泡排序的一種改進(jìn)。基本思想是任取待排序?qū)ο笮蛄兄械哪硞€對象 (例如取第一個對象) 作為基準(zhǔn),按照該對象的關(guān)鍵字大小,將整個對象序列劃分為左右兩個子序列： 左側(cè)子序列中所有對象的關(guān)鍵字都小于或等于基準(zhǔn)對象的關(guān)鍵字 右側(cè)子序列中所有對象

41、的關(guān)鍵字都大于基準(zhǔn)對象的關(guān)鍵字基準(zhǔn)對象則排在這兩個子序列中間(這也是該對象最終應(yīng)安放的位置)。然后分別對這兩個子序列重復(fù)施行上述方法，直到所有的對象都排在相應(yīng)位置上為止。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 快速排序,2）分割過程① 選取表中一個元素a[k]（一般選取第一元素），令x=a[k]，稱為控制關(guān)鍵字，用控制關(guān)鍵字和無序區(qū)中其余元素關(guān)鍵字進(jìn)行比較。② 設(shè)置兩個指示器i,j，分別表示線性表第一個和最后一個元素位置。

42、③ 將j逐漸減小，逐次比較a[j]與x，直到出現(xiàn)一個a[j]x，然后將a[i]移到a[j]位置。如此反復(fù)進(jìn)行，直到i=j為止，最后將x移到a[j]位置，完成一趟排序。此時以x為界將原數(shù)組分割成兩個子區(qū)。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 快速排序,3）算法：void QuickSort(RECORDNODE a[],int low,int high){/*對

43、記錄數(shù)組a[low:high]進(jìn)行快速排序*/if(low>=high) return;t=a[low]; i=low; j=high;while(i=t.key) j--;/*從末端向中間搜索*/if(i<j) a[i]=a[j];while(i<j&&a[i]<=t.key) i++;/*從前端向中間搜索*/if(i<j) a[j]=a[i];}a[i]=t;if

44、(low<i-1) QuickSort(a,low,i-1); if(i+1<high) QuickSort(a,i+1,high);},計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,4）舉例：設(shè)序列為{46,55,13,42,94,5,17,70},,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 快速排序,5) 算法分析算法quicksort是一個遞歸的算法, 其遞歸樹如圖所示。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 快速排序,快速排序的趟

45、數(shù)取決于遞歸樹的高度。如果每次劃分對一個對象定位后, 該對象的左側(cè)子序列與右側(cè)子序列的長度相同, 則下一步將是對兩個長度減半的子序列進(jìn)行排序, 這是最理想的情況。在 n個元素的序列中,對一個對象定位所需時間為 O(n)。若設(shè)t(n) 是對 n 個元素的序列進(jìn)行排序所需的時間, 而且每次對一個對象正確定位后, 正好把序列劃分為長度相等的兩個子序列, 此時, 總的計算時間為：T(n)? cn + 2T(n/2) /*

46、c 是一個常數(shù)*/? cn + 2( cn/2 + 2T(n/4) ) = 2cn + 4T(n/4)? 2cn + 4( cn/4 +2T(n/8) ) = 3cn + 8T(n/8) ………? cn log2n + nT(1) = O(n log2n ),計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 快速排序,可以證明, 函數(shù)quicksort的平均計算時間也是O(nlog2n)。實驗結(jié)果表明: 就平均計算時間而言, 快速排序

47、是所有內(nèi)排序方法中最好的一個?？焖倥判蚴沁f歸的，需要有一個棧存放每層遞歸調(diào)用時的指針和參數(shù)。最大遞歸調(diào)用層次數(shù)與遞歸樹的高度一致,理想情況為 ?log2(n+1)? 。因此，要求存儲開銷為 O(log2n)。在最壞的情況, 即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵字從小到大排好序的情況下, 其遞歸樹成為單支樹, 每次劃分只得到一個比上一次少一個對象的子序列?？偟年P(guān)鍵字比較次數(shù)將達(dá),因此，快速排序在最壞情況下的時間復(fù)雜度為O(n2) 快速排序

48、是一種不穩(wěn)定的排序方法。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,用第一個對象作為基準(zhǔn)對象,快速排序退化的例子,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 快速排序,其排序速度退化到簡單排序的水平, 比直接插入排序還慢。占用附加存儲(棧)將達(dá)到O(n)。改進(jìn)辦法: 取每個待排序?qū)ο笮蛄械牡谝粋€對象、最后一個對象和位置接近正中的 3 個對象，取其關(guān)鍵字居中者作為基準(zhǔn)對象。,用居中排序碼對象作為基準(zhǔn)對象,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,五、歸并排序,1

49、. 歸并，是將兩個或兩個以上的有序表合并成一個新的有序表。對象序列a中兩個有序表a[l] …a[m]和a[m+1] …a[n]。它們可歸并成一個有序表, 存于另一對象序列b的b[l] …b[n] 中。這種歸并方法稱為兩路歸并 (2-way merging)。設(shè)變量 i 和 j 分別是表a[l] …a[m]和a[m+1] …a[n]的當(dāng)前檢測指針。變量 k 是存放指針。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,五、歸并排序,當(dāng) i 和 j

50、都在兩個表的表長內(nèi)變化時, 根據(jù)對應(yīng)項的排序碼的大小,依次把排序碼小的對象排放到新表 k 所指位置中；當(dāng) i 與 j 中有一個已經(jīng)超出表長時，將另一個表中的剩余部分照抄到新表中。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,五、歸并排序,2. 歸并排序歸并排序算法就是利用兩路歸并過程進(jìn)行排序的。其基本思想是：假設(shè)初始對象序列有 n 個對象，首先把它看成是 n 個長度為 1 的有序子序列 (歸并項)，先做兩兩歸并，得到 ?n / 2? 個長度為

51、 2 的歸并項 (如果 n 為奇數(shù)，則最后一個有序子序列的長度為1)；再做兩兩歸并，…，如此重復(fù)，最后得到一個長度為 n 的有序序列。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,五、歸并排序,兩路歸并算法的函數(shù)實現(xiàn)void merge(int start,int end,int m,RECORDNODE a[]){/*將有序表a(start:m)和a(m+1:end)歸并為一個新的有序表a(start:end)*/RECORDNODE t

52、emp[MAXSIZE];int i,j,k;i=start;j=m+1;k=start;while(i<=m&&j<=end)if(a[i].key<a[i].key){temp[i]=a[i];k++;I++;}else{temp[k]=a[j];k++;j++;}while(j<=end){temp[k]=a[j];k++;j++;}while(i<=m

53、){temp[k]=a[i];k++;i++;}for(i=start;i<=end;I++) a[i]=temp{i};/*臨時表的內(nèi)容存回到a中*/},計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,五、歸并排序,歸并排序的算法void MergeSort(RECORDNODE a[],int n){/*對長度為n的數(shù)組a排序*/Int length,left,right;left=0;length=1;while(l

54、ength<N){right=min(n-1,left+2*length-1)//限制right的值，使其不越界Merge(left,right,length,a);if(right+length<N) left=right+1;//右邊還有待合并段else{length*=2;left=1;}//從新開始下一趟排序}},計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,五、歸并排序,計算機(jī)軟件技術(shù)基礎(chǔ),

55、查找與排序,五、歸并排序,3. 算法分析1) 時間復(fù)雜度在函數(shù)MergeSort中while循環(huán)將被執(zhí)行l(wèi)og2n次在while循環(huán)中，將調(diào)用Merge函數(shù)n/(2length)次而在Merge函數(shù)中，將比較length次,故在while循環(huán)中，將比較O(n)次因此，此算法的時間復(fù)雜度為O(nlogn)2) 空間復(fù)雜度歸并排序占用附加存儲較多, 需要另外一個與原待排序?qū)ο髷?shù)組同樣大小的輔助數(shù)組。這是這個算法的缺點。3

56、) 歸并排序是一個穩(wěn)定的排序算法,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,六、各種排序方法的比較,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,六、各種排序方法的比較,? 原則1）待排序記錄的個數(shù)2）記錄本身的大小3）關(guān)鍵字的分布情況4）對排序穩(wěn)定性的要求5）現(xiàn)有語言工具條件等,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,六、各種排序方法的比較,? 結(jié)論1）若待排序的記錄數(shù)n較?。╪≤50），則可采用插入排序或直接選擇排序。且由于插入排序的移動次數(shù)

57、較選擇排序多，因此若記錄本身較大時宜采用選擇排序。2）若n較大，則應(yīng)采用時間復(fù)雜度O(nlog2n)的排序方法，如快速排序或堆排序。當(dāng)排序的關(guān)鍵字是隨機(jī)分布時，快速排序的平均運行時間最短；堆排序只需1個輔助空間，且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況，但堆排序的建堆時間較長。3）若待排序記錄按關(guān)鍵字基本有序，則宜采用插入排序或冒泡排序。,計算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,六、各種排序方法的比較,4）從方法的穩(wěn)定性看，所有時間復(fù)雜度為O(