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

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

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

　　首先，從時間性能上說：

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

　　時間復(fù)雜度為O(nlogn)的方法有：快速排序、堆排序和歸并排序，其中以快速排序?yàn)樽詈?

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

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

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

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

　　其次，從空間性能上說：

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

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

　　2. 快速排序?yàn)镺(logn)，為棧所需的輔助空間;

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

　　4. 鏈?zhǔn)交鶖?shù)排序需附設(shè)隊(duì)列首尾指針，則空間復(fù)雜度為O(rd)。

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

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

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