概述插入排序 （直接插入、折半插入、表插入排序、希爾排序

1、概述插入排序 （直接插入、折半插入、表插入排序、希爾排序）交換排序 （起泡排序、快速排序）選擇排序 （簡(jiǎn)單選擇排序、樹形選擇排序、堆排序）歸并排序 基數(shù)排序小結(jié),第十章 內(nèi)部排序,概述,排序：將一組雜亂無章的數(shù)據(jù)排列成一個(gè)按關(guān)鍵字有序的序列。 數(shù)據(jù)表(datalist): 它是待排序數(shù)據(jù)對(duì)象的有限集合。關(guān)鍵字(key): 通常數(shù)據(jù)對(duì)象有多個(gè)屬性域，即多個(gè)數(shù)據(jù)成員組成，其中有一個(gè)屬性域可用來區(qū)分對(duì)象，作為排序依據(jù)。該域即

2、為關(guān)鍵字。每個(gè)數(shù)據(jù)表用哪個(gè)屬性域作為關(guān)鍵字，要視具體的應(yīng)用需要而定。即使是同一個(gè)表，在解決不同問題的場(chǎng)合也可能取不同的域做關(guān)鍵字。,主關(guān)鍵字: 如果在數(shù)據(jù)表中各個(gè)對(duì)象的關(guān)鍵字互 不相同，這種關(guān)鍵字即主關(guān)鍵字。按照主關(guān)鍵字 進(jìn)行排序，排序的結(jié)果是唯一的。次關(guān)鍵字: 數(shù)據(jù)表中有些對(duì)象的關(guān)鍵字可能相 同，這種關(guān)鍵字稱為次關(guān)鍵字。按照次關(guān)鍵字 進(jìn)行排序，排序的結(jié)果可能不唯一。排序算法的穩(wěn)定性: 如果在對(duì)象序列中有兩個(gè)對(duì)

3、 象r[i]和r[j]，它們的關(guān)鍵字 k[i] == k[j]，且在 排序之前，對(duì)象r[i]排在r[j]前面。如果在排序 之后，對(duì)象r[i]仍在對(duì)象r[j]的前面，則稱這個(gè) 排序方法是穩(wěn)定的，否則稱這個(gè)排序方法是不 穩(wěn)定的。,內(nèi)排序與外排序: 內(nèi)排序是指在排序期間數(shù)據(jù)對(duì)象全部存放在內(nèi)存的排序；外排序是指在排序期間全部對(duì)象個(gè)數(shù)太多，不能同時(shí)存放在內(nèi)存，必須根據(jù)排序過程的要求，不斷在內(nèi)、外存之間移動(dòng)的排序。排序的時(shí)間

4、開銷: 排序的時(shí)間開銷是衡量算法好壞的最重要的標(biāo)志。排序的時(shí)間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動(dòng)次數(shù)來衡量。各節(jié)給出算法運(yùn)行時(shí)間代價(jià)的大略估算一般都按平均情況進(jìn)行估算。對(duì)于那些受對(duì)象關(guān)鍵字序列初始排列及對(duì)象個(gè)數(shù)影響較大的，需要按最好情況和最壞情況進(jìn)行估算。,靜態(tài)排序: 排序的過程是對(duì)數(shù)據(jù)對(duì)象本身進(jìn)行物理地重排，經(jīng)過比較和判斷，將對(duì)象移到合適的位置。這時(shí)，數(shù)據(jù)對(duì)象一般都存放在一個(gè)順序的表中。動(dòng)態(tài)排序: 給每個(gè)對(duì)象增加

5、一個(gè)鏈接指針，在排序的過程中不移動(dòng)對(duì)象或傳送數(shù)據(jù)，僅通過修改鏈接指針來改變對(duì)象之間的邏輯順序，從而達(dá)到排序的目的。算法執(zhí)行時(shí)所需的附加存儲(chǔ): 評(píng)價(jià)算法好壞的另一標(biāo)準(zhǔn)。靜態(tài)排序過程中所用到的數(shù)據(jù)表的定義，體現(xiàn)了抽象數(shù)據(jù)類型的思想。,衡量排序方法的標(biāo)準(zhǔn)排序時(shí)所需要的平均比較次數(shù)排序時(shí)所需要的平均移動(dòng)排序時(shí)所需要的平均輔助存儲(chǔ)空間,插入排序 (Insert Sorting),直接插入排序的基本思想是：當(dāng)插入第i (i ?

6、1) 個(gè)對(duì)象時(shí)，前面的V[0], V[1], …, v[i-1]已經(jīng)排好序。這時(shí)，用v[i]的關(guān)鍵字與v[i-1], v[i-2], …的關(guān)鍵字順序進(jìn)行比較，找到插入位置即將v[i]插入，原來位置上之后的所有對(duì)象依次向后順移。,插入排序的基本方法是：每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵字大小，插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上，直到對(duì)象全部插入為止。,直接插入排序 (Insert Sort),,,各趟排序結(jié)果,21,25,49,25

