C++程序設(shè)計指導(dǎo)書

1、淮陰工學(xué)院C+程序設(shè)計指導(dǎo)書張亞紅 于長輝 殷路 于永濤 許超俊淮陰工學(xué)院·計算機與軟件工程學(xué)院二一六年五月前言“C+程序設(shè)計”是計算機類專業(yè)的一門專業(yè)核心基礎(chǔ)課程，涉及知識點多，教、學(xué)難度非常大，往往費了大量時間而達(dá)不到預(yù)期效果。俗語說：學(xué)習(xí)的最好方法是實踐。本課程設(shè)計正是基于此目的，力求為學(xué)生提供一個理論聯(lián)系實際的機會，通過布置一定難度的課題，要求學(xué)生獨立完成。通過實踐，建立課程設(shè)計的整體思想，鍛煉編寫程序、調(diào)試程序的能力，學(xué)習(xí)文檔編寫規(guī)范，培養(yǎng)獨立學(xué)習(xí)、吸取他人經(jīng)驗、探索前沿知識的習(xí)慣，樹立團(tuán)隊協(xié)作精神。指導(dǎo)書中的綜合選題可以分成幾個小項目供學(xué)生分工合作，其中給出的代碼已經(jīng)有意

2、識地予以變化或刪減，在一些關(guān)鍵之處有意設(shè)置了一點錯誤，直接復(fù)制一般難以調(diào)試通過，或難以達(dá)到預(yù)期的目的。同學(xué)們應(yīng)該加以分析，補充完整，并盡可能地增加功能。同學(xué)們應(yīng)注意小組成員之間共同研究技術(shù)難題，培養(yǎng)團(tuán)隊協(xié)作精神。書中給出的實例概念清楚，體系完整，內(nèi)容豐富，采用循序漸進(jìn)的方式，提高學(xué)生實際動手能力，完成“知識+實踐=技能”的整個學(xué)習(xí)過程。在設(shè)計時，同學(xué)們可以采用結(jié)構(gòu)化程序設(shè)計方法、面向?qū)ο蟪绦蛟O(shè)計方法同時使用。III目錄前 言I選題1Huffman編碼1一、二元Huffman碼1二、m元Huffman碼2選題2幻方5一、奇數(shù)階幻方的制作5二、偶數(shù)階幻方的制作7三、設(shè)計要求10選題3矩陣操作（動態(tài)

3、數(shù)組）11一、矩陣翻轉(zhuǎn)11二、矩陣卷動11三、矩陣旋轉(zhuǎn)12四、設(shè)計要求13選題4漢諾塔問題14一、基本涵義14二、常規(guī)解法14三、設(shè)計要求15選題5八皇后問題16一、基本涵義16二、設(shè)計要求16選題6學(xué)生成績管理18一、設(shè)計要求18選題7數(shù)據(jù)排序19一、基本概念19二、插入排序19三、交換排序21四、選擇排序23五、歸并排序25六、設(shè)計要求26選題8數(shù)據(jù)查找28一、基本概念28二、順序查找28三、二分查找30四、索引查找32五、散列查找35選題9學(xué)生運動會成績管理46一、問題描述46二、設(shè)計要求46選題10算術(shù)表達(dá)式求值47一、基本概念47二、棧的存儲、運算及STL47三、表達(dá)式求值50四、設(shè)

4、計要求53選題11圖書管理54一、設(shè)計要求54選題12集合的運算55一、問題描述55二、設(shè)計要求55三、設(shè)計要點55選題13單位人事檔案管理55一、設(shè)計要求55附錄AC+程序設(shè)計課程設(shè)計操作規(guī)程57一、課程設(shè)計的目的57二、實踐環(huán)境與教學(xué)要求57三、實施原則、方案與步驟57四、課程設(shè)計報告要求58五、成績評定規(guī)則59六、說明59選題1 Huffman編碼一、二元Huffman碼在通信領(lǐng)域，信息編碼是一種最基本的理論基礎(chǔ)與技術(shù)手段，可以針對文字、聲音、圖像、視頻、模型等，分為信源編碼、信道編碼。編碼的方法有很多。1952年，一位外國人提出了一種逐個符號的編碼方法，姑且稱為H編碼方法。其基本思想如

5、下：設(shè)有n個信號u1,u2,un，其概率分布依次為p（u1），p（u2），p（un），稱為信號值，且滿足下式：p（u1）+p（u2）+p（un）=1簡記為：H碼的編碼步驟可以簡述為：（1） 首先將n個信號按值的大小排列。（2） 將最小的兩個信號合并成一個新的信號，新信號的值為該兩信號值的和，從而將原n個信號縮減為n1個信號。（3） 把縮減后的信號仍按值遞減排列，然后再將其中最小的兩個信號合并成一個新信號，這樣又縮減為n2個信號。（4） 依此類推，直至只剩下個信號為止。（5） 將每次合并的兩個信號分別用“0”和“1”兩個符號表示。（6） 從最后一級開始，向前返回，就得出各信號所對應(yīng)的符號序列，即

