軟考軟件設(shè)計師專題講義十：常用的算法設(shè)計方法

　　容易看出，對n個記錄進行歸并排序的時間復雜度為Ο(nlogn)。即：每一趟歸并的時間復雜度為O(n)，總共需進行l(wèi)ogn趟。

　　下面我們比較一下上面談到的各種內(nèi)部排序方法

　　首先，從時間性能上說：

　　1. 按平均的時間性能來分，有三類排序方法：

　　時間復雜度為O(nlogn)的方法有：快速排序、堆排序和歸并排序，其中以快速排序為最好;

　　時間復雜度為O(n2)的有：直接插入排序、起泡排序和簡單選擇排序，其中以直接插入為最好，特別是對那些對關(guān)鍵字近似有序的記錄序列尤為如此;

　　時間復雜度為O(n)的排序方法只有，基數(shù)排序。

　　2. 當待排記錄序列按關(guān)鍵字順序有序時，直接插入排序和起泡排序能達到O(n)的時間復雜度;而對于快速排序而言，這是最不好的情況，此時的時間性能蛻化為O(n2)，因此是應該盡量避免的情況。

　　3. 簡單選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關(guān)鍵字的分布而改變。

　　其次，從空間性能上說：

　　指的是排序過程中所需的輔助空間大小。

　　1. 所有的簡單排序方法(包括：直接插入、起泡和簡單選擇)和堆排序的空間復雜度為O(1);

　　2. 快速排序為O(logn)，為棧所需的輔助空間;

　　3. 歸并排序所需輔助空間最多，其空間復雜度為O(n);

　　4. 鏈式基數(shù)排序需附設(shè)隊列首尾指針，則空間復雜度為O(rd)。

　　再次，從排序方法的穩(wěn)定性能上說：

　　穩(wěn)定的排序方法指的是，對于兩個關(guān)鍵字相等的記錄，它們在序列中的相對位置，在排序之前和經(jīng)過排序之后，沒有改變。當對多關(guān)鍵字的記錄序列進行LSD方法排序時，必須采用穩(wěn)定的排序方法。對于不穩(wěn)定的排序方法，只要能舉出一個實例說明即可。我們需要指出的是：快速排序和堆排序是不穩(wěn)定的排序方法。

　　　　　　　計算機軟考軟件設(shè)計師練習試題及答案解析匯總