7、*,16,08,0 1 2 3 4 5,,0 1 2 3 4 5 temp,21,25,49,25*,16,08,25,i = 1,0 1 2 3 4 5 temp,,21,25,49,25*,16

8、,08,49,i = 2,,,,,,,21,25,49,25*,16,08,0 1 2 3 4 5,,0 1 2 3 4 5 temp,21,25,49,25*,16,08,i = 4,0 1 2 3 4 5

9、 temp,,21,25,49,25*,16,08,i = 5,,,,,i = 3,25*,,,,16,,,,,08,,,,,,,16,,49,16,16,,,21,25,49,25*,16,08,0 1 2 3 4 5,0 1 2 3 4 5 temp,21,25,49,

10、25*,08,i = 4 時(shí)的排序過程,0 1 2 3 4 5 temp,21,25,49,25*,完成,16,,08,16,,i = 4j = 3,i = 4j = 2,,25,,25*,16,,16,,21,25,49,25*,08,0 1 2 3 4 5,0

11、1 2 3 4 5 temp,21,49,25*,08,0 1 2 3 4 5 temp,21,25,49,25*,16,08,16,,16,25,21,,,i = 4j = 1,i = 4j = 0,i = 4j = -1,,16,直接插入排序的算法 （p265算法10.

12、1）void InsertSort(SqList &L) { for (int i=2;i<=L.length;++i)if (LT(L.r[i].key,L.r[i-1].key)) { L.r[0]=L.r[i]; // L.r[0]為監(jiān)視哨 for (int j=i-1; LT(L.r[0].key,L.r[j].key); --j)L.r[j+1]=L.r[

13、j]; L.r[j+1]=L.r[0]; } },算法分析,若設(shè)待排序的對(duì)象個(gè)數(shù)為L(zhǎng).length= n，則該算法的主程序執(zhí)行n-1趟。關(guān)鍵字比較次數(shù)和對(duì)象移動(dòng)次數(shù)與對(duì)象關(guān)鍵字的初始排列有關(guān)。最好情況下，排序前對(duì)象已經(jīng)按關(guān)鍵字大小從小到大有序，每趟只需與前面的有序?qū)ο笮蛄械淖詈笠粋€(gè)對(duì)象的關(guān)鍵字比較 1 次，移動(dòng) 2 次對(duì)象，總的關(guān)鍵字比較次數(shù)為 n-1，對(duì)象移動(dòng)次數(shù)為 2(n-1)。,分析：一個(gè)記錄

14、的輔助存儲(chǔ)空間 監(jiān)視哨比較次數(shù)最小比較次數(shù)：Cmin=n-1最大比較次數(shù)： Cmax=平均比較次數(shù)： Cavg=(n-1)(n+4)/4移動(dòng)次數(shù)最小移動(dòng)次數(shù)：Mmin=0最大移動(dòng)次數(shù)：Mmax=平均移動(dòng)次數(shù)： Mavg=(n+8)(n-1)/4,若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均情況。在平均情況下的關(guān)鍵字比較次數(shù)和對(duì)象移動(dòng)次數(shù)約為 n2/4。因此，直接插入排序的時(shí)

15、間復(fù)雜度為 o(n2)。直接插入排序是一種穩(wěn)定的排序方法。,折半插入排序 (Binary Insertsort),折半插入排序基本思想是：設(shè)在順序表中有一 個(gè)對(duì)象序列 V[0], V[1], …, v[n-1]。其中，v[0], V[1], …, v[i-1] 是已經(jīng)排好序的對(duì)象。在插入 v[i] 時(shí)，利用折半搜索法尋找 v[i] 的插入位置。,折半插入排序的算法void BInsertSort(SqList &L)