6、為各信號對應(yīng)的碼字。例如：已知其對應(yīng)的H碼如圖所示：再如：對有兩種編碼過程：方法(a)的具體原則是，把合并后的信號總是放在其他相同值的信號之上（或之左），方法（b）則是把合并后的信號值放在其他相同值的信號之下（或之右）。通過分析，方法（a）優(yōu)于方法（b），方法（a）的方差比方法（b）的方差要小許多。二、m元Huffman碼上面討論的編碼方法可稱為二元編碼，其思想可推廣到m元編碼。不同的只是每次把值最小的m個信號合并成一個新的信號，并分別用0，1，m1等m個符號來表示。對于m元編碼，信號個數(shù)n必須滿足下式：n（m1）Qm式中： n信號個數(shù)m碼元數(shù)Q縮減次數(shù)對于二元碼，總能找到一個Q，滿足上式。但

7、對于m元碼，當(dāng)n為任意正整數(shù)時，不一定能找到一個Q滿足上式，此時，可以人為地增加一些值為零的信號以滿足上式。然后取值最小的m個信號合并成一個新信號，并把這些信號的值相加作為該新信號的值，重新由大到小排序，再取最小的m個信號合并，如此下去。m元的H碼編碼步驟如下：（1） 驗證所給n是否滿足上式，若不滿足，可以人為地增加一些值為零的信號，以使最后一步有m個信號；（2） 取最小的m個符號合并成一個新信號，并分別用0，1，m給各分支賦值，把這些信號的值相加作為該新信號的值；（3） 將新信號和剩下信號重新排序，重復(fù)（2）。（4） 從最后一級開始，向前返回，就得出各信號所對應(yīng)的符號序列，即為各信號對應(yīng)的碼

8、字。后來新加的值為零的信號，雖也賦予碼字，但實際上是冗余碼字，并未用上，但這樣編成的碼，仍是最佳的，也就是平均碼長最短，如果等值信號排隊時注意到順序，則碼長的方差也是最小的。例如：已知其三元編碼如下圖所示：四元編碼如下圖：要求：編寫代碼，設(shè)有50個信號，用二種方法，運行程序后，顯現(xiàn)下面的參考界面：H碼編碼=1方法A2方法B請選擇（1或2 ，0：退出）：選擇一個菜單后，要求輸入碼元數(shù)N，N取值范圍為216。輸入后，顯示編碼結(jié)果。選題2 幻方所謂幻方，就是一個n行n列的正方形，共有n2個格子，將1、2、3、n2這些數(shù)字放到這些格子里，使其每行的和、每列的和及兩條對角線的和都是一個相同的數(shù)S，S稱為

9、幻和。當(dāng)n為奇數(shù)時，稱為奇數(shù)階幻方，當(dāng)n為偶數(shù)時，稱為偶階幻方。當(dāng)n可被4整除時，稱方為雙偶幻方。當(dāng)n不可被4整除時，稱為單偶幻方。多少年來，許多數(shù)學(xué)家都在研究這個古老而有趣的問題，試圖找出一般的解法，但一般都是針對當(dāng)n是奇數(shù)和n是4的倍數(shù)的情況。當(dāng)n是奇數(shù)時的算法：首先，將1放在第一行中間一個格子里。其次，依次將后一個數(shù)放到前一個數(shù)的右上格，如：將2放到1的右上格。將放到的右上格等等?？赡艹霈F(xiàn)下面的情況。若右上格從上面超出，則將后一數(shù)放到與右上格同列的最后一行。若右上格從右面超出，則將后一數(shù)放到與右上格同行的最后一列。若右上格既從右面超出又從上面超出，則將后一數(shù)放到前一數(shù)的下面。若右上格已被

10、數(shù)字填充，則將后一數(shù)放到前一數(shù)的下面依以上法則，你可以很快的寫出奇數(shù)階幻方！當(dāng)然，這中寫法只是其中一個答案，而不是唯一答案。一、奇數(shù)階幻方的制作1連續(xù)擺數(shù)法例：一個5×5 格子，由最上面一行中間一格開始，依次填1，2，3等等。下一個格子填在左上位置。但是要注意兩點：Ø 出了幻方的范圍，右邊接到左邊，下邊接到上邊。Ø 某一格右上已經(jīng)有了數(shù)字，改填在這個格子的下面一格，然后延續(xù)前面的方法。17241815235714164613202210121921311182529也不一定按照斜上方寫字，可以走馬步，或其他方法。下面用的是馬步，得到的是泛對角幻方。81711524

11、112591821931221102262041351423716哪些“步子”是可行的，是需要注意的一個問題。2階梯法例：以5階為例。第一步：畫一個9×9的方格。如下斜著填數(shù)字。注意中間的5×5格子才是要作的幻方的位置，已經(jīng)涂成了黃色。 54103915281420171319256121824111723162221第二步：黃色范圍以外的數(shù)字，平移到黃色格子中沒有數(shù)字的位置。31692215208211427251311924125186114171023去掉外圍的格子，就得到所要作的幻方。31692215208211427251311924125186114171023

