【正文】 r[j+1]=r[0]。 性能分析 R[0]的使用： ?把 R[I]放在 R[0]中， R[I]的位置用來(lái)向后移動(dòng)記錄 ?比較過(guò)程中，又防止下標(biāo) j 出界，起到了監(jiān)視哨的作用。 2. 冒泡排序 基本思想： 首先將 R[1]和 R[2]比較，若逆序，則交換 R[1]和 R[2]，然后比較 R[2]和 R[3],….. 直到第 n1個(gè)記錄和第 n個(gè)記錄比較，經(jīng)過(guò)這一趟比較，最大的記錄被放在最后一個(gè)位置上；然后對(duì)前 n1個(gè)記錄進(jìn)行同樣的操作，則具有次大關(guān)鍵字的記錄被放在第 n1個(gè)記錄的位置上；重復(fù)以上過(guò)程，直到?jīng)]有記錄交換為止。 for (i=1。 i++) { for ( j=1。 j++) if (r[j+1].key r[j].key) r[j] ? r[j+1]。 for(i=1。 i++) { flag=1。 j=ni。 r[j] ? r[j+1]。 } } ? Flag的作用 用來(lái)指示掃描中有沒(méi)有進(jìn)行數(shù)據(jù)交換，每趟掃描開(kāi)始前將其置 1。如某趟掃描后 flag仍為 1，說(shuō)明此趟掃描已無(wú)數(shù)據(jù)互換，則排序結(jié)束，不必再繼續(xù)掃描了。 基本思想： ?第一趟從 R[0]— R[n1]中最小的記錄，并 R[1]交換；第二趟從 R[2]— R[n]選擇最小的 J記錄并與 R[2]交換；依次進(jìn)行下去，進(jìn)行了 (n1)趟掃描以后就完成了整個(gè)排序過(guò)程。第 i 趟掃描只需將該位置的元素與第 i個(gè)元素交換即可。 圖 簡(jiǎn)單選擇排序 ( 0) [ 13 15 6 10 20 8 3 19 ] ( 1) 3 [ 15 6 10 20 8 13 19 ] ( 2) 3 6 [ 15 10 20 8 13 19 ] ( 3) 3 6 8 [ 10 20 15 13 19 ] ( 4) 3 6 8 10 [ 20 15 13 19 ] ( 5) 3 6 8 10 13 [ 15 20 19 ] ( 6) 3 6 8 10 13 15 [ 20 19 ] ( 7) 3 6 8 10 13 15 19 20 簡(jiǎn)單選擇排序算法 void selectsort (r[ ], n) { int i, j, k。 i=n1。 /*k始終記住到目前為止最小者的下標(biāo) for (j=i+1。 j++) if (r[ j]. key r[ k]. key) k=j。 } } 簡(jiǎn)單選擇排序分析 ?簡(jiǎn)單選擇排序在 (n1)趟掃描中共需進(jìn)行n(n1)/2次比較，最壞情況下的互換次數(shù)為 (n1)，整個(gè)算法的時(shí)間復(fù)雜性為 O(n2)。 ?簡(jiǎn)單選擇排序是不穩(wěn)定的排序算法。 ?簡(jiǎn)單選擇 1. 輸入是已知的； 2. 每一趟排序結(jié)束后，所選擇的元素都 都放在了最終的位置上。 ?基本思想：把整個(gè)文件分成若干個(gè)較小的子文件，對(duì)每個(gè)子文件進(jìn)行直接插入排序；在文件的記錄達(dá)到基本有序時(shí)，再對(duì)整個(gè)文件進(jìn)行一次直接插入排序。 i=t。 /*以 dk[i]為增量進(jìn) /* 行一趟希爾排序 } Void shellpass (r[], n, d) /*一趟希爾排序 */ { int i, k。 i++) { r[0]=r [i]。 while((k0) amp。 (r[0].keyr[k].key)) { r[k+d}.key=r[k].key。 } r[k+d]=r[0]。 ?任何增量序列能使用，但必須保證 t1=1；當(dāng)增量序列為 1時(shí)，該算法就退化成直接插入排序了。 快速排序 ?快速排序是由冒泡排序改進(jìn)而得到的，又稱(chēng)為分區(qū)交換排序，是目前內(nèi)部排序中速度較快的方法。 ?第一次劃分以后，再用相同的算法對(duì)劃成的兩部分分別進(jìn)行類(lèi)似的運(yùn)算，即從每一部分中任選一個(gè)數(shù)據(jù)將其劃分成更小的兩部分。 ?圖 ，圖中的方括號(hào)表示待排序部分。 ?假設(shè)原始數(shù)據(jù)已存于一個(gè)一維數(shù)組 r中，具體的做法是：設(shè)兩個(gè)指示器 i和 j，初始時(shí) i指向數(shù)組中的第一個(gè)數(shù)據(jù)， j指向最末一個(gè)數(shù)據(jù)。 ?圖 過(guò)程。 ?最后一行只有一個(gè)括號(hào)，說(shuō)明 i與 j相等了，此單元即是數(shù)據(jù) 13的最終位置。 x=r[i]。amp。 if (ij) /*已找到了滿足 { r[i]=r[j]。 } 快速排序算法續(xù) while (r[i].key =) amp。 ( ij )) i++。 j。 r[i]=x。 } ?整個(gè)快速排序過(guò)程如下： Void quicksort(r[], low, hig) { int k。 Quicksort(r, low, k1)。 } } 快速排序分析 ?當(dāng)初始序列有序或基本有序時(shí)，快速排序就接近于冒泡排序了，其時(shí)間復(fù)雜度為 O(n*n). ?該算法是霍爾 1962年提出的。當(dāng)時(shí)他就發(fā)現(xiàn)了以上的問(wèn)題，他在文章中建議用兩種方法改進(jìn)：產(chǎn)生一個(gè)隨機(jī)數(shù)，或選擇一個(gè)小樣本中值。 快速排序分析 ?快速排序的平均時(shí)間復(fù)雜性為 O(nlogn)，對(duì) n較大的情況，這種算法是平均速度最快的排序算法，但當(dāng) n很小時(shí)，此方法往往比其他簡(jiǎn)單排序方法還要慢。 ?快速排序是不穩(wěn)定的。 ?（大根）堆（ Heap）：在一棵完全二叉樹(shù)中，每個(gè)結(jié)點(diǎn)如果有兒子的話，此結(jié)點(diǎn)必須大于或等于其兒子結(jié)點(diǎn)。 ?設(shè)某堆的結(jié)點(diǎn)數(shù)共有 n個(gè)，順序?qū)⑺鼈兇嫒胍痪S數(shù)組 r[] 中。 ? ?2/j?由堆的定義可知，其根結(jié)點(diǎn)（即在數(shù)組中下標(biāo)為 1的結(jié)點(diǎn)）具有最小的關(guān)鍵字，堆排序就是利用這一特點(diǎn)進(jìn)行的。這個(gè)調(diào)整過(guò)程稱(chēng)為“ 篩選 ”。 /*R[i+1]和 R[i+2]為根的左右子樹(shù)是 x=r[i]。amp。 if (r[j].key) /*j為左右兒子中較小者的下標(biāo) { r[i]=r[j]。 j=2*i } else break 。 /*把 x放在 i的位置上 } 篩選算法 ?介紹第 1個(gè)問(wèn)題，即把一個(gè)無(wú)序的序列建成一個(gè)堆。 ?例： 堆排序算法 void heapsort (r[], n) { int i。 i=1。 /* 初始建堆 */