16、{ int low,high,mid; for (int i=2;i=high+1;--j) L.r[j+1]=L.r[j]; L.r[high+1]=L.r[0];}}說明：low 或者 high+1為插入點(diǎn) 穩(wěn)定排序,算法分析,二分查找比順序查找快，所以二分插入排序就平均性能來說比直接插入排序要快。它所需要的關(guān)鍵字比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o關(guān)，僅依賴于對(duì)象個(gè)數(shù)。

17、在插入第 i 個(gè)對(duì)象時(shí)，需要經(jīng)過 ?log2i? +1 次關(guān)鍵字比較，才能確定它應(yīng)插入的位置。因此，將 n 個(gè)對(duì)象（為推導(dǎo)方便，設(shè)為 n=2k )用二分插入排序所進(jìn)行的關(guān)鍵字比較次數(shù)為：,當(dāng) n 較大時(shí)，總關(guān)鍵字比較次數(shù)比直接插入排序的最壞情況要好得多，但比其最好情況要差。在對(duì)象的初始排列已經(jīng)按關(guān)鍵字排好序或接近有序時(shí)，直接插入排序比二分插入排序執(zhí)行的關(guān)鍵字比較次數(shù)要少。二分插入排序的對(duì)象移動(dòng)次數(shù)與直接插入排序相同，依賴于對(duì)象的初始

18、排列。二分插入排序是一個(gè)穩(wěn)定的排序方法。,希爾排序 (Shell Sort),希爾排序方法又稱為“縮小增量”排序。該方法的基本思想是：先將整個(gè)待排對(duì)象序列按照一定間隔分割成為若干子序列，分別進(jìn)行直接插入排序，然后縮小間隔，對(duì)整個(gè)對(duì)象序列重復(fù)以上的劃分子序列和分別排序工作，直到最后間隔為1，此時(shí)整個(gè)對(duì)象序列已 “基本有序”，進(jìn)行最后一次直接插入排序。,,,21,25,49,25*,16,08,0 1

19、 2 3 4 5,,21,25*,i = 1,,08,49,gap = 3,,25,16,49,25,16,08,49,25*,08,21,25,21,25*,16,希爾排序過程示例,,,21,25,49,25*,16,08,0 1 2 3 4 5,,21,i = 2,,08,49,gap =

20、2,,25,16,49,16,25*,08,21,25,49,25*,08,16,21,25*,25,,,21,25,49,25*,16,08,0 1 2 3 4 5,,21,i = 3,08,gap = 1,25,16,49,25*,開始時(shí) gap（間隔值） 的值較大，子序列中的對(duì)象較少，排序速度較快；隨著排序進(jìn)展，gap 值逐漸變小，子序列中對(duì)

21、象個(gè)數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對(duì)象已基本有序，所以排序速度仍然很快。,希爾排序的算法void ShellSort(SqList &L, int dlta[],int t){for (int k=0;k<t;++k){ShellInsert(L,dlta[k]);}}說明：dlta[3]={5，3，1},//一趟希爾排序,按間隔dk劃分子序列void ShellInsert(SqList

22、 &L, int gap){for (int i=gap+1;i0 && LT(L.r[0].key,L.r[j].key); j-=gap)L.r[j+gap]=L.r[j];L.r[j+gap]=L.r[0];}}},,,算法分析,對(duì)特定的待排序?qū)ο笮蛄?，可以?zhǔn)確地估算關(guān)鍵字的比較次數(shù)和對(duì)象移動(dòng)次數(shù)。但想要弄清關(guān)鍵字比較次數(shù)和對(duì)象移動(dòng)次數(shù)與增量選擇之間的依賴關(guān)系，并給出完整

23、的數(shù)學(xué)分析，還沒有人能夠做到。gap的取法有多種。最初 shell 提出取 gap = ?n/2?，gap = ?gap/2?，直到gap = 1。后來Knuth 提出取gap = ?gap/3? +1。還有人提出都取奇數(shù)為好，也有人提出各gap互質(zhì)為好。其他取法：教材p272 倒數(shù)第二段,Knuth利用大量的實(shí)驗(yàn)統(tǒng)計(jì)資料得出，當(dāng) n 很大時(shí)，關(guān)鍵字平均比較次數(shù)和對(duì)象平均移動(dòng)次數(shù)大約在 n1.25 到 1.6n1.25 的范圍內(nèi)。這是