12、 二、偶數(shù)階幻方的制作偶數(shù)階幻方的制作比較復(fù)雜，下面介紹幾個方法。1對稱法，適用于雙偶數(shù)階幻方例：以8階幻方為例。第一步：在左上4×4格子中，取一半的格子，要求每行每列都取到2個。如下圖黃色格子所示。第二步：按照左右對稱、上下對稱、中心對稱的方法把這8個格子擴充為32個格子。第三步：從左上角開始，從左到右從上到下，從1開始填數(shù)。不過只填沒有選中的格子（即沒有涂黃色的格子）24579111416171922242628293134363739414346484951545658606163第四步：從右下角開始從右到左從下到上在選中的格子里填進(jìn)剛才沒有填的數(shù)字。64262455

13、975795511535214501617471945442242244026382829353133323430363727392541234321204618484915511312541056858660613631制作成功。這個方法可以產(chǎn)生不同的雙偶數(shù)階幻方。思考：能否算出這個方法可以產(chǎn)生多少個8階幻方？2斯特雷奇法，適用于單偶數(shù)幻方例：設(shè)階數(shù)n=2(2m+1)=6，m=1。第一步：把方陣分為4個小方陣，位置依次為A左上，B右下，C右上，D左下。 用連續(xù)擺數(shù)法，把1a2放在A中成第一個幻方；把a212a2放在B中成第二個幻方。把2a213a2放在C中成第三個幻方。把3a214a2放在D

14、中成第四個幻方。 816261924357212325492222720352833171015303234121416313629131822第二步：在A的各行左起取m個方格，但中間一行從第二格開始。與D中相應(yīng)位置對換。816261924357212325492222720352833171015303234121416313629131822第三步：在C的各行右起取m1個方格，與B中相應(yīng)位置對換。此例m-1=0，無需交換。3516261924332721232531922227208283317101530534121416436291318223LUX方法 這是劍橋大學(xué)康韋教授發(fā)明的方法

