10.1 知識點分析
1．排序基本概念：
（1）排序
將資料元素的任意序列，重新排列成乙個按關鍵字有序（遞增或遞減）的序列的過程稱為排序。
（2）排序方法的穩定和不穩定
若對任意的資料元素序列，使用某個排序方法，對它按關鍵字進行排序，若對原先具有相同鍵值元素間的位置關係，排序前與排序後保持一致，稱此排序方法是穩定的；反之，則稱為不穩定的。
（3）內排序
整個排序過程都在記憶體進行的排序稱為內排序，本書僅討論內排序。
（4）外排序
待排序的資料元素量大，以致記憶體一次不能容納全部記錄，在排序過程中需要對外存進行訪問的排序稱為外排序。
2．直接插入排序
直接插入排序法是將乙個記錄插到已排序好的有序表中，從而得到乙個新的，記錄數增1的有序表。
3．二分插入排序
二分插入排序法是用二分查詢法在有序表中找到正確的插入位置，然後移動記錄，空出插入位置，再進行插入的排序方法。
4．希爾排序
希爾排序的基本思想是：先選取乙個小於n的整數d1作為第乙個增量，把待排序的資料分成d1個組，所有距離為d1的倍數的記錄放在同乙個組內，在各組內進行直接插入排序，每一趟排序會使資料更接近於有序。然後，取第二個增量d2，d2< d1，重複進行上述分組和排序，直至所取的增量di=1（其中di< di-1 < ……< d2< d1），即所有記錄在同一組進行直接插入排序後為止。
5．氣泡排序
冒泡法是指每相鄰兩個記錄關鍵字比大小，大的記錄往下沉（也可以小的往上浮）。每一遍把最後乙個下沉的位置記下，下一遍只需檢查比較到此為止；到所有記錄都不發生下沉時，整個過程結束。
6．快速排序
快速排序法是通過一趟排序，將待排序的記錄組分割成獨立的兩部分，其中前一部分記錄的關鍵字均比樞軸記錄的關鍵字小；後一部分記錄的關鍵字均比樞軸記錄的關鍵字大，樞軸記錄得到了它在整個序列中的最終位置並被存放好。第二趟再分別對分割成兩部分子序列，再進行快速排序，這兩部分子序列中的樞軸記錄也得到了最終在序列中的位置而被存放好，並且它們又分別分割出獨立的兩個子串行……。
7．簡單選擇排序
（1）初始狀態：整個陣列r劃分成兩個部分，即有序區（初始為空）和無序區。
（2）基本操作：從無序中選擇關鍵字值最小的記錄，將其與無序區的第乙個記錄交換（實質是新增到有序區尾部）。
（3）從初態（有序區為空）開始，重複步驟（2），直到終態（無序區為空）。
8．堆排序
（1）把用陣列來儲存待排序的記錄，將r[1..n]看成是一棵完全二叉樹。
（2）利用完全二叉樹雙親結點和孩子結點之間的內在關係，將其建成堆，從而在當前無序區中選擇關鍵字最大的記錄，然後將最大的關鍵字取出。
（3）對剩下的關鍵字再建堆，得到次大的關鍵字。
如此反覆進行，直到最小值，從而將全部關鍵字排序好為止。
9．歸併排序
歸併排序是將兩個或兩個以上的有序子表合併成乙個新的有序表。其基本思想是：
（1）將n個記錄的待排序序列看成是有n個長度都為1的有序子表組成。
（2）將兩兩相鄰的子表歸併為乙個有序子表。
（3重複上述步驟，直至歸併為乙個長度為n的有序表。
10．各種排序方法的比較
評估乙個排序法的好壞，除了用排序的時間及空間外，尚需考慮穩定度、最壞狀況和程式的編寫難易程度。以下就常用的排序法按最壞情況下所需時間、平均所需時間、是否屬於穩定排序、所需的額外空間等以表10-1來表示。
10-1 排序效能比較表
10.2 典型習題分析
【例1】 當初始序列已按關鍵字有序時，用直接插入演算法進行排序，需要比較次數為（ ）。
a．n-1 b．log2nc．2log2nd．n2
分析：直接插入排序是每趟從待排序列中取乙個元素，按關鍵字從有序區間的尾部向前查詢插入位置。當初始序列已按關鍵字值有序時，則每趟比較乙個就找到了正確位置，也就是本身位置，則n個元素需要進行n-1趟排序，故總的比較為n-1次，答案為a。
【例2】一組記錄的鍵值為（12，38，35，25，74，50，63，90），按2路歸併排序方法對該序列進行一趟歸併後的結果為（ ）。
a．12,38,25,35,50,74,63,90b．12,38,35,25,74,50,63,90
c．12,25,35,38,50,74,63,90d．12,35,38,25,63,50,74,90
分析：2路歸併排序是將兩個有序子表合併成乙個新的有序表。其基本思想是：
（1）將n個記錄的待排序序列看成是有n個長度都為1的有序子表組成；
（2）將兩兩相鄰的子表歸併為乙個有序子表；
（3）重複上述步驟，直至歸併為乙個長度為n的有序表。
初始值12 38 35 25 74 50 63 90
第一趟排序結果：12 38 25 35 50 74 63 90
答案為a。
【例3】待排序的記錄初態是按碼值降序排列的，若欲將其按碼值公升序重新排列，則直接插入排序、簡單選擇排序和氣泡排序哪乙個更好?
解： 當待排序的記錄初態是按碼值降序排列時，用氣泡排序法比較和交換的次數最多；而直接插入排序和簡單選擇排序的比較次數相近。但是直接插入排序時記錄的移動次數比較多。
所以，當待排序的記錄初態是按碼值降序排列，要按碼值公升序重新排列時，用簡單選擇排序更好。
【例4】設待排序記錄的初態是按關鍵字值遞增排列的，分別用堆排序、快速排序、氣泡排序和歸併排序方法對其仍按遞增進行排序，則哪種排序方法最省時間？哪種排序方法最費時間？
解： 堆排序和歸併排序所用時間複雜度為o(nlog2n)；當待排記錄的初始狀態是按關鍵字值遞增時，用快速排序法，因為每次選取的中間元素都是最小的，故劃分出的左右兩個區域乙個為空，另乙個比原區域少乙個元素，使得元素比較只比上一趟少一次，所以總的時間複雜度為o(n2)；對於氣泡排序來說，其平均所需時間和最壞所需時間都是o(n2)，但是如果在演算法中設定乙個標誌flag，用於記錄每趟排序中是否出現記錄的交換。如果沒有交換，則表明待排序序列已經有序，則可結束排序。
綜上所述本題採用這樣氣泡排序所用時間最省；採用快速排序最費時間。
【例5】設有n個互不相同的元素，試問能否用少於2n-3次的比較次數，從這n個關鍵字中選出最大元素和最小元素？
解： 若採用先選最小元素（通過n-1次比較得到），再在剩餘的n-1個元素中選最大元素（通過n-2次比較得到）的方法，則共需要 (n-1)+(n-2)=2n-3次比較。
可以通過成對比較元素，來減少比較次數。具體方法如下：
先比較第1對元素，較小者送當前最小變數min，較大者送當前最大變數max；然後依次對第i對元素（i=2，3……，），進行比較。對於每一對元素，做一次比較（大小）以後，分別將較小者和當前最小元素變數min比較；將較大者和當前最大元素變數max比較（共比較3次）。若較小者小於min，則令較小者取代當前的min；若較大者大於max，則令較大者取代當前的max。
待所有元素比較完成以後，max和min分別就是最大元素和最小元素。
因為第1對元素只比較了1次，其餘的各對元素分別都需要進行3次比較，所以總的比較次數是：1+(-1)╳3=3-2，顯然小於2n-3次。
【例6】已知序列（503，87，512，61，908，170，897，275，653，462）請給出採用快速排序法作公升序排序時的第一趟的結果。
分析：設待排序列的下界和上界分別為low和high，r[low]是樞軸元素，一趟快速排序的具體過程如下：
（1）首先將r[low]中的記錄儲存到pivot變數中，用兩個整型變數i，j分別指向low和high所在位置上的記錄；
（2）先從j所指的記錄起自右向左逐一將關鍵字和進行比較，當找到第1個關鍵字小於的記錄時，將此記錄複製到i所指的位置上去；
（3）然後從i+1所指的記錄起自左向右逐一將關鍵字和進行比較，當找到第1個關鍵字大於的記錄時，將該記錄複製到j所指的位置上去；
（4）接著再從j1所指的記錄重複以上的（2）、（3）兩步，直到i=j為止，此時將pivot中的記錄放回到i（或j）的位置上。一趟快速排序完成。
排序過程如下：
503 87 512 61 908 170 897 275 653 462
交換 462 87 512 61 908 170 897 275 653 503
交換462 87 503 61 908 170 897 275 653 512
交換 462 87 275 61 908 170 897 503 653 512
交換462 87 275 61 503 170 897 908 653 512
交換[462 87 275 61 170] 503 [897 908 653 512]
第一趟快速排序結果是462，87，275，61，170，503，897，908，653，512。
資料結構第9章 排序
第9章排序 一 複習要點 排序是使用最頻繁的一類演算法。排序分內排序與外排序。內排序演算法主要分5大類，有12個演算法。在插入排序類中討論了直接插入排序 二分法插入排序 表插入排序和shell排序演算法 在交換排序類中討論了起泡排序和快速排序演算法 在選擇排序類中討論了簡單選擇排序 錦標賽排序和堆排...
資料結構習題第10章
第10章內部排序 一 選擇題 1.下列排序方法中，穩定的排序方法是 a.簡單選擇排序 b.氣泡排序 c.希爾排序 d.快速排序 2.在下列排序演算法中,哪乙個演算法的時間複雜度與初始排序無關 a.直接插入排序 b.氣泡排序 c.快速排序 d.簡單選擇排序 3.排序方法中，從未排序序列中依次取出元素與...
資料結構 C語言 第10章排序自測題
第9章排序 一 填空題 每空1分，共24分 1.大多數排序演算法都有兩個基本的操作 和 2.在對一組記錄 54，38，96，23，15，72，60，45，83 進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置至少需比較次。3.在插入和選擇排序中，若初始資料基本正序，則選用 若初始...