24、在利用直接插入排序作為子序列排序方法的情況下得到的。,,初始關(guān)鍵字序列：,增量d＝5,第一趟排序結(jié)果：,增量d＝3,第二趟排序結(jié)果：,增量d＝1,第三趟排序結(jié)果：,練習(xí)題,交換排序 ( Exchange Sort ),起泡排序的基本方法是：設(shè)待排序?qū)ο笮蛄兄械膶?duì)象個(gè)數(shù)為 n。最多作 n-1 趟排序。在第 i 趟中順次兩兩比較r[j-1].Key和r[j].Key，j = i, i+1, ?, n-i-1。如果發(fā)生逆序，則交換r[j-1

25、]和r[j]。,交換排序的基本思想是兩兩比較待排序?qū)ο蟮年P(guān)鍵字，如果發(fā)生逆序(即排列順序與排序后的次序正好相反)，則交換之，直到所有對(duì)象都排好序?yàn)橹埂?起泡排序 (Bubble Sort),,,21,25,49,25*,16,08,0 1 2 3 4 5,,21,25*,i = 1,,49,,25,16,49,chang=1,08,,,,

26、25*,,,chang=1,i = 2,i = 3,08,16,chang=1,25*,,25,21,49,21,25,16,08,,起泡排序過程示例,,,25*,0 1 2 3 4 5,i = 4,49,16,chang=1,08,25,21,,25*,0 1 2 3

27、 4 5,i = 5,49,16,chang=0,08,25,21,void BubbleSort(SqList &L){ int i, j, tag; j = L.length-1; do{ tag=1; for(i=1; i<=j; i++) if( L.r[i+1].key< L.r[i].key )

28、 { L.r[0]= L.r[i+1]; L.r[i+1]= L.r[i]; L.r[i]= L.r[0]; tag=0; } if( !tag ) j--; } while( !tag &&j ); return;},起泡排序的算法——1,void BubbleS

29、ort(SqList &L){for (int i=L.length, change=TRUE;i>1 && change; --i) {change = FALSE;for (int j=1; j<i; ++j) if (LT(L.r[j+1].key,L.r[j].key)) { ElemType temp=L.r[j];L.r[

30、j]=L.r[j+1];L.r[j+1]=temp;change = TRUE;} }},起泡排序的算法——2,特 點(diǎn),至少比較1次，至多比較n-1次；一次確定位置；可實(shí)現(xiàn)部分排序穩(wěn)定排序,算法分析,在對(duì)象的初始排列已經(jīng)按關(guān)鍵字從小到大排好序時(shí)，此算法只執(zhí)行一趟起泡，做 n-1 次關(guān)鍵字比較，不移動(dòng)對(duì)象。這是最好的情形。最壞的情形是算法執(zhí)行了n-1趟起泡，第 i 趟 (1? i? n) 做了 n-

31、 i 次關(guān)鍵字比較，執(zhí)行了n-i 次對(duì)象交換。這樣在最壞情形下總的關(guān)鍵字比較次數(shù)KCN和對(duì)象移動(dòng)次數(shù)RMN為：,,起泡排序需要一個(gè)附加對(duì)象以實(shí)現(xiàn)對(duì)象值的對(duì)換。起泡排序是一個(gè)穩(wěn)定的排序方法。,練習(xí)題,初始關(guān)鍵字序列：,49,38,65,97,76,13,27,49*,快速排序 (Quick Sort),快速排序方法的基本思想是任取待排序?qū)ο笮蛄兄械哪硞€(gè)對(duì)象 (例如取第一個(gè)對(duì)象) 作為樞軸(pivot)，按照該對(duì)象的關(guān)鍵字大小，將整個(gè)對(duì)象

32、序列劃分為左右兩個(gè)子序列： 左側(cè)子序列中所有對(duì)象的關(guān)鍵字都小于或等于樞軸對(duì)象的關(guān)鍵字 右側(cè)子序列中所有對(duì)象的關(guān)鍵字都大于樞軸對(duì)象的關(guān)鍵字樞軸對(duì)象則排在這兩個(gè)子序列中間(這也是該對(duì)象最終應(yīng)安放的位置)。,,然后分別對(duì)這兩個(gè)子序列重復(fù)施行上述方法，直到所有的對(duì)象都排在相應(yīng)位置上為止。算法描述,QuickSort ( List ) { if ( List的長(zhǎng)度大于1) {將序列List劃分為兩個(gè)子序列

33、 LeftList 和 Right List; QuickSort ( LeftList );QuickSort ( RightList ); 將兩個(gè)子序列 LeftList 和 RightList 合并為一個(gè)序列List; }},,,,,21,25,49,25*,16,08,0 1 2 3