15、例：設(shè)階數(shù)n=2(2m+1)=10，m=2。第一步：任取一個2m+1 階幻方，例如5階幻方。如下。12316421151471811241713922081912653102225第二步：在上面的m+1行 (此處為3行）的每個格子里填入一個字母L；接下去一行填字母U，余下m-1 行填字母X。最后把中間的一個L 與它下面的一個U 交換一下。1L23L16L4L21L15L14L7L18L11L24L17L13U9L2L20U8U19L12U6U5X3X10X22X25X第三步：作一個10×10方格，設(shè)想為每2×2為一個單位,每個單位相應(yīng)于上面一個格子。對應(yīng)于5階幻方中數(shù)字1的

16、單位填1，2，3，4。對應(yīng)于5階幻方中數(shù)字2的填5，6，7，8。等等。但是標(biāo)有字母L 的按照“右上左下右下左上”次序；標(biāo)有字母U 的按照“左上左下右下右上”次序；標(biāo)有字母X 的按照“左上右下左下右上”次序。419289646116138481239091626314158283605756532825726944415859545526277071424396936865495236338594956667505134356777802932767345482124787930317475464722231720912374085889710019181110393887869998當(dāng)然，這個

17、方法也產(chǎn)生很多幻方，并不唯一。三、設(shè)計要求編寫代碼，實現(xiàn)奇、偶數(shù)幻方的制作。運行程序后，出現(xiàn)下面的參考界面：幻方制作=1奇數(shù)階幻方2偶數(shù)階幻方請選擇（1或2，0：退出）：選擇一個菜單后，要求輸入幻方的階數(shù)n。n的取值范圍為310。輸入n后，首先判斷是否存在對應(yīng)階的幻方，如果存在，則顯示幻方制作效果。選題3 矩陣操作（動態(tài)數(shù)組）一、矩陣翻轉(zhuǎn)沿某中心軸翻轉(zhuǎn)，或垂直，或水平翻轉(zhuǎn)。翻轉(zhuǎn)的實質(zhì)是，矩陣的每行（或每列）元素進(jìn)行倒序排放。二、矩陣卷動可以左右、上下卷動。如下圖：矩陣卷動涉及二個問題：（1）卷動方向，或左右卷動，或上下卷動。（2）卷動幅度T，如上下卷動行數(shù)，左右卷動列數(shù)。卷動的實質(zhì)是將某行或某

18、列元素循環(huán)移位。上下卷動時，是將每列元素循環(huán)移位，左右卷動時是將每行元素循環(huán)移位，卷動方向決定是左移還是右移。一維數(shù)組的循環(huán)移位問題：如，已知int temp10，將其循環(huán)右移一位。顯然， 移位后，temp8 temp0 依次存入temp9 temp1 而原來的temp9 則返回數(shù)組起始部位，存入temp0 。 那么，循環(huán)右移W位呢？循環(huán)左移W位呢？了解了一維數(shù)組循環(huán)移位問題后，顯然，矩陣卷動無非是多個一維數(shù)組循環(huán)移位，只要在外層加個大循環(huán)就解決了。三、矩陣旋轉(zhuǎn)矩陣旋轉(zhuǎn)（繞中心點）涉及二個方面：（1）旋轉(zhuǎn)方向，順時針還是逆時針。（2）旋轉(zhuǎn)角度，如90o、180o、270o、360o等。分析：（

19、1）考慮旋轉(zhuǎn)方向、角度（2）此處僅考慮方陣情況，即矩陣行、列數(shù)相同。（3）考慮是奇次方陣還是偶次方陣。（4）旋轉(zhuǎn)時，實質(zhì)是數(shù)組元素的重新組合，對應(yīng)交換元素值。（5）設(shè)方陣有K圈，每圈操作過程相似。因此，問題的關(guān)鍵是某圈元素的旋轉(zhuǎn)、交換。如下圖。考慮幾種特殊情況，如90°，180 ° ，270 ° ，360 ° 等。（1）其它角度都是90°的整數(shù)倍。因此，設(shè)計時僅需要考慮90°情況，其它情況只需重復(fù)操作若干次即可。以順時針旋轉(zhuǎn)為例，如需旋轉(zhuǎn)180 ° ，只需將旋轉(zhuǎn)90 °操作連續(xù)執(zhí)行兩次即能實現(xiàn)。（2）逆時針旋轉(zhuǎn)可以

20、看作為“過度”旋轉(zhuǎn)，如逆時針90°，可認(rèn)為是順時針旋轉(zhuǎn)270 °。當(dāng)然，也可設(shè)計新的交換規(guī)則。四、設(shè)計要求編寫代碼，實現(xiàn)矩陣的翻轉(zhuǎn)、卷動和旋轉(zhuǎn)。運行程序后，隨機生成一個元素為三位正整數(shù)的5×5矩陣，并顯現(xiàn)下面的參考界面：矩陣操作=1矩陣翻轉(zhuǎn)2矩陣卷動3矩陣旋轉(zhuǎn)請選擇（1、2或3，0：退出）：選擇一個菜單后，要求輸入操作的方向、行數(shù)或列數(shù)或角度，輸入后，顯示操作結(jié)果。60選題4 漢諾塔問題一、基本涵義在印度，有這么一個古老的傳說：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時候，在其中一根針上從下到上地穿好了由大

21、到小的片金片，這就是所謂的漢諾塔（如下圖）。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必在大片上面。當(dāng)所有的金片都從梵天穿好的那根針上移到另外一概針上時，世界就將在一聲霹靂中消滅，梵塔、廟宇和眾生都將同歸于盡。故漢諾塔問題又被稱為“世界末日問題?！边@是一個典型問題。由于問題中給出的圓盤移動條件是：一次僅能移動一個盤，且不允許大盤放在小盤的上面，這樣64個盤子的移動次數(shù)為：18,446,744,073,709,511,615（次）這是個天文數(shù)字，若每一微秒可以計算（并不輸出）一次移動，那麼也需要幾乎一百萬年。我們僅能找出問題的解決方法并解決較小值

22、時的漢諾塔，但目前計算機的速度還不能解決曾的漢諾塔。二、常規(guī)解法按照上面的方法分析問題，找到移動圓盤的的遞歸算法：設(shè)要解決的的漢諾塔共有個圓盤，對桿上的全部個圓盤從小到大順序編號，最小的圓盤為號，次之為號，依次類推，則最下面的圓盤的編號為。第一步：先將問題簡化。假設(shè)桿上只有一個圓盤，即漢諾塔只有一層，則只要將號盤從桿上移到桿上即可。第二步：對於一個有（）個圓盤的漢諾塔，將個圓盤分成兩部分：上面的個圓盤和最下面的號圓盤。第三步：將“上面的個圓盤”看成一個整體，為了解決個圓盤的漢諾塔，可以按下面圖示的方式逕行操作：（1）將桿上面的個盤子，借助桿，移到桿上；（2）將桿上剩余的號盤子移到桿上；（3）將

23、桿上的個盤子，借助桿，移到桿上。 整理上述結(jié)果，把第一步中化簡問題的條件作為遞歸結(jié)束條件，將第三步分析得到的算法作為遞歸算法，可以寫出如下完整得遞歸算法描述。三、設(shè)計要求編寫代碼，用兩種方法解決盤子的移動。運行程序后，顯現(xiàn)下面的參考界面：漢諾塔=1遞歸解法2非遞歸解法請選擇（1或2，0：退出）：選擇一個菜單后，要求輸入盤片數(shù)目，輸入后，顯示移動過程及結(jié)果。選題5 八皇后問題一、基本涵義八皇后問題是一個古老而著名的問題。該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8X8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。高斯認(rèn)為

24、有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來有人用圖論的方法解出92種結(jié)果。顯然問題的鍵在于如何判定某個皇后所在的行、列、斜線上是否有別的皇后；可以從矩陣的特點上找到規(guī)律，如果在同一行，則行號相同；如果在同一列上，則列號相同；如果同在“”斜線上的行列值之和相同；如果同在“”斜線上的行列值之差相同；如果斜線不分方向，則同一斜線上兩皇后的行號之差的絕對值與列號之差的絕對值相同。從下圖可以驗證上面的說法： 對于一組布局我們可以用一個一維數(shù)組來表示：X:ARRAY 1.8 OF INTEGER;XI的下標(biāo)I表示第I個皇后在棋盤的第I行，XI的內(nèi)容表示在第I行的第XI列

25、，例如：X3=5就表示第3個皇后在第3行的第5列。在這種方式下，要表示兩個皇后A和B不在同一列或斜線上的條件可以描述為：XA<>XB AND ABS(A-B)<>ABS(XA-XB)A和B分別表示兩個皇后的行號。二、設(shè)計要求編寫代碼，用至少三種方法解決八皇后問題。運行程序后，顯現(xiàn)下面的參考界面：八皇后問題=1方法一2方法二3方法三請選擇（1、2或3，0：退出）：選擇一個菜單后，要求輸入棋盤的階層，即N。輸入后，顯示共有多少種布局方案，并顯示每一種方案的具體情況，如下圖：77: (0,2) (1,0) (2,6) (3,4) (4,7) (5,1) (6,3) (7,5)

26、78: (0,7) (1,1) (2,4) (3,2) (4,0) (5,6) (6,3) (7,5)選題6 學(xué)生成績管理一、設(shè)計要求由于同學(xué)們已經(jīng)學(xué)習(xí)了指針、鏈表、文件讀寫等基本知識，為了與后續(xù)課程，如數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫系統(tǒng)等有一個知識體系上的銜接，特設(shè)置一個信息管理類的課題成績管理系統(tǒng)，其它諸如人事管理、學(xué)籍管理、圖書管理、通訊錄管理等，結(jié)構(gòu)類似，僅管理對象有所不同。管理內(nèi)容包括：學(xué)號、姓名、班級、五門課成績。主要功能有：添加、修改、刪除、讀出、寫入、查找、排序、計算總分、平均分、分類匯總等。編寫代碼，運行程序后，顯現(xiàn)下面的參考界面：成績管理=1輸入學(xué)生成績2修改學(xué)生成績3刪除學(xué)生成績4計算

27、每位學(xué)生的總分5計算每位學(xué)生的平均分6按學(xué)號或姓名查詢學(xué)生成績7按班級查詢學(xué)生成績8成績排序9按班級統(tǒng)計學(xué)科總分、平均分等請選擇（19，0：退出）：選擇一個菜單后，顯示結(jié)果。選題7 數(shù)據(jù)排序一、基本概念排序是數(shù)據(jù)處理中經(jīng)常使用的一種重要運算。設(shè)文件由n個記錄R1，R2，Rn組成，如n個學(xué)生記錄，每個學(xué)生記錄包括學(xué)號、姓名、班級等。n個記錄對應(yīng)的關(guān)鍵字集合為K1，K2，Kn，如學(xué)生的學(xué)號。所謂排序就是將這n個記錄按關(guān)鍵字大小遞增或遞減重新排列。當(dāng)待排序記錄的關(guān)鍵字均不相同時，排序結(jié)果是惟一的，否則排序結(jié)果不唯一。如果文件中關(guān)鍵字相同的記錄經(jīng)過某種排序方法進(jìn)行排序之后，仍能保持它們在排序之前的相對

28、次序，則稱這種排序方法是穩(wěn)定的；否則，稱這種排序方法是不穩(wěn)定的。由于文件大小不同使排序過程中涉及的存儲器不同，可將排序分成內(nèi)部排序和外部排序兩類。整個排序過程都在內(nèi)存進(jìn)行的排序，稱為內(nèi)部排序；反之，若排序過程中要進(jìn)行數(shù)據(jù)的內(nèi)、外存交換，則稱之為外部排序。內(nèi)排序適用于記錄個數(shù)不是很多的小文件，而外排序則適用于記錄個數(shù)太多，不能一次性放人內(nèi)存的大文件。按策略劃分，內(nèi)部排序方法可以分為五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。幾乎所有的排序都有兩個基本的操作：（1）關(guān)鍵字大小的比較。（2）改變記錄的位置。具體處理方式依賴于記錄的存儲形式，對于順序型記錄，一般移動記錄本身，而鏈?zhǔn)酱鎯Φ挠?/p>

