首頁 考試吧論壇 Exam8視線 考試商城 網(wǎng)絡(luò)課程 模擬考試 考友錄 實(shí)用文檔 求職招聘 論文下載
2011中考 | 2011高考 | 2012考研 | 考研培訓(xùn) | 在職研 | 自學(xué)考試 | 成人高考 | 法律碩士 | MBA考試
MPA考試 | 中科院
四六級(jí) | 職稱英語 | 商務(wù)英語 | 公共英語 | 托福 | 雅思 | 專四專八 | 口譯筆譯 | 博思 | GRE GMAT
新概念英語 | 成人英語三級(jí) | 申碩英語 | 攻碩英語 | 職稱日語 | 日語學(xué)習(xí) | 法語 | 德語 | 韓語
計(jì)算機(jī)等級(jí)考試 | 軟件水平考試 | 職稱計(jì)算機(jī) | 微軟認(rèn)證 | 思科認(rèn)證 | Oracle認(rèn)證 | Linux認(rèn)證
華為認(rèn)證 | Java認(rèn)證
公務(wù)員 | 報(bào)關(guān)員 | 銀行從業(yè)資格 | 證券從業(yè)資格 | 期貨從業(yè)資格 | 司法考試 | 法律顧問 | 導(dǎo)游資格
報(bào)檢員 | 教師資格 | 社會(huì)工作者 | 外銷員 | 國(guó)際商務(wù)師 | 跟單員 | 單證員 | 物流師 | 價(jià)格鑒證師
人力資源 | 管理咨詢師考試 | 秘書資格 | 心理咨詢師考試 | 出版專業(yè)資格 | 廣告師職業(yè)水平
駕駛員 | 網(wǎng)絡(luò)編輯
衛(wèi)生資格 | 執(zhí)業(yè)醫(yī)師 | 執(zhí)業(yè)藥師 | 執(zhí)業(yè)護(hù)士
會(huì)計(jì)從業(yè)資格考試會(huì)計(jì)證) | 經(jīng)濟(jì)師 | 會(huì)計(jì)職稱 | 注冊(cè)會(huì)計(jì)師 | 審計(jì)師 | 注冊(cè)稅務(wù)師
注冊(cè)資產(chǎn)評(píng)估師 | 高級(jí)會(huì)計(jì)師 | ACCA | 統(tǒng)計(jì)師 | 精算師 | 理財(cái)規(guī)劃師 | 國(guó)際內(nèi)審師
一級(jí)建造師 | 二級(jí)建造師 | 造價(jià)工程師 | 造價(jià)員 | 咨詢工程師 | 監(jiān)理工程師 | 安全工程師
質(zhì)量工程師 | 物業(yè)管理師 | 招標(biāo)師 | 結(jié)構(gòu)工程師 | 建筑師 | 房地產(chǎn)估價(jià)師 | 土地估價(jià)師 | 巖土師
設(shè)備監(jiān)理師 | 房地產(chǎn)經(jīng)紀(jì)人 | 投資項(xiàng)目管理師 | 土地登記代理人 | 環(huán)境影響評(píng)價(jià)師 | 環(huán)保工程師
城市規(guī)劃師 | 公路監(jiān)理師 | 公路造價(jià)師 | 安全評(píng)價(jià)師 | 電氣工程師 | 注冊(cè)測(cè)繪師 | 注冊(cè)計(jì)量師
繽紛校園 | 實(shí)用文檔 | 英語學(xué)習(xí) | 作文大全 | 求職招聘 | 論文下載 | 訪談 | 游戲
您現(xiàn)在的位置: 考試吧(Exam8.com) > 軟件水平考試 > 復(fù)習(xí)資料 > 程序員資料 > 正文

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

