1、第九章：分類。學習本章要求掌握排序的基本概念和相關(guān)術(shù)語。碩士：插入排序的基本思想，直接插入排序算法、二進制插入排序算法和希爾排序算法的實現(xiàn)過程和算法。并了解插入排序算法的時間效率和空間效率。碩士：交換排序的基本思想，冒泡排序算法，快速排序的實現(xiàn)過程和算法。了解氣泡排序和快速排序的算法評估。碩士：選擇性排序的基本思想，簡單的選擇性排序，實現(xiàn)算法和算法評估的堆排序。碩士：合并排序的基本思想和雙向合并的實現(xiàn)算法。默認排序數(shù)據(jù)結(jié)構(gòu)：待排序的記錄按順序存儲，待排序記錄的定義為：#define MAXSIZE 100 /*假設(shè)順序表的最大長度為100 */typedef int KeyType；/*假設(shè)關(guān)

2、鍵字類型是整數(shù)類型*/typedef結(jié)構(gòu)關(guān)鍵字類型關(guān)鍵字；/*關(guān)鍵字項*/其他類型其他；/*其他項目*/數(shù)據(jù)類型；/*數(shù)據(jù)元素類型*/typedef結(jié)構(gòu)數(shù)據(jù)類型r maxsize1/* r0空閑或充當哨兵*/int length；/*序列表長度*/sqlist；/*序列表類型*/，9.1基本概念，排序定義將數(shù)據(jù)元素(或記錄)的任意序列重新排列成按鍵排序的序列，這稱為排序分類。根據(jù)待排序記錄的內(nèi)部位置進行排序：待排序記錄存儲在內(nèi)存外部進行排序：排序過程中需要訪問外部內(nèi)存的排序的穩(wěn)定性。如果關(guān)鍵元素之間的位置關(guān)系相同，則排序前后是一致的。稱這種排序方法為穩(wěn)定的，否則就是不穩(wěn)定的。排序的基本操作是比

3、較兩個關(guān)鍵字的大小，并將記錄從一個位置移動到另一個位置。排序方法：內(nèi)部排序(本章討論的方法):在排序過程中，所有要排序的記錄都存儲在內(nèi)存中。插入排序：直接插入排序，分割插入排序，表格插入排序，希爾排序交換排序：氣泡排序，快速排序選擇排序：簡單選擇排序，樹選擇排序，堆排序合并排序：雙向合并排序基數(shù)排序：多鍵排序，鏈基數(shù)排序外排序：排序過程多路平衡合并是基于排序所需的工作量。簡單排序法：T(n)=O(n)高級排序法：T(n)=O(logn)基數(shù)排序法：T(n)=O(d.n)。評估排序算法的質(zhì)量有兩個主要標準。首先是執(zhí)行算法所需的時間；第二是執(zhí)行算法所需的額外空間；此外，算法本身的復雜性也是一個需要

4、考慮的因素。因為排序是一個經(jīng)常使用的操作，所以排序的時間成本是算法最重要的標志。排序的時間成本可以通過算法執(zhí)行中的比較和移動次數(shù)來衡量。同時，有時也要考慮排序的穩(wěn)定性。9.2插入排序，9.2.1直接插入排序，假設(shè)要排序的n個記錄r0，R1，rn-1存儲在一個數(shù)組中，當插入記錄Ri(i=1，2n-1)時，記錄集被分成兩個區(qū)間R0，Ri-1和Ri，Rn-1，其中前一個子區(qū)間已經(jīng)被排序。直接插入排序采用順序存儲結(jié)構(gòu)。基本思想是每次將一條要排序的記錄插入到排序后的子序列的適當位置，根據(jù)其關(guān)鍵字大小，直到所有記錄都被插入。例如，49 38 65 97 76 13 27，I=2 38 (38 49) 65

5、 97 76 13 27，I=3 65 (38 49 65) 97 76 13 27，I=4 97 (38 49 65 97) 76 13 27，I=5 76(38 47 I=6 13(13 38 49 65 76 97)27，I=1()，I=7(11設(shè)立監(jiān)視哨；尋找插入位置；移動元素；插入；您可以在尋找插入位置時移動元素。該算法在以下最佳情況下評估時間復雜度：如果要排序的記錄按關(guān)鍵字從小到大(正序)排列，則關(guān)鍵字比較的數(shù)量為：最壞的情況：如果要排序的記錄按關(guān)鍵字從小到大(反序)排列，則關(guān)鍵字比較的數(shù)量為：如果要排序的記錄是隨機的，則關(guān)鍵字比較的平均數(shù)量為：記錄移動的數(shù)量為：t (n)=o()

6、?？臻g復雜度：S(n)=O(1)，直接插入排序是一種穩(wěn)定的排序算法，9.2.2二進制插入排序的排序過程：使用二分搜索法方法確定插入位置的排序稱為，例如，I=1 (30) 13 70 85 39 42 620，I=2 13(13 30)70 85 39 I=7 6(6 13 30 39 42 70 85)20，i=8 20 (6 13 20 30 39 42 70 85)，對于(I=2；I=n；設(shè)立監(jiān)視哨；尋找插入位置；移動元素；插入；void binarysertsport(sqlist * s)/*將序列表s半插入并排序*/int low、high、mid對于(I=2；ilength1)S-

7、r0=S-ri；/*保存要插入的元素*/low=1；高=I-1；/*設(shè)置初始間隔*/while(low r0 . keys-rmid . key)low=mid 1；/*插入位置在上半部分區(qū)域*/否則高=中1；/*插入位置在下半部分區(qū)域*/*而*/為(j=I-1；j=高1；J-)/* high 1是插入位置*/s-rj 1=s-rj；/*向后移動元素以留出插入空間*/s-rhigh 1=s-r0；/*將元素插入*/*進行*/* binarysertsport */，效率分析：教科書是錯誤的！否則，排序不穩(wěn)定！算法描述，2。二進制插入排序，二進制插入排序的比較次數(shù)與待排序記錄的初始狀態(tài)無關(guān)，而只

8、取決于記錄的數(shù)量。插入第I條記錄時，其比較次數(shù)最多為N條記錄。排序的總比較次數(shù)為：移動記錄的次數(shù)與直接插入排序的次數(shù)相同，因此時間復雜度仍為O(n2)。二分法插入排序是一種穩(wěn)定的排序方法/注意確保if (s-r0)。鑰匙-rmid。鍵)低=中1；該算法的輔助空間為0(1)。注：推導過程可參考北京大學教材9.2.4希爾排序法(收縮增量法)，殼排序也稱為收縮增量排序。首先，要排列的整個記錄序列被分成幾個子序列，用于直接插入和排序，當整個序列中的記錄“基本有序”時，整個序列可以通過直接插入一次來排序。殼排序的一個特點是子序列的組成不是簡單的“逐段”，而是由以一定增量分隔的記錄組成的子序列。算法描述，希爾排序算法描述：空殼插入(數(shù)據(jù)類型r，i