29、錄則通過改變指向記錄的指針實現(xiàn)重定位。為了簡化描述，在下面的講解中，我們只考慮記錄的關(guān)鍵字，則其存儲結(jié)構(gòu)也簡化為數(shù)組或鏈表。并約定排序結(jié)果為遞增。排序的算法很多，不同的算法有不同的優(yōu)缺點，沒有哪種算法在任何情況下都是最好的。評價一種排序算法好壞的標(biāo)準(zhǔn)主要有兩條：（1）執(zhí)行時間和所需的輔助空間，即時間復(fù)雜度和空間復(fù)雜度；（2）算法本身的復(fù)雜程度，比如算法是否易讀、是否易于實現(xiàn)。二、插入排序插入排序的基本思想是：每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的記錄集中，使記錄依然有序，直到所有待排序記錄全部插入完成。1直接插入排序假設(shè)待排序數(shù)據(jù)存放在數(shù)組A1.n中，則A1可看作是一個有

30、序序列，讓i從2開始，依次將Ai插入到有序序列A1.i-1中，An插入完畢則整個過程結(jié)束，A1.n成為有序序列。排序過程示例 （用【 】表示有序序列）待排序數(shù)據(jù)：【25】 54 8 54 21 1 97 2 73 15 （n=10）i=2：【25 54】 8 54 21 1 97 2 73 15i=3：【8 25 54】 54 21 1 97 2 73 15i=4：【8 25 54 54】 21 1 97 2 73 15i=5：【8 21 25 54 54】 1 97 2 73 15i=6：【1 8 21 25 54 54】 97 2 73 15i=7：【1 8 21 25 54 54 97】