考試吧提供了“2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理”,供考生參考。

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

  9、內(nèi)部排序

  考查你對(duì)書本上的各種排序算法及其思想以及其優(yōu)缺點(diǎn)和性能指標(biāo)(時(shí)間復(fù)雜度)能否了如指掌。

  排序方法分類有:插入、選擇、交換、歸并、計(jì)數(shù)等五種排序方法。

  (1)插入排序中又可分為:直接插入、折半插入、2路插入(?)、希爾排序。這幾種插入排序算法的最根本的不同點(diǎn),說到底就是根據(jù)什么規(guī)則尋找新元素的插入點(diǎn)。直接插入是依次尋找,折半插入是折半尋找,希爾排序,是通過控制每次參與排序的數(shù)的總范圍“由小到大”的增量來實(shí)現(xiàn)排序效率提高的目的。

  (2)交換排序,又稱冒泡排序,在交換排序的基礎(chǔ)上改進(jìn)又可以得到快速排序?焖倥判虻乃枷,一語以敝之:用中間數(shù)將待排數(shù)據(jù)組一分為二。

  (3)選擇排序可以分為:簡(jiǎn)單選擇、樹選擇、堆排序。選擇排序相對(duì)于前面幾種排序算法來說,難度大一點(diǎn)。這三種方法的不同點(diǎn)是,根據(jù)什么規(guī)則選取最小的數(shù)。

  簡(jiǎn)單選擇,是通過簡(jiǎn)單的數(shù)組遍歷方案確定最小數(shù);

  樹選擇,是通過“錦標(biāo)賽”類似的思想,讓兩數(shù)相比,不斷淘汰較大(小)者,最終選出最小(大)數(shù);

  而堆排序,是利用堆這種數(shù)據(jù)結(jié)構(gòu)的性質(zhì),通過堆元素的刪除、調(diào)整等一系列操作將最小數(shù)選出放在堆頂。堆排序中的堆建立、堆調(diào)整是重要考點(diǎn)。

  (4)歸并排序,是通過“歸并”這種操作完成排序的目的,既然是歸并就必須是兩者以上的數(shù)據(jù)集合才可能實(shí)現(xiàn)歸并。所以,在歸并排序中,關(guān)注最多的就是2路歸并。算法思想比較簡(jiǎn)單,有一點(diǎn),要銘記在心:歸并排序是穩(wěn)定排序。

  (5)基數(shù)排序,是一種很特別的排序方法,也正是由于它的特殊,所以,基數(shù)排序就比較適合于一些特別的場(chǎng)合,比如撲克牌排序問題等;鶖(shù)排序,又分為兩種:多關(guān)鍵字的排序(撲克牌排序),鏈?zhǔn)脚判?整數(shù)排序)。基數(shù)排序的核心思想也是利用“基數(shù)空間”這個(gè)概念將問題規(guī)模規(guī)范、變小,并且,在排序的過程中,只要按照基排的思想,是不用進(jìn)行關(guān)鍵字比較的,這樣得出的最終序列就是一個(gè)有序序列。

  本章各種排序算法的思想以及偽代碼實(shí)現(xiàn),及其時(shí)間復(fù)雜度都是必須掌握的。

  //////////////////////////////////////////////穩(wěn)定性分析////////////////////////////////////////////////

  排序算法的穩(wěn)定性,通俗地講就是能保證排序前2個(gè)相等的數(shù)其在序列的前后位置順序和排序后它們兩個(gè)的前后位置順序相同。

  穩(wěn)定性的好處:若排序算法如果是穩(wěn)定的,那么從一個(gè)鍵上排序,然后再?gòu)牧硪粋(gè)鍵上排序,第一個(gè)鍵排序的結(jié)果可以為第二個(gè)鍵排序所用。基數(shù)排序就是這樣,先按低位排序,逐次按高位排序,低位相同的元素其順序再高位也相同時(shí)是不會(huì)改變的。另外,如果排序算法穩(wěn)定,對(duì)基于比較的排序算法而言,元素交換的次數(shù)可能會(huì)少一些(個(gè)人感覺,沒有證實(shí))。

  分析一下常見的排序算法的穩(wěn)定性,每個(gè)都給出簡(jiǎn)單的理由。

  (1) 冒泡排序

  冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較,交換也發(fā)生在這兩個(gè)元素之間。所以,如果兩個(gè)元素相等,我想你是不會(huì)再無聊地把他們倆交換一下的;如果兩個(gè)相等的元素沒有相鄰,那么即使通過前面的兩兩交換把兩個(gè)相鄰起來,這時(shí)候也不會(huì)交換,所以相同元素的前后順序并沒有改變,所以冒泡排序是一種穩(wěn)定排序算法。

  (2) 選擇排序

  選擇排序是給每個(gè)位置選擇當(dāng)前元素最小的,比如給第一個(gè)位置選擇最小的,在剩余元素里面給第二個(gè)元素選擇第二小的,依次類推,直到第n-1個(gè)元素,第n個(gè)元素不用選擇了,因?yàn)橹皇O滤粋(gè)最大的元素了。那么,在一趟選擇,如果當(dāng)前元素比一個(gè)元素小,而該小的元素又出現(xiàn)在一個(gè)和當(dāng)前元素相等的元素后面,那么交換后穩(wěn)定性就被破壞了。比較拗口,舉個(gè)例子,序列5 8 5 2 9,我們知道第一遍選擇第1個(gè)元素5會(huì)和2交換,那么原序列中2個(gè)5的相對(duì)前后順序就被破壞了,所以選擇排序不是一個(gè)穩(wěn)定的排序算法。

  (3) 插入排序

  插入排序是在一個(gè)已經(jīng)有序的小序列的基礎(chǔ)上,一次插入一個(gè)元素。當(dāng)然,剛開始這個(gè)有序的小序列只有1個(gè)元素,就是第一個(gè)元素。比較是從有序序列的末尾開始,也就是想要插入的元素和已經(jīng)有序的最大者開始比起,如果比它大則直接插入在其后面,否則一直往前找直到找到它該插入的位置。如果碰見一個(gè)和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后順序沒有改變,從原無序序列出去的順序就是排好序后的順序,所以插入排序是穩(wěn)定的。

  (4) 快速排序

  快速排序有兩個(gè)方向,左邊的i下標(biāo)一直往右走,當(dāng)a[i] <= a[center_index],其中center_index是中樞元素的數(shù)組下標(biāo),一般取為數(shù)組第0個(gè)元素。而右邊的j下標(biāo)一直往左走,當(dāng)a[j]> a[center_index]。如果i和j都走不動(dòng)了,i <= j, 交換a[i]和a[j],重復(fù)上面的過程,直到i>j。交換a[j]和a[center_index],完成一趟快速排序。在中樞元素和a[j]交換的時(shí)候,很有可能把前面的元素的穩(wěn)定性打亂,比如序列為 5 3 3 4 3 8 9 10 11,現(xiàn)在中樞元素5和3(第5個(gè)元素,下標(biāo)從1開始計(jì))交換就會(huì)把元素3的穩(wěn)定性打亂,所以快速排序是一個(gè)不穩(wěn)定的排序算法,不穩(wěn)定發(fā)生在中樞元素和 a[j] 交換的時(shí)刻。

  (5) 歸并排序

  歸并排序是把序列遞歸地分成短序列,遞歸出口是短序列只有1個(gè)元素(認(rèn)為直接有序)或者2個(gè)序列(1次比較和交換),然后把各個(gè)有序的段序列合并成一個(gè)有序的長(zhǎng)序列,不斷合并直到原序列全部排好序。可以發(fā)現(xiàn),在1個(gè)或2個(gè)元素時(shí),1個(gè)元素不會(huì)交換,2個(gè)元素如果大小相等也沒有人故意交換,這不會(huì)破壞穩(wěn)定性。那么,在短的有序序列合并的過程中,穩(wěn)定是是否受到破壞?沒有,合并過程中我們可以保證如果兩個(gè)當(dāng)前元素相等時(shí),我們把處在前面的序列的元素保存在結(jié)果序列的前面,這樣就保證了穩(wěn)定性。所以,歸并排序也是穩(wěn)定的排序算法。

  (6) 基數(shù)排序

  基數(shù)排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次類推,直到最高位。有時(shí)候有些屬性是有優(yōu)先級(jí)順序的,先按低優(yōu)先級(jí)排序,再按高優(yōu)先級(jí)排序,最后的次序就是高優(yōu)先級(jí)高的在前,高優(yōu)先級(jí)相同的低優(yōu)先級(jí)高的在前;鶖(shù)排序基于分別排序,分別收集,所以其是穩(wěn)定的排序算法。

  (7) 希爾排序(shell)

  希爾排序是按照不同步長(zhǎng)對(duì)元素進(jìn)行插入排序,當(dāng)剛開始元素很無序的時(shí)候,步長(zhǎng)最大,所以插入排序的元素個(gè)數(shù)很少,速度很快;當(dāng)元素基本有序了,步長(zhǎng)很小,插入排序?qū)τ谟行虻男蛄行屎芨。所以,希爾排序的時(shí)間復(fù)雜度會(huì)比o(n^2)好一些。由于多次插入排序,我們知道一次插入排序是穩(wěn)定的,不會(huì)改變相同元素的相對(duì)順序,但在不同的插入排序過程中,相同的元素可能在各自的插入排序中移動(dòng),最后其穩(wěn)定性就會(huì)被打亂,所以shell排序是不穩(wěn)定的。

  (8) 堆排序

  我們知道堆的結(jié)構(gòu)是節(jié)點(diǎn)i的孩子為2*i和2*i+1節(jié)點(diǎn),大頂堆要求父節(jié)點(diǎn)大于等于其2個(gè)子節(jié)點(diǎn),小頂堆要求父節(jié)點(diǎn)小于等于其2個(gè)子節(jié)點(diǎn)。在一個(gè)長(zhǎng)為n 的序列,堆排序的過程是從第n/2開始和其子節(jié)點(diǎn)共3個(gè)值選擇最大(大頂堆)或者最小(小頂堆),這3個(gè)元素之間的選擇當(dāng)然不會(huì)破壞穩(wěn)定性。但當(dāng)為n /2-1, n/2-2, ...1這些個(gè)父節(jié)點(diǎn)選擇元素時(shí),就會(huì)破壞穩(wěn)定性。有可能第n/2個(gè)父節(jié)點(diǎn)交換把后面一個(gè)元素交換過去了,而第n/2-1個(gè)父節(jié)點(diǎn)把后面一個(gè)相同的元素沒有交換,那么這2個(gè)相同的元素之間的穩(wěn)定性就被破壞了。所以,堆排序不是穩(wěn)定的排序算法。

1 2 3 4 5 6 7 8 9 10 11 下一頁
  相關(guān)推薦:

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

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

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

文章搜索
軟件水平考試欄目導(dǎo)航
版權(quán)聲明:如果軟件水平考試網(wǎng)所轉(zhuǎn)載內(nèi)容不慎侵犯了您的權(quán)益,請(qǐng)與我們聯(lián)系800@exam8.com,我們將會(huì)及時(shí)處理。如轉(zhuǎn)載本軟件水平考試網(wǎng)內(nèi)容,請(qǐng)注明出處。