2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理(5)

　　<|>對(duì)排序算法的總結(jié)

　　按平均時(shí)間將排序分為四類：

　　(1)平方階(O(n2))排序

　　一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序;

　　(2)線性對(duì)數(shù)階(O(nlgn))排序

　　如快速、堆和歸并排序;

　　(3)O(n1+￡)階排序

　　￡是介于0和1之間的常數(shù)，即0<￡<1，如希爾排序;

　　(4)線性階(O(n))排序

　　如桶、箱和基數(shù)排序。

　　各種排序方法比較

　　簡單排序中直接插入最好，快速排序最快，當(dāng)文件為正序時(shí)，直接插入和冒泡均最佳。

　　影響排序效果的因素

　　因?yàn)椴煌�的排序方法適應(yīng)不同的應(yīng)用環(huán)境和要求，所以選擇合適的排序方法應(yīng)綜合考慮下列因素：

　�、俅�排序的記錄數(shù)目n;

　�、谟涗浀拇笮�(規(guī)模);

　�、坳P(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài);

　�、軐�(duì)穩(wěn)定性的要求;

　　⑤語言工具的條件;

　　⑥存儲(chǔ)結(jié)構(gòu);

　　⑦時(shí)間和輔助空間復(fù)雜度等。

　　不同條件下，排序方法的選擇

　　(1)若n較小(如n≤50)，可采用直接插入或直接選擇排序。

　　當(dāng)記錄規(guī)模較小時(shí)，直接插入排序較好;否則因?yàn)橹苯舆x擇移動(dòng)的記錄數(shù)少于直接插人，應(yīng)選直接選擇排序?yàn)橐恕?/P>

　　(2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插人、冒泡或隨機(jī)的快速排序?yàn)橐?

　　(3)若n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。

　　快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短;

　　堆排序所需的輔助空間少于快速排序，并且不會(huì)出現(xiàn)快速排序可能出現(xiàn)的最壞情況。這兩種排序都是不穩(wěn)定的。

　　若要求排序穩(wěn)定，則可選用歸并排序。但本章介紹的從單個(gè)記錄起進(jìn)行兩兩歸并的 排序算法并不值得提倡，通�？梢詫⑺�和直接插入排序結(jié)合在一起使用。先利用直接插入排序求得較長的有序子文件，然后再兩兩歸并之。因?yàn)橹苯硬迦肱判蚴欠�(wěn)定的，所以改進(jìn)后的歸并排序仍是穩(wěn)定的。

　　軟考程序員考試歷年真題重點(diǎn)題總結(jié)及答案

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)