NOI排序算法課程膠片

1、排序1. 冒泡排序2. 快速排序3. 直接插入排序4. 希爾排序5. 選擇排序6. 小結冒泡排序算法描述設待排序記錄序列中的記錄個數為n一般地，第i趟起泡排序從1到n-i+1依次比較相鄰兩個記錄的關鍵字，如果發(fā)生逆序，則交換之其結果是這n-i+1個記錄中，關鍵字最大的記錄被交換到第n-i+1的位置上，最多作n-1趟。算法示例10 1 2 3 4 5算法示例20 1 2 3 4 5總體演示初始關鍵字第一趟排序第四趟排序第二趟排序第三趟排序第五趟排序算法實現輸入n 個數給a1 到 anfor j=1 to n-1for i=1 to n-jaiai+1真假aiai+1輸出a1 到 an#inclu

2、de main() int a11,i,j,t; printf(Input 10 numbers:n); for(i=1;i11;i+) scanf(%d,&ai); printf(n); for(j=1;j=9;j+) for(i=1;iai+1) t=ai; ai=ai+1; ai+1=t; printf(The sorted numbers:n); for(i=1;i11;i+) printf(%d ,ai); 1. 冒泡排序2. 快速排序3. 直接插入排序4. 希爾排序5. 選擇排序6. 小結快速排序 快速排序是通過比較關鍵碼、交換記錄，以某個記錄為界(該記錄稱為支點)，將待排序列分成

3、兩部分一部分所有記錄的關鍵碼大于等于支點記錄的關鍵碼另一部分所有記錄的關鍵碼小于支點記錄的關鍵碼 算法描述任取待排序記錄序列中的某個記錄(例如取第一個記錄)作為基準(樞),按照該記錄的關鍵字大小,將整個記錄序列劃分為左右兩個子序列左側子序列中所有記錄的關鍵字都小于或等于基準記錄的關鍵字 右側子序列中所有記錄的關鍵字都大于基準記錄的關鍵字基準記錄則排在這兩個子序列中間(這也是該記錄最終應安放的位置)。然后分別對這兩個子序列重復施行上述方法，直到所有的記錄都排在相應位置上為止?；鶞视涗浺卜Q為樞軸（或支點）記錄。取序列第一個記錄為樞軸記錄，其關鍵字為Pivotkey指針low指向序列第一個記錄位置指

4、針high指向序列最后一個記錄位置算法示例1始關鍵字pivotkey一次交換二次交換三次交換high-1完成一趟排序lowhighlowlowlowlowlowhighhighhighhighhigh算法示例212完成一趟排序分別進行快速排序有序序列算法分析快速排序是一個遞歸過程;利用序列第一個記錄作為基準，將整個序列劃分為左右兩個子序列。只要是關鍵字小于基準記錄關鍵字的記錄都移到序列左側；快速排序的趟數取決于遞歸樹的高度。如果每次劃分對一個記錄定位后, 該記錄的左側子序列與右側子序列的長度相同, 則下一步將是對兩個長度減半的子序列進行排序, 這是最理想的情況 131. 冒泡排序2. 快速排序

5、3. 直接插入排序4. 希爾排序5. 選擇排序6. 小結直接插入排序 算法描述：記錄存放在數組R0.n-1中，排序過程的某一中間時刻，R被劃分成兩個子區(qū)間R0i-1和Ri.n-1，其中：前一個子區(qū)間是已排好序的有序區(qū)；后一個子區(qū)間則是當前未排序的部分?；静僮鲗斍盁o序區(qū)的第1個記錄Ri插入到有序區(qū)R0.i-1中適當的位置，使R0i變?yōu)樾碌挠行騾^(qū) 直接插入排序 操作細節(jié)：當插入第i(i1)個對象時, 前面的r0, r1, , ri-1已經排好序。用ri的關鍵字與ri-1, ri-2, 的關鍵字順序進行比較(和順序查找類似)，如果小于，則將rx向后移動(插入位置后的記錄向后順移)找到插入位置即將

6、ri插入直接插入排序 實用例子：已知待序的一組記錄的初始排列為：21, 25, 49, 25*, 16, 080 1 2 3 4 5算法示例0 1 2 3 4 5 temp250 1 2 3 4 5 temp4925*0 1 2 3 4 5算法示例0 1 2 3 4 5 temp160 1 2 3 4 5 temp080 1 2 3 4 5完成算法實現void InsertSort (int r , int n ) / 假設關鍵字為整型，放在向量r中 int i, j, temp; for (i = 1;i0;j- -) /從后向前順序比較，并依次后移 if ( temp rj-1 ) rj

7、= rj-1; else break; rj = temp; 算法分析關鍵字比較次數和記錄移動次數與記錄關鍵字的初始排列有關。最好情況下, 排序前記錄已按關鍵字從小到大有序, 每趟只需與前面有序記錄序列的最后一個記錄比較1次, 移動2次記錄, 總的關鍵字比較次數為 n-1, 記錄移動次數為 2(n-1)在平均情況下的關鍵字比較次數和記錄移動次數約為 n2/4。直接插入排序是一種穩(wěn)定的排序方法直接插入排序最大的優(yōu)點是簡單，在記錄數較少時，是比較好的辦法1. 冒泡排序2. 快速排序3. 直接插入排序4. 希爾排序5. 選擇排序6. 小結希爾排序 希爾排序又稱縮小增量排序是1959年由D.L.She