34、 4 5,,21,25*,i = 1,,49,,25,16,25,16,08,49,pivot,08,25*,49,21,i = 2,i = 3,08,16,25*,25,21,pivot,pivot,pivot,,,,,,21,25,49,25*,16,08,0 1 2 3 4 5,25*,i =

35、1劃分,25,16,25,16,08,49,pivotpos,08,25*,49,08,16,25*,25,21,,,,pivotpos,21,比較4次交換25,16,i,,i,pivotpos,21,比較1次交換49,08,49,low pivotpos,交換21,08,快速排序的算法void QSort(SqList &L, int low, int high){if (low

36、< high){int pivotloc = Partition(L,low,high);QSort(L,low, pivotloc-1);PrintST(L);QSort(L,pivotloc+1, high);PrintST(L);}}void QuickSort(SqList &L){QSort(L,1,L.length);},int Partition(SqList &am

37、p;L, int low, int high) { L.r[0] = L.r[low]; int pivotkey = L.r[low].key; while (low = pivotkey) --high;L.r[low] = L.r[high];while (low<high && L.r[low].key <= pivotkey) ++low;L.r[high] = L.r[l

38、ow]; }L.r[low]=L.r[0];return low;},,,,,,算法quicksort是一個(gè)遞歸的算法，其遞歸樹如圖所示。算法partition利用序列第一個(gè)對(duì)象作為樞軸，將整個(gè)序列劃分為左右兩個(gè)子序列。算法中執(zhí)行了一個(gè)循環(huán)，只要是關(guān)鍵字小于樞軸對(duì)象關(guān)鍵字的對(duì)象都移到序列左側(cè)，最后樞軸對(duì)象安放到位，函數(shù)返回其位置。,,21,,25*,25,49,08,16,,算法分析,從快速排序算法的

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

40、 // c是一個(gè)常數(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 )可以證明，函數(shù)quicksort的平均計(jì)算時(shí)間也是o(nlog2n)。實(shí)驗(yàn)結(jié)果表明：就平均計(jì)算時(shí)間而言，快速排序是我們所討論的所有內(nèi)排序方

41、法中最好的一個(gè)。,快速排序是遞歸的，需要有一個(gè)棧存放每層遞歸調(diào)用時(shí)的指針和參數(shù)。最大遞歸調(diào)用層次數(shù)與遞歸樹的深度一致，理想情況為 ?log2(n+1)? 。因此，要求存儲(chǔ)開銷為 o(log2n)。在最壞的情況，即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵字從小到大排好序的情況下，其遞歸樹成為單支樹，每次劃分只得到一個(gè)比上一次少一個(gè)對(duì)象的子序列。這樣，必須經(jīng)過 n-1 趟才能把所有對(duì)象定位，而且第 i 趟需要經(jīng)過 n-i 次關(guān)鍵字比較才能找到第 i

42、個(gè)對(duì)象的安放位置，總的關(guān)鍵字比較次數(shù)將達(dá)到,其排序速度退化到簡(jiǎn)單排序的水平，比直接插入排序還慢。占用附加存儲(chǔ)(即棧)將達(dá)到o(n)。若能更合理地選擇基準(zhǔn)對(duì)象，使得每次劃分所得的兩個(gè)子序列中的對(duì)象個(gè)數(shù)盡可能地接近，可以加速排序速度，但是由于對(duì)象的初始排列次序是隨機(jī)的，這個(gè)要求很難辦到。有一種改進(jìn)辦法：取每個(gè)待排序?qū)ο笮蛄械牡谝粋€(gè)對(duì)象、最后一個(gè)對(duì)象和位置接近正中的3個(gè)對(duì)象，取其關(guān)鍵字居中者作為基準(zhǔn)對(duì)象。,用第一個(gè)對(duì)象作為基準(zhǔn)對(duì)象,快速排

43、序退化的例子,08 16 21 25 25* 49,08,0 1 2 3 4 5 pivot,初始,16 21 25 25* 49,08,16,21 25 25* 49,21,08 16,25,25 25* 49,08 16

