一、選擇排序

1.簡單選擇排序

基本思想：假設排序表為[1,…,n]，第i趟排序即從[i,…,n]中選擇關鍵字最小的元素與L[i]交換

eg：給定關鍵字序列{87，45，78，32，17，65，53，09}，用簡單選擇排序算法進行排序

代碼實現：

void SelectSort(ElemType A[],int n){for(i=0;i<n-1;i++){min=i;for(j=i+1;j<n;j++){if(A[j]<A[min]){min=j;}}if(min!=i){swap(A[i],A[min]);}}
}

空間效率：O(1)

時間效率：O(n^2)

穩定性：穩定

2.堆排序

（1）構造大根堆

eg：下面的序列中，（）是堆

A.1,2,8,4,3,9,10,5? ? B.1,5,10,6,7,8,9,2? ? C.9,8,7,6,4,8,2,1? ? D.9,8,7,6,5,4,3,7

答案：A

（2）刪除元素

輸出棧頂元素后，將堆的最后一個元素與棧頂元素交換，此時堆的性質被破壞

（3）插入元素

對堆進行插入操作時，先將新結點放在堆的末端，再對這個新結點向上執行調整操作

空間效率：O(1)

時間效率：O(nlog2n)

穩定性：不穩定

eg：設有5000個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10個記錄關鍵字，則用下列（B）方法可以達到目的

A.快速排序? B.堆排序? C.冒泡排序? D.希爾排序

二、歸并排序

“歸并”的含義是將兩個或兩個以上的有序表組合成一個新的有序表

2路歸并排序：

空間效率：O(n)

時間效率：O(nlog2n)

穩定性：穩定

eg：一組記錄值為（12，38，35，25，74，50，63，90），按2路歸并排序方法對序列進行一趟歸并后的結果是（12，38，25，35，50，74，63，90）

三、基數排序

基數排序不基于比較和移動進行排序，而是基于關鍵字各位的大小排序

個位：

十位：

百位：

空間效率：O(r)

時間效率：O(d(n+r))? ?d為趟數

穩定性：穩定

eg：如果將所有中國人按照生日（不考慮年份，只考慮月、日）來排序，那么使用下列排序算法中的（D）算法最快

A.歸并排序? B.希爾排序? C.快速排序? D.基數排序

四、各種排序算法的比較

eg：在直接插入排序和快速排序中，若初始數據基本有序，則選用（直接插入排序）；在冒泡排序和堆排序中，若要求數據的穩定性，則選用（冒泡排序）

eg：以下四種排序方法中，需要附加的內存空間(空間復雜度)最大的是（D）

A.插入排序? B.選擇排序? C.快速排序? D.歸并排序

eg：一趟排序結束之后不一定能夠選出一個元素放在其最終位置上的是（D）

A.簡單選擇排序? B.冒泡排序? C.快速排序? D.希爾排序

五、習題

?

答案：A

答案：√

答案：A

答案：A

答案：不是；7，18，21，41，58，63，29，43

答案：

第一趟：12，51，23，55，07，49，36，72，12'

第二趟：12，23，51，55，07，36，49，72，12'

第三趟：07，12，23，36，49，51，55，72，12'

第四趟：07，12，12'，23，36，49，51，55，72

答案：C

答案：快速排序；O(nlog2n)

答案：D