31、 2 73 15i=8：【1 2 8 21 25 54 54 97】 73 15i=9：【1 2 8 21 25 54 54 73 97】 15i=10：【1 2 8 15 21 25 54 54 73 97】 排序結(jié)束算法實現(xiàn)可在數(shù)組中增加元素A0作為關(guān)鍵值存儲器和循環(huán)控制開關(guān)。第i趟排序，即Ai的插入過程為： 保存AiA0 如果Aj<=A0（即待排序的Ai），則A0Aj+1，完成插入； 否則，將Aj后移一個位置：AjAj+1；繼續(xù)執(zhí)行對于上面的數(shù)據(jù)實例，i從2依次變化到10的過程中，j值分別為1，0，3，1，0，6，1，7，3算法分析l 穩(wěn)定性：穩(wěn)定l 時間復(fù)雜度：原始數(shù)據(jù)正序，總比

32、較次數(shù)：n-1原始數(shù)據(jù)逆序，總比較次數(shù)：原始數(shù)據(jù)無序，第i趟平均比較次數(shù)=，總次數(shù)為：可見，原始數(shù)據(jù)越趨向正序，比較次數(shù)和移動次數(shù)越少。l 空間復(fù)雜度：僅需一個單元AO2希爾排序基本思想任取一個小于n的整數(shù)S1作為增量，把所有元素分成S1個組。所有間距為S1的元素放在同一個組中。第一組：A1，AS1+1，A2*S1+1，第二組：A2，AS1+2，A2*S1+2，第三組：A3，AS1+3，A2*S1+3，第s1組：AS1，A2*S1，A3*S1，先在各組內(nèi)進(jìn)行直接插人排序；然后，取第二個增量S2（<S1）重復(fù)上述的分組和排序，直至所取的增量St=1（St<St-1<St-2&l

33、t;<S2<S1），即所有記錄放在同一組中進(jìn)行直接插入排序為止。排序示例序 號12345678910原始數(shù)據(jù)1289573296375457957S1=5組別排序結(jié)果1254532573789577996S2=3組別排序結(jié)果1254532573789577996S3=2組別排序結(jié)果5321237575479578996S4=1組別排序結(jié)果5123237545757798996算法實現(xiàn)由于在分組內(nèi)部使用的是直接插入排序，因此排序過程只要在直接插入排序的算法上對j的步長進(jìn)行修改就可以了。算法分析l 穩(wěn)定性：不穩(wěn)定l 時間復(fù)雜度：Shell排序的執(zhí)行時間依賴于增量序列。如實例所示，選擇增

34、量系列為5-2-1的比較次數(shù)<增量系列為5-3-2-1的比較次數(shù)。在直接插入排序中，數(shù)據(jù)越趨向于有序，比較和移動次數(shù)越少，Shell排序的目的則是增加這種有序趨勢。雖然看起來重復(fù)次數(shù)較多，需要多次選擇增量，但開始時，增量較大，分組較多，但由于各組的數(shù)據(jù)個數(shù)少，則比較次數(shù)累計值也小，當(dāng)增量趨向1時，組內(nèi)數(shù)據(jù)增多，而所有數(shù)據(jù)已經(jīng)基本接近有序狀態(tài)，因此，Shell的時間性能優(yōu)于直接插入排序。l 空間復(fù)雜度：僅需一個單元AO三、交換排序交換排序的基本思想是：兩兩比較待排序的數(shù)據(jù)，發(fā)現(xiàn)兩個數(shù)據(jù)的次序相反則進(jìn)行交換，直到?jīng)]有反序的數(shù)據(jù)為止。1冒泡排序排序思想最多進(jìn)行n-1趟排序，每趟排序時，從底部向

35、上掃描，一旦發(fā)現(xiàn)兩個相鄰的元素不符合規(guī)則，則交換。我們發(fā)現(xiàn)，第一趟排序后，最小值在A1，第二趟排序后，較小值在A2，第n-1趟排序完成后，所有元素完全按順序排列。排序示例待排序數(shù)據(jù)：53 33 19 53 3 63 82 20 19 39第一趟排序：3 53 33 19 53 19 63 82 20 39第二趟排序：3 19 53 33 19 53 20 63 82 39第三趟排序：3 19 19 53 33 20 53 39 63 82第四趟排序：3 19 19 20 53 33 39 53 63 82第五趟排序：沒有反序數(shù)據(jù)，排序結(jié)束。算法分析l 穩(wěn)定性：穩(wěn)定l 時間復(fù)雜度：原始數(shù)據(jù)正序，