44、 21,25* 49,25*,08 16 21 25,,49,08 16 21 25 25*,i = 1,i = 2,i = 3,i = 4,i = 5,用居中關(guān)鍵字對(duì)象作為基準(zhǔn)對(duì)象,快速排序是一種不穩(wěn)定的排序方法。對(duì)于 n 較大的平均情況而言，快速排序是“快速”的，但是當(dāng) n 很小時(shí)，這種排序方法往往比其它簡(jiǎn)單排序方法還要慢。,08 16 21

45、 25 25* 49,0 1 2 3 4 5 pivot,21,初始,08 16,21,25 25* 49,08,25*,08,16,21,25,25*,49,i = 1,i = 2,38,65,97,13,27,49*,55,1,2,3,4,5,6,7,8,49,04,9,,,i,j,,,練習(xí)題:快速排序中的一

46、趟劃分,,快速排序中的一趟劃分(續(xù)),38,65,97,13,27,49*,55,1,2,3,4,5,6,7,8,49,04,9,49,L.r[j]與pivot比較，L.r[j]小則與L.r[i]交換；否則j減1,,L.r[j] 與L.r[i]交換，i加1,快速排序中的一趟劃分(續(xù)),38,65,97,13,27,49*,55,1,2,3,4,5,6,7,8,04,49,9,49,pivot,L.r[i]與pivot比較，L.r[i]大

47、則與L.r[j]交換；否則i增1,快速排序中的一趟劃分(續(xù)),L.r[i]與pivot比較，L.r[i]大則與L.r[j]交換；否則i增1,38,65,97,13,27,49*,55,1,2,3,4,5,6,7,8,04,49,9,49,pivot,,L.r[i]與L.r[j]交換，j減1,快速排序中的一趟劃分(續(xù)),38,49,97,13,27,49*,55,1,2,3,4,5,6,7,8,04,65,9,49,,L.r[j]與piv

48、ot比較，L.r[j]小則與L.r[i]交換；否則j減1,快速排序中的一趟劃分(續(xù)),38,49,97,13,27,49*,55,1,2,3,4,5,6,7,8,04,65,9,49,pivot,L.r[j]與pivot比較，L.r[j]小則與L.r[i]交換；否則j減1,快速排序中的一趟劃分(續(xù)),L.r[j]與pivot比較，L.r[j]小則與L.r[i]交換；否則j減1,38,49,97,13,27,49*,55,1,2,3,4,

49、5,6,7,8,04,65,9,49,pivot,L.r[j]小則與L.r[i]交換，i加1,,快速排序中的一趟劃分(續(xù)),pivot,38,27,97,13,49,49*,55,1,2,3,4,5,6,7,8,04,65,9,49,pivot,L.r[i]與pivot比較，L.r[i]大則與L.r[j]交換；否則i增1,L.r[i]大則與L.r[j]交換，j減1,,快速排序中的一趟劃分(續(xù)),pivot,L.r[j]與pivot比較，

50、L.r[j]小則與L.r[i]交換；否則j減1,38,27,49,13,97,49*,55,1,2,3,4,5,6,7,8,04,65,9,49,pivot,L.r[j]小則與L.r[i]交換，i加1,,快速排序中的一趟劃分(續(xù)),38,27,13,49,97,49*,55,1,2,3,4,5,6,7,8,04,65,9,49,pivot,當(dāng)i與j相等時(shí)，樞軸元素確定了位置i，結(jié)束本次劃分,,選擇排序的基本思想是：每一趟 (例如第 i

51、趟，i = 1, …, n-1) 在后面的 n-i+1 個(gè)待排序?qū)ο笾羞x出關(guān)鍵字最小的對(duì)象, 作為有序?qū)ο笮蛄械牡?i 個(gè)對(duì)象。待到第 n-1 趟作完，待排序?qū)ο笾皇Ｏ?個(gè)，就不用再選了。,選擇排序(Selection Sort),基本步驟為：i從1開始，直到n-1，進(jìn)行n-1趟排序，第i 趟的排序過程為： 在一組對(duì)象r[i]～r[n] (i=1,2,…,n-1)中選擇具有最小關(guān)鍵字的對(duì)象；并和第 i 個(gè)對(duì)象進(jìn)行交換；,簡(jiǎn)單選擇排序

