（2）插入類排序法
插入類排序法主要有簡單插入排序法和希爾排序法。
簡單插入排序法，是指將無序序列中的各元素依次插入到已經(jīng)有序的線性表中。在這種排序方法中，每一次比較后最多移掉一個(gè)逆序，因此，這種排序方法的效率與冒泡排序法相同。在最壞情況下，簡單插入排序需要n(n–1)/2次比較。
希爾排序法對簡單插入排序做了較大的改進(jìn)。它是將整個(gè)無序序列分割成若干小的子序列分別進(jìn)行插入排序。希爾排序的效率與所選取的增量序列有關(guān)。在最壞情況下，希爾排序所需要的比較次數(shù)為O(n1.5)。
（3）選擇類排序
選擇類排序主要有簡單選擇類排序法和堆排序法。
簡單選擇排序法的基本思想是：掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最前面（這是它應(yīng)有的位置）；然后對剩下的子表采用同樣的方法，直到子表空為止。對于長度為n的線性表，在最壞情況下需要比較n(n–1)/2次。
堆排序法也屬于選擇類排序法。具有n個(gè)元素的序列（h1, h2, …, hn），當(dāng)且僅當(dāng)滿足條件：
   或  
(i=1, 2, …, n/2）時(shí)稱之為堆?？梢?，堆頂元素（即第一個(gè)元素）必為最大項(xiàng)。
堆排序的方法對于規(guī)模較小的線性表并不適合，但對于較大規(guī)模的線性表來說是很有效的。在最壞情況下，堆排序需要比較的次數(shù)為O(nlog2n)。
程序設(shè)計(jì)基礎(chǔ)
1．程序設(shè)計(jì)方法與風(fēng)格
除了好的程序設(shè)計(jì)方法和技術(shù)外，程序設(shè)計(jì)風(fēng)格也是很重要的內(nèi)容。程序設(shè)計(jì)風(fēng)格是指編寫程序時(shí)所表現(xiàn)出的特點(diǎn)、習(xí)慣和邏輯思路。要形成良好的程序設(shè)計(jì)風(fēng)格，主要應(yīng)注重和考慮下述一些因素。
（1）源程序文檔化
符號名的命名：符號名的命名應(yīng)具有一定的實(shí)際含義，以便于對程序功能的理解。
程序注釋：注釋一般分為序言性注釋和功能性注釋。序言性注釋通常位于每個(gè)程序的開頭部分，它給出程序的整體說明；而功能性注釋的位置一般嵌在源程序體中，主要描述其后的語句或程序做什么。
視覺組織：可以在程序中利用空格、空行、縮進(jìn)等技巧使程序?qū)哟吻逦?br /> （2）數(shù)據(jù)說明的方法
主要包括數(shù)據(jù)說明的次序規(guī)范化、說明語句中變量安排有序化和使用注釋來說明復(fù)雜數(shù)據(jù)結(jié)構(gòu)等。
（3）語句的結(jié)構(gòu)
語句構(gòu)造應(yīng)該簡單直接，不應(yīng)該為提高效率而把語句復(fù)雜化。
（4）輸入和輸出
輸入和輸出方式和格式應(yīng)盡可能方便用戶的使用。
2．結(jié)構(gòu)化程序設(shè)計(jì)
結(jié)構(gòu)化程序設(shè)計(jì)的主要原則、設(shè)計(jì)要素應(yīng)是重點(diǎn)掌握的內(nèi)容。
由于軟件危機(jī)的出現(xiàn)，人們開始研究程序設(shè)計(jì)方法，其中最受關(guān)注的是結(jié)構(gòu)化程序設(shè)計(jì)方法。結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則可以概括為自頂向下、逐步求精、模塊化、限制使用goto語句。
在結(jié)構(gòu)化程序設(shè)計(jì)的具體實(shí)施中，要注意把握如下要素。
（1）使用程序設(shè)計(jì)語言中的順序、選擇、循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯。
（2）使用的控制結(jié)構(gòu)只準(zhǔn)許有一個(gè)入口和一個(gè)出口。
（3）程序語句組成容易識別的塊，每塊只有一個(gè)入口和一個(gè)出口。
（4）復(fù)雜結(jié)構(gòu)應(yīng)該用嵌套的基本控制結(jié)構(gòu)進(jìn)行組合嵌套來實(shí)現(xiàn)。
（5）語言中所沒有的控制結(jié)構(gòu)，應(yīng)該采用前后一致的方法來模擬。
（6）嚴(yán)格控制goto語句的使用。
3．面向?qū)ο蟮某绦蛟O(shè)計(jì)及其重要概念
面向?qū)ο蟮某绦蛟O(shè)計(jì)方法及其有關(guān)概念是重點(diǎn)掌握的內(nèi)容，也是考試的重點(diǎn)。
面向?qū)ο蟮某绦蚍椒ㄖ鲝垙目陀^世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，提倡用人類在現(xiàn)實(shí)生活中常用的思維方法來認(rèn)識、理解和描述客觀事物，強(qiáng)調(diào)最終建立的系統(tǒng)能夠映射問題域。它具有與人類習(xí)慣的思維方法一致、穩(wěn)定性好、可重用性好、易于開發(fā)大型軟件產(chǎn)品、可維護(hù)性好等優(yōu)點(diǎn)。
在面向?qū)ο蟮某绦蚍椒ㄖ校腥缦轮匾母拍睢?br /> （1）對象
用來表示客觀世界中的任何實(shí)體，即應(yīng)用領(lǐng)域中有意義的、與所要解決的問題有關(guān)系的任何事物都可以作為對象。它既可以是具體的物理實(shí)體的抽象，也可以是人為的概念，或者是任何有明確邊界和意義的東西。面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中涉及的對象是系統(tǒng)中用來描述客觀事物的一個(gè)實(shí)體，是構(gòu)成系統(tǒng)的一個(gè)基本單位，它由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。
屬性即對象所包含的信息，它在設(shè)計(jì)對象時(shí)確定，一般只能通過執(zhí)行對象的操作來改變。
操作描述了對象執(zhí)行的功能，若通過消息傳遞，還可以為其他對象使用。
（2）類和實(shí)例
將屬性、操作相似的對象歸為類，即是具有共同屬性、共同方法的對象的集合。因此，類是對象的抽象，它描述了屬于該對象類型的所有對象的性質(zhì)，而一個(gè)對象則是其對應(yīng)類的一個(gè)實(shí)例。
（3）消息
面向?qū)ο蟮氖澜缡峭ㄟ^對象與對象間彼此的相互合作來推動的，對象間的這種相互合作需要一個(gè)機(jī)制協(xié)助進(jìn)行，這樣的機(jī)制稱為“消息”。消息是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息，它請示對象執(zhí)行某一處理或回答某一要求的信息，它統(tǒng)一了數(shù)據(jù)流和控制流。一個(gè)消息由接收消息的對象的名稱、消息標(biāo)識符（即消息名）、零個(gè)或多個(gè)參數(shù)組成。
（4）繼承
繼承是面向?qū)ο蟮姆椒ǖ囊粋€(gè)主要特征。繼承是使用已有的類定義作為基礎(chǔ)建立新類的定義技術(shù)。已有的類可當(dāng)做基類來引用，則新類相應(yīng)地可當(dāng)做派生類來引用。一個(gè)類的上層可以有父類，下層可以有子類。一個(gè)類直接繼承其父類的描述（數(shù)據(jù)和操作）或特性，子類自動地共享基類中定義的數(shù)據(jù)和方法。
（5）多態(tài)性
對象根據(jù)所接受的消息而做出動作，同樣的消息被不同的對象接受時(shí)可導(dǎo)致完全不同的行動，該現(xiàn)象稱為多態(tài)性。