36、需一趟排序，比較次數(shù)n-1=O(n)原始數(shù)據(jù)反序，需n-1趟排序，比較次數(shù)一般情況下，雖然不一定需要n-1趟排序，但由于每次數(shù)據(jù)位置的改變需要3次移動操作，因此，總時間復(fù)雜度高于直接插入排序。l 空間復(fù)雜度：僅需一個中間變量改進(jìn)可以在每趟排序時，記住最后一次發(fā)生交換發(fā)生的位置，則該位置之前的記錄均已有序。下一趟排序掃描到該位置結(jié)束。利用這種方式，可以減少一部分比較次數(shù)。2快速排序排序思想在A1.n中任取一個數(shù)據(jù)元素作為比較的“基準(zhǔn)”（不妨記為X），將數(shù)據(jù)區(qū)劃分為左右兩個部分：A1.i-1和Ai+1.n，且A1.i-1XAi+1.n(1in)，當(dāng)A1.i-1和Ai+1.n非空時，分別對它們進(jìn)行上

37、述的劃分過程，直至所有數(shù)據(jù)元素均已排序為止。算法實現(xiàn)可以使用遞歸函數(shù)實現(xiàn)這一算法。假定待排序序列的下標(biāo)范圍為lowhigh。借用兩個整型變量i、j作為指針，約定初值分別為low、high。排序過程如下： 選定基準(zhǔn)X（不妨用Alow） j向前掃描，直到Aj<X，交換Ai與Aj，i+1。保證了Alow.i-1X i向后掃描，直到Ai>X，交換Ai與Aj，j-1。保證了XAj.high 繼續(xù)執(zhí)行、，直到i=j。這時，X恰好在Ai位置上。 對序列Alow.i-1及Ai+1.high按照上述規(guī)律繼續(xù)劃分，直到序列為空。仔細(xì)分析算法，我們發(fā)現(xiàn)，在排序中，我們總是用基準(zhǔn)X與另一數(shù)據(jù)交換，因此，一

38、趟排序結(jié)束后，X就能確切定位其最終位置。排序過程示例待排序數(shù)據(jù)： 67 67 14 52 29 9 90 54 87 71X=67 i j掃描j i j 交換 54 67 14 52 29 9 90 67 87 71掃描i i j 交換 54 67 14 52 29 9 67 90 87 71j=i，結(jié)束 ij 第一趟排序后：54 67 14 52 29 9 67 90 87 71第二趟排序后： 9 29 14 52 54 67 67 71 87 90第三趟排序后：9 29 14 52 54 67 67 71 87 90第四趟排序后：9 14 29 52 54 67 67 71 87 90第五

39、趟排序后：9 14 29 52 54 67 67 71 87 90算法分析l 穩(wěn)定性：不穩(wěn)定。l 時間復(fù)雜度：每趟排序所需的比較次數(shù)為待排序區(qū)間的長度-1，排序趟數(shù)越多，占用時間越多。最壞情況：每次劃分選取的基準(zhǔn)恰好都是當(dāng)前序列中的最小(或最大)值，劃分的結(jié)果Alow.i-1為空區(qū)間或Ai+1.high是空區(qū)間，且非空區(qū)間長度達(dá)到最大值。這種情況下，必須進(jìn)行n-1趟快速排序，第i次趟去見長度為n-i+1，總的比較次數(shù)達(dá)到最大值：n(n-1)/2=O(n2)最好情況：每次劃分所取的基準(zhǔn)都是當(dāng)前序列中的“中值”，劃分后的兩個新區(qū)間長度大致相等。共需lgn趟快速排序，總的關(guān)鍵字比較次數(shù)：O(nlgn

40、)基準(zhǔn)的選擇決定了算法性能。經(jīng)常采用選取low和high之間一個隨機位置作為基準(zhǔn)的方式改善性能。l 空間復(fù)雜度：快速排序在系統(tǒng)內(nèi)部需要一個棧來實現(xiàn)遞歸，最壞情況下為O(n)，最佳情況下為O(lgn)。四、選擇排序選擇排序的基本思想是：每一趟從待排序的數(shù)據(jù)中選出最小元素，順序放在已排好序的數(shù)據(jù)最后，直到全部數(shù)據(jù)排序完畢。1直接選擇排序過程模擬待排序數(shù)據(jù)92286284621656873366第一趟排序16286284629256873366第二趟排序16286284629256873366第三趟排序16283384629256876266第四趟排序16283356629284876266第五趟排

41、序16283356629284876266第六趟排序16283356626284879266第七趟排序16283356626266879284第八趟排序16283356626266849287第九趟排序16283356626266848792算法分析l 穩(wěn)定性：不穩(wěn)定。l 時間復(fù)雜度：O(n2)。l 空間復(fù)雜度：僅需一個中間單元A0。2堆排序排序思想堆排序是一種樹形選擇排序，在排序過程中，將A1.n看成是完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系來選擇最小的元素。堆的定義：n個元素的序列K1，K2，K3，Kn稱為堆，當(dāng)且僅當(dāng)該序列滿足特性：KiK2i ， Ki

42、K2i+1（1in/2）堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉子結(jié)點的關(guān)鍵字均大于等于其孩子結(jié)點的關(guān)鍵字。例如序列1,35,14,60,61,45,15,81就是一個堆，它對應(yīng)的完全二叉樹如下圖1所示。這種堆中根結(jié)點（稱為堆頂）的關(guān)鍵字最小，我們把它稱為小根堆。反之，若完全二叉樹中任一非葉子結(jié)點的關(guān)鍵字均大于等于其孩子的關(guān)鍵字，則稱之為大根堆。圖1 最小堆 圖2 最大堆存儲結(jié)構(gòu)：816061451511435135146061451581堆排序過程（以最大堆為例）第一、調(diào)整堆假定待排序數(shù)組A為20，12，35，15，10，80，30，17，2，1（n=10），初始完全樹狀態(tài)為：圖3