52、(Simple Selection Sort),簡(jiǎn)單選擇排序的算法void SelectSort(SqList &L) { for (int i=1; i L.r[j].key) k=j; if (i!=k){ ElemType temp=L.r[i]; L.r[i]=L.r[k]; L.r[k]=temp; }

53、}},,,,,,21,25,49,25*,16,08,0 1 2 3 4 5,21,25*,i = 1,49,25,16,25,16,08,49,08,25*,49,21,i = 2,i = 3,08,16,25*,25,21,初始,最小者 08交換21,08,最小者 16交換25,16,最小者 21交換49,21,,,,,49,

54、25*,0 1 2 3 4 5,25*,i = 5,25,16,08,49,25*,49,21,結(jié)果,i = 4,08,16,25,21,最小者 25*無交換,最小者 25無交換,25,21,16,08,各趟排序后的結(jié)果,,,,,0 1 2 3 4

55、 5,49,16,08,25*,49,21,08,25*,25,21,i =2時(shí)選擇排序的過程,,,,i k j,49,25,08,25*,16,21,,,i k j,,49 ? 25,25* ? 25,16,,,,25,i k j,16 < 25,,49,25,0

56、8,25*,16,21,0 1 2 3 4 5,i k j,,,,21 ? 16,k 指示當(dāng)前序列中最小者,算法分析,直接選擇排序的關(guān)鍵字比較次數(shù)KCN與對(duì)象的初始排列無關(guān)。第 i 趟選擇具有最小關(guān)鍵字對(duì)象所需的比較次數(shù)總是 n-i-1

57、次，此處假定整個(gè)待排序?qū)ο笮蛄杏?n 個(gè)對(duì)象。因此，總的關(guān)鍵字比較次數(shù)為,對(duì)象的移動(dòng)次數(shù)與對(duì)象序列的初始排列有關(guān)。當(dāng)這組對(duì)象的初始狀態(tài)是按其關(guān)鍵字從小到大有序的時(shí)候，對(duì)象的移動(dòng)次數(shù)RMN = 0，達(dá)到最少。最壞情況是每一趟都要進(jìn)行交換，總的對(duì)象移動(dòng)次數(shù)為RMN = 3(n-1)。直接選擇排序是一種不穩(wěn)定的排序方法。,錦標(biāo)賽排序 (Tournament Tree Sort)樹形選擇排序(Tree Selection Sort),它的

58、思想與體育比賽時(shí)的淘汰賽類似。首先取得 n 個(gè)對(duì)象的關(guān)鍵字，進(jìn)行兩兩比較，得到 ?n/2? 個(gè)比較的優(yōu)勝者(關(guān)鍵字小者)，作為第一步比較的結(jié)果保留下來。然后對(duì)這 ?n/2? 個(gè)對(duì)象再進(jìn)行關(guān)鍵字的兩兩比較，…，如此重復(fù)，直到選出一個(gè)關(guān)鍵字最小的對(duì)象為止。在圖例中，最下面是對(duì)象排列的初始狀態(tài)，相當(dāng)于一棵滿二叉樹的葉結(jié)點(diǎn)，它存放的是所有參加排序的對(duì)象的關(guān)鍵字。,,,,,,,,,,,,,,,,如果 n 不是2的 k 次冪，則讓葉結(jié)點(diǎn)數(shù)補(bǔ)足到滿

59、足 2k-1 < n ? 2k 的2k個(gè)。葉結(jié)點(diǎn)上面一層的非葉結(jié)點(diǎn)是葉結(jié)點(diǎn)關(guān)鍵字兩兩比較的結(jié)果。最頂層是樹的根。,08,Winner,21,08,08,63,25*,21,21,25,49,25*,16,08,63,tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14],勝者樹的概念,每次兩兩比較的結(jié)果是把關(guān)鍵字小者作為優(yōu)勝者上升到雙親結(jié)

60、點(diǎn)，稱這種比賽樹為勝者樹。位于最底層的葉結(jié)點(diǎn)叫做勝者樹的外結(jié)點(diǎn)，非葉結(jié)點(diǎn)稱為勝者樹的內(nèi)結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)除了存放對(duì)象的關(guān)鍵字 key 外，還存放了此對(duì)象是否要參選的標(biāo)志 Active 和此對(duì)象在滿二叉樹中的序號(hào)index。勝者樹最頂層是樹的根，表示最后選擇出來的具有最小關(guān)鍵字的對(duì)象。,,,,,,,,,,,,,,,,08,Winner (勝者),21,08,08,63,25*,21,21,25,49,25*,16,08,63,tree[7

61、] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14],形成初始勝者樹（最小關(guān)鍵字上升到根）,,a[0],關(guān)鍵字比較次數(shù) : 6,,,,,,,,,,,,,,,,16,Winner (勝者),21,16,16,63,25*,21,21,25,49,25*,16,,63,tree[7] tree[8] tree[9] tree[10] tree[11]