8、ll提出來的 算法描述首先取一個整數 gap n(待排序記錄數) 作為間隔, 將全部記錄分為 gap 個子序列, 所有距離為 gap 的記錄放在同一個子序列中在每一個子序列中分別施行直接插入排序。然后縮小間隔 gap, 例如取 gap = gap/2重復上述的子序列劃分和排序工作，直到最后取gap = 1, 將所有記錄放在同一個序列中排序為止。算法示例已知待排序的一組記錄的初始排列為：21, 25, 49, 25*, 16, 080 1 2 3 4 5 算法示例t 30 1 2 3 4 50 1 2 3 4 5t 2t 1算法分析開始時 gap 的值較大, 子序列中的記錄較少, 排序速度較快隨

9、著排序進展, gap 值逐漸變小, 子序列中記錄個數逐漸變多,由于前面大多數記錄已基本有序, 所以排序速度仍然很快Gap的取法有多種。 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。1. 冒泡排序2. 快速排序3. 直接插入排序4. 希爾排序5. 選擇排序6. 小結排序過程首先通過n-1次比較，從n個數中找出最小的， 將它與第一個數 交換第一趟選擇排序，結果最小的數被安置在第一個元素位置上再通過n-2次比較，從剩余的n-1個數中找出關鍵字次小的記錄，將它與第二個數交換第二趟選擇排序重復上述過程，共經過n-1趟排序后，排序結束排序示例初始：初始： 49 38

10、 65 97 76 13 27 kji=11349一趟：一趟： 13 38 65 97 76 49 27 i=22738二趟：二趟： 13 27 65 97 76 49 38 三趟：三趟： 13 27 38 97 76 49 65 四趟：四趟： 13 27 38 49 76 97 65 五趟：五趟： 13 27 38 49 65 97 76 六趟：六趟： 13 27 38 49 65 76 97 kkkkjjjjjjjjjj算法示例0 1 2 3 4 5算法示例0 1 2 3 4 5最小者最小者各趟排序后的結果算法示例0 1 2 3 4 5i =2時選擇排序的過程i k j i k j i k

11、 j 算法示例0 1 2 3 4 5i k j 算法實現輸入n 個數給a1 到 anfor i=1 to n-1for j=i+1 to najak真假k=j輸出a1 到 ank=iaiaki != k真假#include main() int a11,i,j,k,x; printf(Input 10 numbers:n); for(i=1;i11;i+) scanf(%d,&ai); printf(n); for(i=1;i10;i+) k=i; for(j=i+1;j=10;j+) if(ajak) k=j; if(i!=k) x=ai; ai=ak; ak=x; printf(The s

12、orted numbers:n); for(i=1;i11;i+) printf(%d ,ai); 1. 冒泡排序2. 快速排序3. 直接插入排序4. 希爾排序5. 選擇排序6. 小結36基本概念排序排序（Sorting）： 簡單地說，排序就是把一組記錄一組記錄按照某個（或某幾個）字段的值以遞增（由小到大）或遞減（由大到?。┑拇涡蛑匦屡帕械倪^程。（如按年齡從小到大排序）學號姓名年齡性別2004001張佳18男2004002王鵬19男2004003劉寧17女2004004李娟18女2004005陳濤19男2004006李小燕18女37作為比較基礎的一個(或多個)字段，稱為排序碼排序碼。排序碼可以

13、是數值、符號或符號串。排序碼排序碼不一定是關鍵碼，是關鍵碼，關鍵碼可以作為排序碼。關鍵碼是唯一的，但排序碼不一定唯一。排序碼不唯一時，排序的結果可能不唯一。參與排序的對象，稱為記錄。一個記錄可以包含多個字段。如果記錄集合中存在多個排序碼排序碼相同的記錄，經過排序后，排序碼排序碼相同的記錄的前后次序保持不變，則這種排序方法稱為是穩(wěn)定穩(wěn)定的，否則是不穩(wěn)定不穩(wěn)定的。排序碼 與 關鍵碼（primary key）38 排序方法可以分為五種 插入插入排序、選擇選擇排序、交換交換排序、分配分配排序和歸并歸并排序。 在排序過程中，全部記錄存放在內存，則稱為內排序內排序，如果排序過程中需要使用外存，則稱為外排序。外排序。排序的類型評價排序算法好壞的標準 執(zhí)行算法所需的時間 執(zhí)行算法所需要的附加空間 算法本身的復雜程度也是考慮的一個因素排序的時間開銷時間開銷是算法好壞的最重要的標志排序的時間開銷衡量標準: 算法執(zhí)行中的比較次數（必須）。 算法執(zhí)行中的移動次數（有可能避免）。通常會關注最壞情況和平均情況的開銷。排序算法的評價39階段小節(jié)幾種