43、圖4結(jié)點（20）、（35）、(12)等，值小于其孩子結(jié)點，因此，該樹不屬最大堆。為了將該樹轉(zhuǎn)化為最大堆，從后往前查找，自第一個具有孩子的結(jié)點開始，根據(jù)完全二叉樹性質(zhì)，這個元素在數(shù)組中的位置為i=n/2，如果以這個結(jié)點為根的子樹已是最大堆，則此時不需調(diào)整，否則必須調(diào)整子樹使之成為堆。隨后，繼續(xù)檢查以i-1、i-2等結(jié)點為根的子樹，直到檢查到整個二叉樹的根結(jié)點（i=1），并將其調(diào)整為堆為止。調(diào)整方法：由于Ai的左、右子樹均已是堆，因此A2i和A2i+1分別是各自子樹中關(guān)鍵字最大的結(jié)點。若Ai不小于A2i和A2i+1，則Ai沒有違反堆性質(zhì)，那么以Ai為根的子樹已是堆，無須調(diào)整；否則必須將Ai和A2i

44、與A2i+1中較大者（不妨設(shè)為Aj）進(jìn)行交換。交換后又可能使結(jié)點Aj違反堆性質(zhì)，同樣由于該結(jié)點的兩棵子樹仍然是堆，故可重復(fù)上述的調(diào)整過程，直到當(dāng)前被調(diào)整的結(jié)點已滿足堆性質(zhì)，或者該結(jié)點已是葉子結(jié)點為止。以上圖為例，經(jīng)過調(diào)整后，最大堆為：80，17，35，12，10，20，30，15，2，1。如圖4所示。此堆作為排序的初始無序區(qū)。第二、選擇、交換、調(diào)整將建成的最大堆作為初始無序區(qū)。將堆頂元素（根）A1和An交換，由此得到新的無序區(qū)A1.n-1和有序區(qū)An，且滿足A1.n-1An將A1.n-1調(diào)整為堆。再次將A1和無序區(qū)最后一個數(shù)據(jù)An-1交換，由此得到新的無序區(qū)A1.n-2和有序區(qū)An-1.n，且

45、仍滿足關(guān)系A(chǔ)1.n-2An-1.n，同樣要將A1.n-2調(diào)整為堆。直到無序區(qū)只有一個元素A1為止。說明：如果需要生成降序序列，則利用最小堆進(jìn)行操作。算法分析l 穩(wěn)定性：不穩(wěn)定。假定數(shù)據(jù)序列為1，1，已是大堆，經(jīng)過排序后，結(jié)果為1，1。l 時間復(fù)雜度：堆排序的時間，主要由建立初始堆和反復(fù)調(diào)整堆這兩部分的時間開銷構(gòu)成，它們均是通過調(diào)用editheap函數(shù)實現(xiàn)的。堆排序的最壞時間復(fù)雜度為O(nlgn)。堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。l 空間復(fù)雜度：O(1)五、歸并排序歸并排序是利用“歸并”技術(shù)來進(jìn)行排序。歸并是指將若干個已排序的

46、子文件合并成一個有序的文件。1兩路歸并算法基本思路設(shè)有兩個有序（升序）序列存儲在同一數(shù)組中相鄰的位置上，不妨設(shè)為Al.m，Am+1.h，將它們歸并為一個有序數(shù)列，并存儲在Al.h。為了減少數(shù)據(jù)移動次數(shù)，不妨采用一個臨時工作數(shù)組C，將中間排序結(jié)果暫時保存在C數(shù)組中，等歸并結(jié)束后，再將C數(shù)組值復(fù)制給A。歸并過程中，設(shè)置p1，p2和p3三個指針，其初值分別指向三個有序區(qū)的起始位置。歸并時依次比較Ap1和Ap2的關(guān)鍵字，取關(guān)鍵字較小的記錄復(fù)制到Cp3中，然后將被復(fù)制記錄的指針p1或p2加1，以及指向復(fù)制位置的指針p3加1。重復(fù)這一過程直至有一個已復(fù)制完畢，此時將另一序列中剩余數(shù)據(jù)依次復(fù)制到C中即可。2歸并排序歸并排序有兩種實現(xiàn)方法：自底向上和自頂向下。自底向上的方法自底向上的基本思想是：第1趟歸并排序時，將數(shù)列A1.n看作是n個長度為1的有序序列，將這些序列兩兩歸并，若n為偶數(shù)，則得到n/2個長度為2的有序序列；若n為奇數(shù)，則最后一個子序列不參與歸并。第2趟歸并則是將第1趟歸并所得到的有序序列兩兩歸并。如此反復(fù)，直到最后得到一個長度為n的有序文件為止。上述的每次歸并操作，均是將兩個有序序列合并成一個有序序列，故稱其為“二路歸并排序”。類似地有k(k>2)路歸并排序。自頂向下的方法采用分治法進(jìn)行自