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

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

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

　　首先，從時(shí)間性能上說(shuō)：

　　1. 按平均的時(shí)間性能來(lái)分，有三類排序方法：

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

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

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

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

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

　　其次，從空間性能上說(shuō)：

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

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

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

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

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

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

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

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