62、 tree[12] tree[13] tree[14],輸出冠軍并調(diào)整勝者樹后樹的狀態(tài),,a[1],關(guān)鍵字比較次數(shù) : 2,,,,,,,,,,,,,,,,21,Winner (勝者),21,63,,63,25*,21,21,25,49,25*,,,63,tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14],輸出亞軍并調(diào)整勝者樹后樹的狀態(tài),

63、,a[2],關(guān)鍵字比較次數(shù) : 2,,,,,,,,,,,,,,,,25,Winner (勝者),25,63,,63,25*,25,,25,49,25*,,,63,tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14],輸出第三名并調(diào)整勝者樹后樹的狀態(tài),,a[3],關(guān)鍵字比較次數(shù) : 2,,,,,,,,,,,,,,,,25*,Winner (勝者

64、),25*,63,,63,25*,,,,49,25*,,,63,tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14],輸出第四名并調(diào)整勝者樹后樹的狀態(tài),,a[4],關(guān)鍵字比較次數(shù) : 2,,,,,,,,,,,,,,,,63,Winner (勝者),,63,,63,,,,,,,,,63,tree[7] tree[8] tree[9] tr

65、ee[10] tree[11] tree[12] tree[13] tree[14],全部比賽結(jié)果輸出時(shí)樹的狀態(tài),,a[6],關(guān)鍵字比較次數(shù) : 2,算法分析,錦標(biāo)賽排序構(gòu)成的樹是滿的完全二叉樹，其深度為 ?log2(n+1)?，其中 n 為待排序元素個(gè)數(shù)。除第一次選擇具有最小關(guān)鍵字的對(duì)象需要進(jìn)行 n-1 次關(guān)鍵字比較外，重構(gòu)勝者樹選擇具有次小、再次小關(guān)鍵字對(duì)象所需的關(guān)鍵字比較次數(shù)均為 O(log2n)?？傟P(guān)鍵字比較次數(shù)為O(n

66、log2n)。對(duì)象的移動(dòng)次數(shù)不超過關(guān)鍵字的比較次數(shù)，所以錦標(biāo)賽排序總的時(shí)間復(fù)雜度為O(nlog2n)。這種排序方法雖然減少了許多排序時(shí)間，但是使用了較多的附加存儲(chǔ)。,,如果有 n 個(gè)對(duì)象，必須使用至少 2n-1 個(gè)結(jié)點(diǎn)來存放勝者樹。最多需要找到滿足 2k-1 < n ? 2k 的k，使用 2*2k-1 個(gè)結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)包括關(guān)鍵字、對(duì)象序號(hào)和比較標(biāo)志三種信息。錦標(biāo)賽排序是一個(gè)穩(wěn)定的排序方法。,,堆排序 (Heap Sort)

67、,利用堆及其運(yùn)算，可以很容易地實(shí)現(xiàn)選擇排序的思路。堆排序分為兩個(gè)步驟：第一步，根據(jù)初始輸入數(shù)據(jù)，利用堆的調(diào)整算法 HeapAdjust ( ) 形成初始堆，第二步，通過一系列的對(duì)象交換和重新調(diào)整堆進(jìn)行排序。,給定一組關(guān)鍵字，初始態(tài)存儲(chǔ)時(shí)是一個(gè)完全二叉樹堆的建立對(duì)堆的篩選與建立的重復(fù)交替,,堆排序 (Heap Sort),給定一組關(guān)鍵字，初始態(tài)存儲(chǔ)時(shí)是一個(gè)完全二叉樹堆的建立： 對(duì) m/2 1,的元素依次進(jìn)行篩

68、選：若kik2i(k2i+1)且kik2i且ki>k2i+1，則ki與較小的哪個(gè)交換若k2i=k2i+1)< ki,則ki與k2i交換對(duì)堆的篩選與建立的重復(fù)交替,,,,,,,,,,建立初始的最大堆,21,25,25*,49,16,08,1,2,3,4,5,6,,i,,21,25,25*,16,49,08,1,3,6,5,4,2,,i,,21 25 49 25* 16 08,,,,,,初始關(guān)鍵字集合,21 2