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