畢業(yè)設(shè)計(jì)（論文）排序演示系統(tǒng)的設(shè)計(jì)

1、三江學(xué)院畢業(yè)設(shè)計(jì)報(bào)告題 目 排序演示系統(tǒng)的設(shè)計(jì) 子題目 計(jì)算機(jī)科學(xué)與工程 系 計(jì)算機(jī)科學(xué)與技術(shù) 專業(yè)學(xué) 號(hào) 姓 名 指導(dǎo)教師 起訖日期 2007年 月 日 月 日 設(shè)計(jì)地點(diǎn) l317 摘 要本設(shè)計(jì)使用軟件工程方法，采用visual c+6.0作為開發(fā)工具，制作出排序演示系統(tǒng)。排序在數(shù)據(jù)處理中占有極重要的位置,排序算法的好壞,直接影響到程序?qū)崿F(xiàn)的復(fù)雜度。本文動(dòng)態(tài)地演示排序過程，使得它的演示更形象，有利于教學(xué)。詳細(xì)討論了各種排序法的實(shí)現(xiàn)思想和改進(jìn),最后對(duì)這些排序算法進(jìn)行了比較。本設(shè)計(jì)共有五章，其中第三章里講到了排序演示系統(tǒng)所用到的關(guān)鍵技術(shù)。關(guān)鍵詞：排序算法 vc+abstractthis desi

2、gn uses the software engineering method, creates a sort demonstrate system with using visual c+ programming language ,sorting plays important role in the data processing. sort algorithm quality, affects the realization order of complexity directly. the author designs a new way to dynamically demonst

3、rate ordering procedure by using the complementary attribute, and the demonstration more visual for teaching was made. this article introduced commonly used based on the comparison sort algorithm and non- based on the comparison linearity sort algorithm, and discussed each kind of arrangement method

4、 realization thought and the improvement in detail, finally has carried on the comparison to these sort algorithms. this design totally contains five chapters, among them the third chapter is speaking system using technique.key words: sort algorithm vc+目 錄摘 要iabstractii目 錄iii第一章 概述41.1 選題意義、背景41.2 主

5、要技術(shù)4第二章 系統(tǒng)設(shè)計(jì)52.1 需求分析52.2 系統(tǒng)功能模塊設(shè)計(jì)5第三章 詳細(xì)設(shè)計(jì)73.1 visual c+6.0和c+73.2 隨機(jī)數(shù)生成的設(shè)計(jì)及注釋93.3 排序介紹103.4 各種排序算法介紹113.5 排序算法設(shè)計(jì)代碼及注釋153.6 各種排序算法小結(jié)233.7 排序算法總結(jié)比較24第四章 部分功能測(cè)試圖25第五章 關(guān)鍵問題26結(jié)束語27致謝28第一章 概述1.1 選題意義、背景排序（sorting）是指將一個(gè)數(shù)據(jù)元素序列排列成為一個(gè)有序序列的過程。排序是計(jì)算機(jī)科學(xué)的一個(gè)重要領(lǐng)域，并廣泛應(yīng)用于數(shù)據(jù)處理，情報(bào)檢索，商業(yè)金融及企業(yè)管理等許多方面。資料表明，在當(dāng)今的計(jì)算機(jī)系統(tǒng)中，有50

6、以上的cpu時(shí)間是用在排序數(shù)據(jù)上的。目前人們已經(jīng)提出了許多不同的排序算法，本文選擇其中最基本也是最常用的一些算法進(jìn)行討論，介紹它們的基本思想和實(shí)現(xiàn)過程，分析各種算法的時(shí)間與空間復(fù)雜度，以清晰描述排序演示系統(tǒng)。 作為計(jì)算機(jī)科學(xué)中一項(xiàng)復(fù)雜而重要的技術(shù)，排序一直是計(jì)算機(jī)領(lǐng)域內(nèi)人們感興趣的課題，尋找速度快、附加存儲(chǔ)空間開銷小的高效排序算法也一直是人們追尋的目標(biāo)。本文討論整數(shù)數(shù)組元素的排序，分析幾種常見排序算法并進(jìn)行比較。排序是程序設(shè)計(jì)中非常重要的內(nèi)容，每一種程序設(shè)計(jì)語言中都涉及到排序，它的功能是將一組無序的數(shù)據(jù)序列變成有序的數(shù)據(jù)序列，結(jié)果一般只有兩種情況：數(shù)據(jù)從大到小排列或者從小到大排列。排序的算法有

7、很多種，常用的有三種，即冒泡排序、選擇排序和插入排序。要判斷排序算法的優(yōu)劣，一般有兩個(gè)標(biāo)準(zhǔn)：一是算法執(zhí)行所需的時(shí)間，又稱時(shí)間復(fù)雜度；二是算法所需的存儲(chǔ)空間，又稱空間復(fù)雜度。排序算法的優(yōu)劣將直接影響到程序的性能。 隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，排序（sorting）仍將成為計(jì)算機(jī)科學(xué)的一個(gè)重要組成部分。早期計(jì)算機(jī)多用于進(jìn)行簡單的數(shù)值計(jì)算，輸入和輸出的數(shù)據(jù)量不大，數(shù)據(jù)元素之間的關(guān)系較為簡單，數(shù)據(jù)處理時(shí)間較長，但是自從第一臺(tái)計(jì)算機(jī)誕生，隨著操作系統(tǒng)從簡單到復(fù)雜，從低級(jí)到高級(jí)的發(fā)展，排序速度也越來越快，當(dāng)處理大批量數(shù)據(jù)，特別是成千上萬的數(shù)據(jù)時(shí)，時(shí)間也挺長，但是效率已相當(dāng)高了。操作系統(tǒng)大概經(jīng)歷了以下幾個(gè)階段

8、：一.手工操作階段 二.早期批量處理階段 三.管理程序階段 四.多道程序設(shè)計(jì)與多道批處理系統(tǒng)。有了這許多硬件和軟件的支持，排序算法的實(shí)現(xiàn)就有了強(qiáng)大的支撐力，從而為我們的計(jì)算機(jī)科學(xué)注入了活力。 計(jì)算機(jī)已經(jīng)深入到人類社會(huì)的各個(gè)領(lǐng)域，其應(yīng)用已經(jīng)不再局限于科學(xué)計(jì)算，而更多用于控制，管理及數(shù)據(jù)處理等非數(shù)值計(jì)算的處理工作。另外，計(jì)算機(jī)加工處理的對(duì)象由純粹的數(shù)值發(fā)展到字符，表格和圖象等各種具有一定結(jié)構(gòu)的數(shù)據(jù)，這就必須分析待處理對(duì)象的特性以及各處理對(duì)象之間存在的關(guān)系，而排序是其中必不可少的一份子。所以展望計(jì)算機(jī)世界，數(shù)據(jù)結(jié)構(gòu)是它的支持框架，而作為數(shù)據(jù)結(jié)構(gòu)中排序一大塊，其作用是非同小可的，我們不再論述，且用我們

9、有限的時(shí)間去不斷學(xué)習(xí)計(jì)算機(jī)這門科學(xué)，讓它為我們的學(xué)習(xí)生活服務(wù)。1.2 主要技術(shù)微軟基本類庫(mfc)是一個(gè)應(yīng)用框架，用c+寫的。mfc提供許多代碼，為了管理窗口、菜單和對(duì)話框;執(zhí)行基本的輸入輸出;存儲(chǔ)搜集數(shù)據(jù)對(duì)象等。將增加您所需要的，有特殊用途的代碼進(jìn)入這個(gè)框架。而此次設(shè)計(jì)用到的主要技術(shù)就是隨機(jī)數(shù)的生成以及各種排序算法的實(shí)現(xiàn)。第二章 系統(tǒng)設(shè)計(jì)2.1 需求分析數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)相關(guān)專業(yè)的重要基礎(chǔ)課，排序算法是數(shù)據(jù)結(jié)構(gòu)教學(xué)的重點(diǎn)和難點(diǎn)。然而用傳統(tǒng)靜態(tài)的講法形式很難將排序算法的執(zhí)行過程動(dòng)態(tài)地演示出來，影響了教學(xué)效果。有必要設(shè)計(jì)排序算法演示系統(tǒng)，幫助學(xué)生更快地掌握算法。并且要求系統(tǒng)同步顯示算法的源代碼，

10、使算法的執(zhí)行過程一目了然，從而提高教學(xué)效果。2.2 系統(tǒng)功能模塊設(shè)計(jì)以visual c+編寫一個(gè)基于對(duì)話框的程序，我們假設(shè)待排序的數(shù)字的總數(shù)為10，排序的整個(gè)過程為（每個(gè)步驟對(duì)應(yīng)一個(gè)按鈕）：（1）數(shù)字分散：模擬編號(hào)分散開來的過程對(duì)應(yīng)的按鈕為：idc_button1按鈕標(biāo)題為：編號(hào)分散 （2）分配數(shù)字：模擬給每個(gè)編號(hào)一個(gè)3位或4位的數(shù)字的過程對(duì)應(yīng)的按鈕為：idc_button2按鈕標(biāo)題為：產(chǎn)生數(shù)字（3）集合：所有編號(hào)在獲得數(shù)字后，為進(jìn)行排序，他們需要先集合對(duì)應(yīng)的按鈕為：idc_button3按鈕標(biāo)題為：編號(hào)集合（4）排序：a.對(duì)應(yīng)的按鈕為：idc_button4 按鈕標(biāo)題為：冒泡排序b.交換排序

11、對(duì)應(yīng)的按鈕為：idc_button5按鈕標(biāo)題為：交換排序c.選擇排序?qū)?yīng)的按鈕為：idc_button6按鈕標(biāo)題為：選擇排序整個(gè)對(duì)話框的消息映射關(guān)系為：begin_message_map (cmy520dlg, cdialog)/afx_msg_map(cmy520dlg)on_wm_syscommand ()on_wm_paint ()on_wm_querydragicon ()on_bn_clicked (idc_button1, onbutton1)on_bn_clicked (idc_button2, onbutton2)on_bn_clicked (idc_button3, onbu

12、tton3)on_bn_clicked (idc_button4, onbutton4)on_bn_clicked (idc_button5, onbutton5)on_bn_clicked (idc_button6, onbutton6)/afx_msg_mapend_message_map ()第三章 詳細(xì)設(shè)計(jì)3.1 visual c+6.0和c+3.1.1 visual c+6.0簡介visual c+ 6.0是microsoft公司推出的功能強(qiáng)大的軟件開發(fā)平臺(tái)，是運(yùn)行于windows上的交互式可視化集成開發(fā)環(huán)境。是程序員首選的開發(fā)工具之一。跟其他的可視化集成開發(fā)環(huán)境一樣，visual

13、c+6.0集程序的代碼編輯、編譯、連接、調(diào)試等于一體，給編程人員提供了一個(gè)完整而又方便的開發(fā)界面和許多有效的輔助開發(fā)工具。visual c+ 6.0的appwizard可以為很大的程序提供框架代碼，用戶不需要書寫代碼，只需要按幾個(gè)按紐就可以生成一個(gè)完整的可以運(yùn)行的程序。visual c+ 6.0以ansi c+為基礎(chǔ)，并在此基礎(chǔ)上進(jìn)行了大量的擴(kuò)展，以適應(yīng)開發(fā)各種windows應(yīng)用程序的需要。到目前為止，絕大多數(shù)windows應(yīng)用程序都是用visual c+ 6.0或其早期版本開發(fā)而成的，visual c+ 6.0己成為在windows環(huán)境下進(jìn)行大型軟件開發(fā)的首選。首先vc是一個(gè)軟件（ide集成

14、開發(fā)環(huán)境）（編譯、編輯、調(diào)試） ，c和c+。但c+中的有些特性是不用的，例如i/o流，多態(tài)繼承 ，windows sdk（軟件開發(fā)工具）， vc的靈魂：mfc（微軟基礎(chǔ)類庫） ，atl（activex模板類庫） ，其他的sdk，如opengl, directx, active movie, draw dib (wing)。visual c+ 6.0以ansi c+為基礎(chǔ)，并在此基礎(chǔ)上進(jìn)行了大量的擴(kuò)展，以適應(yīng)開發(fā)各種windows應(yīng)用程序的需要。到目前為止，絕大多數(shù)windows應(yīng)用程序都是用visual c+ 6.0或其早期版本開發(fā)而成的，visual c+ 6.0己成為在windows環(huán)境下

15、進(jìn)行大型軟件開發(fā)的首選。3.1.2 c+簡介隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展以及軟件程序的高度復(fù)雜化，面向?qū)ο蟪绦蛟O(shè)計(jì)的重要性也越來越突顯出來，而c+語言則是面向?qū)ο蟪绦蛟O(shè)計(jì)的最重要的代表性語言之一。c+語言是在c語言的基礎(chǔ)上，吸收面向?qū)ο蟪绦蛟O(shè)計(jì)的概念，發(fā)展起來的一種高效實(shí)用的程序設(shè)計(jì)語言。c+既支持面向過程的程序設(shè)計(jì)方法，也支持面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，既可以開發(fā)系統(tǒng)軟件，也可以開發(fā)普通的應(yīng)用軟件，因此得到廣大軟件開發(fā)人員的青睞。隨著c+成為ansi標(biāo)準(zhǔn)，c+迅速成為程序員廣泛使用的工具。c+語言最初是由at&t貝爾實(shí)驗(yàn)室的bjarne stroustrup博士設(shè)計(jì)、實(shí)現(xiàn)的，1980年首次投入使用，

16、當(dāng)時(shí)它只支持系統(tǒng)程序設(shè)計(jì)技術(shù)和數(shù)據(jù)抽象；1983年，c+語言增大了對(duì)基本的面向?qū)ο蟪绦蛟O(shè)計(jì)的支持；1985年，c+第一次走向市場(chǎng)；1987年至1989年，增加了對(duì)類屬程序設(shè)計(jì)的支持。c+的標(biāo)準(zhǔn)化工作于1990年啟動(dòng)，主要由ansi(american national standard institute)以及后來加入的iso(international standard organization)負(fù)責(zé)，1998年正式發(fā)布了第一個(gè)國際標(biāo)準(zhǔn)(iso/iec14882)。3.1.3 visual c+6.0和c+的關(guān)系vc+只是1個(gè)c+的集成開發(fā)環(huán)境。vc+以c+為編程語言，并在c+的基礎(chǔ)上增加了m

17、fc（微軟基礎(chǔ)類庫），可以比單純使用c+程序設(shè)計(jì)語言更為簡單、高效地開發(fā)windows程序。最常用的mfc類： cwnd cdocument cview cdc cdialog cwinapp cgdiobject及子類 cstring、cpoint、crect、csize等簡單數(shù)據(jù)類型 cfile 以上提到的這些內(nèi)容，是每個(gè)人都會(huì)用到的內(nèi)容。 3.2 隨機(jī)數(shù)生成的設(shè)計(jì)及注釋srand (unsigned) time (null); /產(chǎn)生10個(gè)3/4位的數(shù) for (int i = 0; i 10; i+) int temp; temp = rand (); if (temp % 2 = 0

18、) /產(chǎn)生3位數(shù) while (temp % 1000 100) temp = rand (); sortobjecti.inumber = temp % 1000; else /產(chǎn)生4位數(shù) while (temp % 10000 1000) temp = rand(); sortobjecti.inumber = temp % 10000; 3.3 排序介紹排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列。內(nèi)部排序和外部排序：若整個(gè)排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序； 反之，若參加排序的記錄數(shù)量很大，整個(gè)序列的排序過程不可能在

19、內(nèi)存中完成，則稱此類排序問題為外部排序。內(nèi)部排序的過程是一個(gè)逐步擴(kuò)大記錄的有序序列長度的過程。 內(nèi)排序的方法有許多種，按所用策略不同，可歸納為五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。其中，插入排序主要包括直接插入排序和希爾排序兩種；選擇排序主要包括直接選擇排序和堆排序；交換排序主要包括氣（冒）泡排序和快速排序。3.4 各種排序算法介紹3.4.1 冒泡排序冒泡排序的基本概念是：依次比較相鄰的兩個(gè)數(shù)，將大數(shù)放在前面，小數(shù)放在后面。即首先比較第1個(gè)和第2個(gè)數(shù)，將大數(shù)放前，小數(shù)放后。然后比較第2個(gè)數(shù)和第3個(gè)數(shù)，將大數(shù)放前，小數(shù)放后，如此繼續(xù)，直至比較最后兩個(gè)數(shù)，將大數(shù)放前，小數(shù)放后，此

20、時(shí)第一趟結(jié)束，在最后的數(shù)必是所有數(shù)中的最小數(shù)。重復(fù)以上過程，仍從第一對(duì)數(shù)開始比較（因?yàn)榭赡苡捎诘?個(gè)數(shù)和第3個(gè)數(shù)的交換，使得第1個(gè)數(shù)不再大于第2個(gè)數(shù)），將大數(shù)放前，小數(shù)放后，一直比較到最小數(shù)前的一對(duì)相鄰數(shù)，將大數(shù)放前，小數(shù)放后，第二趟結(jié)束，在倒數(shù)第二個(gè)數(shù)中得到一個(gè)新的最小數(shù)。如此下去，直至最終完成排序。由于在排序過程中總是大數(shù)往前放，小數(shù)往后放，相當(dāng)于氣泡往上升，所以稱作冒泡排序。用二重循環(huán)實(shí)現(xiàn)，外循環(huán)變量設(shè)為i，內(nèi)循環(huán)變量設(shè)為j。外循環(huán)重復(fù)9次，內(nèi)循環(huán)依次重復(fù)9，8，.，1次。每次進(jìn)行比較的兩個(gè)元素都是與內(nèi)循環(huán)j有關(guān)的，它們可以分別用aj和aj+1標(biāo)識(shí)，i的值依次為1,2,.,9，對(duì)于每一個(gè)

21、i, j的值依次為1,2,.10-i。產(chǎn)生在許多程序設(shè)計(jì)中，我們需要將一個(gè)數(shù)列進(jìn)行排序，以方便統(tǒng)計(jì)，常見的排序方法有冒泡排序，二叉樹排序，選擇排序等等。而冒泡排序一直由于其簡潔的思想方法和比較高的效率而倍受青睞。排序過程設(shè)想被排序的數(shù)組r1.n垂直豎立，將每個(gè)數(shù)據(jù)元素看作有重量的氣泡，根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組r，凡掃描到違反本原則的輕氣泡，就使其向上漂浮，如此反復(fù)進(jìn)行，直至最后任何兩個(gè)氣泡都是輕者在上，重者在下為止。算法示例49 13 13 13 13 13 13 13 38 49 27 27 27 27 27 27 65 38 49 38 38 38 38 38 9

22、7 65 38 49 49 49 49 49 76 97 65 49 49 49 49 49 13 76 97 65 65 65 65 65 27 27 76 97 76 76 76 76 49 49 49 76 97 97 97 97 procedure bubblesort(var r : filetype) /從下往上掃描的起泡排序/ begin for i := 1 to n-1 do /做n-1趟排序/ begin noswap := true; /置未排序的標(biāo)志/ for j := n - 1 downto 1 do /從底部往上掃描/ begin if rj+1 rj then

23、/交換元素/ begin temp := rj+1; rj+1 := rj; rj := temp; noswap := false end; end; if noswap then return/本趟排序中未發(fā)生交換，則終止算法/ end end; /bubblesort/ 該算法的時(shí)間復(fù)雜性為o(n2),算法為穩(wěn)定的排序方冒泡排序算法具體代碼#include void bubblesort(int* pdata,int count) int itemp; for(int i=1;i=i;j-) if(pdatajpdataj-1) itemp = pdataj-1; pdataj-1 =

24、pdataj; pdataj = itemp; void main() int data = 10,9,8,7,6,5,4; bubblesort(data,7); for (int i=0;i7;i+) coutdata ; cout arri+1 arr,arri+1 = arri+1,arr end end break if a1 = arr end arrend冒泡排序法的改進(jìn) 比如用冒泡排序?qū)?、5、7、1、2、3這6個(gè)數(shù)排序。在該列中，第二趟排序結(jié)束后，數(shù)組已排好序，但計(jì)算機(jī)此時(shí)并不知道已經(jīng)反排好序，計(jì)算機(jī)還需要進(jìn)行一趟比較，如果這一趟比較，未發(fā)生任何數(shù)據(jù)交換，則知道已排序好，可以

25、不再進(jìn)行比較了。因而第三趟比較還需要進(jìn)行，但第四、五趟比較則是不必要的。為此，我們可以考慮程序的優(yōu)化。為了標(biāo)志在比較中是否進(jìn)行了，設(shè)一個(gè)布爾量flag。在進(jìn)行每趟比較前將flag置成true。如果在比較中發(fā)生了數(shù)據(jù)交換，則將flag置為false，在一趟比較結(jié)束后，再判斷flag，如果它仍為true（表明在該趟比較中未發(fā)生一次數(shù)據(jù)交換）則結(jié)束排序，否則進(jìn)行下一趟比較。性能分析 若記錄序列的初始狀態(tài)為正序，則冒泡排序過程只需進(jìn)行一趟排序，在排序過程中只需進(jìn)行n-1次比較，且不移動(dòng)記錄；反之，若記錄序列的初始狀態(tài)為逆序，則需進(jìn)行n(n-1)/2次比較和記錄移動(dòng)。因此冒泡排序總的時(shí)間復(fù)雜度為o(n*

26、n)。3.4.2 交換排序所謂交換，就是根據(jù)序列中兩個(gè)記錄鍵值的比較結(jié)果來對(duì)換這兩個(gè)記錄在序列中的位置，交換排序的特點(diǎn)是：將鍵值較大的記錄向序列的尾部移動(dòng)，鍵值較小的記錄向序列的前部移動(dòng)。3.4.3 選擇排序1. 基本思想：每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。2. 排序過程：【示例】： 初始關(guān)鍵字 49 38 65 97 76 13 27 49第一趟排序后 13 38 65 97 76 49 27 49第二趟排序后 13 27 65 97 76 49 38 49第三趟排序后 13 27 38 97 76 49 65

27、 49第四趟排序后 13 27 38 49 49 97 65 76第五趟排序后 13 27 38 49 49 97 65 76第六趟排序后 13 27 38 49 49 65 97 76第七趟排序后 13 27 38 49 49 76 97 76最后排序結(jié)果 13 27 38 49 49 76 76 973.void selectionsort(type* arr,long len) long i=0,j=0;/*iterator value*/ long maxpos; assertf(arr!=null,in insertsort sort,arr is nulln); for(i=len

28、-1;i=1;i-) maxpos=i; for(j=0;ji;j+) if(arrmaxposarrj)maxpos=j; if(maxpos!=i)swaparrdata(arr,maxpos,i); 選擇排序法的第一層循環(huán)從起始元素開始選到倒數(shù)第二個(gè)元素,主要是在每次進(jìn)入的第二層循環(huán)之前,將外層循環(huán)的下標(biāo)賦值給臨時(shí)變量,接下來的第二層循環(huán)中,如果發(fā)現(xiàn)有比這個(gè)最小位置處的元素更小的元素,則將那個(gè)更小的元素的下標(biāo)賦給臨時(shí)變量,最后,在二層循環(huán)退出后,如果臨時(shí)變量改變,則說明,有比當(dāng)前外層循環(huán)位置更小的元素,需要將這兩個(gè)元素交換.3.5 排序算法設(shè)計(jì)代碼及注釋3.5.1 冒泡排序cclient

29、dc dc(this);dc.setbkcolor(rgb(180, 180, 180);int objectnamesort_object_num; /每個(gè)位置對(duì)應(yīng)的成員名/初始化每個(gè)位置對(duì)應(yīng)的成員for (int i = 0; i sort_object_num; i+)objectname = i;/冒泡排序for (i = 1; i = i; j-)if (sortobjectobjectnamej.inumber sortobjectobjectnamej -1.inumber)/交換成員序號(hào)int itemp;itemp = sortobjectobjectnamej - 1.is

30、eq;sortobjectobjectnamej - 1.iseq = sortobjectobjectnamej.iseq;sortobjectobjectnamej.iseq = itemp;/交換成員位置itemp = objectnamej;objectnamej = objectnamej - 1;objectnamej - 1 = itemp;/顯示新位置cstring strname;cstring strnum;/顯示j-1位置的成員strname.format(%d, objectnamej - 1);dc.textout(objectcoordsortobjectobjec

31、tnamej - 1.iseq.x - 5,objectcoordsortobjectobjectnamej - 1.iseq.y - 8, strname);if (sortobjectobjectnamej - 1.inumber 1000)strnum.format( %d, sortobjectobjectnamej - 1.inumber);elsestrnum.format(%d, sortobjectobjectnamej - 1.inumber);dc.textout(objectcoordsortobjectobjectnamej - 1.iseq.x - 15,object

32、coordsortobjectobjectnamej - 1.iseq.y - 30, strnum);/顯示j位置的成員strname.format(%d, objectnamej);dc.textout(objectcoordsortobjectobjectnamej.iseq.x - 5,objectcoordsortobjectobjectnamej.iseq.y - 8, strname);if (sortobjectobjectnamej.inumber 1000)strnum.format( %d, sortobjectobjectnamej.inumber);elsestrnu

33、m.format(%d, sortobjectobjectnamej.inumber);dc.textout(objectcoordsortobjectobjectnamej.iseq.x - 15,objectcoordsortobjectobjectnamej.iseq.y - 30, strnum);/延遲1秒進(jìn)行下一次排序以便將排序過程顯示為動(dòng)畫sleep(1000);通過運(yùn)行上述程序，我們非常清晰地看到了較小的數(shù)冒泡的全過程，這是緣于我們?cè)诿看闻判蛑g利用sleep(1000)插入了1秒鐘的延遲。下面是我們追蹤所得的一次冒泡排序的軌跡：196 3993 2037 2953 318 2

34、815 5770 960 7325 486 196 3993 2037 2953 318 2815 5770 960 486 7325 196 3993 2037 2953 318 2815 5770 486 960 7325 196 3993 2037 2953 318 2815 486 5770 960 7325 196 3993 2037 2953 318 486 2815 5770 960 7325 196 3993 2037 318 2953 486 2815 5770 960 7325 196 3993 318 2037 2953 486 2815 5770 960 7325 19

35、6 318 3993 2037 2953 486 2815 5770 960 7325 196 318 3993 2037 2953 486 2815 960 5770 7325 196 318 3993 2037 2953 486 960 2815 5770 7325 196 318 3993 2037 486 2953 960 2815 5770 7325 196 318 3993 486 2037 2953 960 2815 5770 7325 196 318 486 3993 2037 2953 960 2815 5770 7325 196 318 486 3993 2037 960

36、2953 2815 5770 7325 196 318 486 3993 960 2037 2953 2815 5770 7325 196 318 486 960 3993 2037 2953 2815 5770 7325 196 318 486 960 3993 2037 2815 2953 5770 7325 196 318 486 960 2037 3993 2815 2953 5770 7325 196 318 486 960 2037 2815 3993 2953 5770 7325 196 318 486 960 2037 2815 2953 3993 5770 73253.5.2

37、 交換排序cclientdc dc (this) ;dc.setbkcolor(rgb(180,180,180); int objectnamesort_object_num; /每個(gè)位置對(duì)應(yīng)的成員名/初始化每個(gè)位置對(duì)應(yīng)的成員for (int i = 0; i sort_object_num; i+)objectname = i;/交換排序for(i=0;isort_object_num;i+) for(int j=i+1;jsort_object_num;j+) if(sortobjectobjectnamej.inumber sortobjectobjectname.inumber) /交

38、換成員序號(hào)int itemp;itemp = sortobjectobjectnamej.iseq; sortobjectobjectnamej.iseq =sortobjectobjectname.iseq; sortobjectobjectname.iseq = itemp; /交換成員位置itemp = objectnamej;objectnamej = objectname;objectname = itemp;/顯示新位置cstring strname;cstring strnum; /顯示j位置的成員strname.format(%d,sortobjectobjectnamej.i

39、name); dc.textout(objectcoordsortobjectobjectnamej.iseq.x-5,objectcoordsortobjectobjectnamej.iseq.y-8,strname);if(sortobjectobjectnamej.inumber1000) strnum.format( %d,sortobjectobjectnamej.inumber);elsestrnum.format(%d,sortobjectobjectnamej.inumber);dc.textout(objectcoordsortobjectobjectnamej.iseq.x

40、-15,objectcoordsortobjectobjectnamej.iseq.y-30,strnum);/顯示i位置的成員strname.format(%d,sortobjectobjectname.iname); dc.textout(objectcoordsortobjectobjectname.iseq.x-5,objectcoordsortobjectobjectname.iseq.y-8,strname);if(sortobjectobjectname.inumber1000)strnum.format( %d,sortobjectobjectname.inumber); el

41、sestrnum.format(%d,sortobjectobjectname.inumber);dc.textout(objectcoordsortobjectobjectname.iseq.x-15,objectcoordsortobjectobjectname.iseq.y-30,strnum);/延遲1秒進(jìn)行下一次排序以便將排序過程顯示為動(dòng)畫 sleep(1000); 下面是我們追蹤所得的一次交換排序的軌跡：7449 318 964 396 4973 1431 6541 2331 1489 3743 318 7449 964 396 4973 1431 6541 2331 1489 3

42、743 318 964 7449 396 4973 1431 6541 2331 1489 3743 318 396 7449 964 4973 1431 6541 2331 1489 3743 318 396 964 7449 4973 1431 6541 2331 1489 3743 318 396 964 4973 7449 1431 6541 2331 1489 3743 318 396 964 1431 7449 4973 6541 2331 1489 3743 318 396 964 1431 4973 7449 6541 2331 1489 3743 318 396 964 14

43、31 2331 7449 6541 4973 1489 3743 318 396 964 1431 1489 7449 6541 4973 2331 3743 318 396 964 1431 1489 6541 7449 4973 2331 3743 318 396 964 1431 1489 4973 7449 6541 2331 3743 318 396 964 1431 1489 2331 7449 6541 4973 3743 318 396 964 1431 1489 2331 6541 7449 4973 3743 318 396 964 1431 1489 2331 4973

44、7449 6541 3743 318 396 964 1431 1489 2331 3743 7449 6541 4973 318 396 964 1431 1489 2331 3743 6541 7449 4973 318 396 964 1431 1489 2331 3743 4973 7449 6541 318 396 964 1431 1489 2331 3743 4973 6541 74493.5.3 選擇排序cclientdc dc (this) ;dc.setbkcolor(rgb(180,180,180); int objectnamesort_object_num; /每個(gè)位

45、置對(duì)應(yīng)的成員名/初始化每個(gè)位置對(duì)應(yīng)的成員for(int i=0;isort_object_num;i+)objectname = i;/選擇排序for(i=0;isort_object_num;i+) int ipos;ipos = i;for(int j=i+1;jsort_object_num;j+) if(sortobjectobjectnamej.inumber sortobjectobjectnameipos.inumber) ipos = j;if(ipos!=i)/交換序號(hào)int itemp;itemp = sortobjectobjectnameipos.iseq; sorto

46、bjectobjectnameipos.iseq = sortobjectobjectname.iseq; sortobjectobjectname.iseq = itemp; /交換成員名itemp = objectnameipos;objectnameipos = objectname;objectname = itemp;/顯示變化cstring strname;cstring strnum; /對(duì)象iposstrname.format(%d,sortobjectobjectnameipos.iname); dc.textout(objectcoordsortobjectobjectna

47、meipos.iseq.x-5,objectcoordsortobjectobjectnameipos.iseq.y-8,strname);if(sortobjectobjectnameipos.inumber1000) strnum.format( %d,sortobjectobjectnameipos.inumber);elsestrnum.format(%d,sortobjectobjectnameipos.inumber);dc.textout(objectcoordsortobjectobjectnameipos.iseq.x-15,objectcoordsortobjectobje

48、ctnameipos.iseq.y-30,strnum);/對(duì)象istrname.format(%d,sortobjectobjectname.iname); dc.textout(objectcoordsortobjectobjectname.iseq.x-5,objectcoordsortobjectobjectname.iseq.y-8,strname);if(sortobjectobjectname.inumber1000)strnum.format( %d,sortobjectobjectname.inumber);elsestrnum.format(%d,sortobjectobj

49、ectname.inumber); dc.textout(objectcoordsortobjectobjectname.iseq.x-15,objectcoordsortobjectobjectname.iseq.y-30,strnum);/延遲1秒進(jìn)行下一次排序以便將排序過程顯示為動(dòng)畫sleep(1000); 下面是我們追蹤所得的一次選擇排序的軌跡：5919 280 1617 4375 332 1467 158 9599 342 496 158 280 1617 4375 332 1467 5919 9599 342 496 158 280 332 4375 1617 1467 5919

50、9599 342 496 158 280 332 342 1617 1467 5919 9599 4375 496 158 280 332 342 496 1467 5919 9599 4375 1617 158 280 332 342 496 1467 1617 9599 4375 5919 158 280 332 342 496 1467 1617 4375 9599 5919 158 280 332 342 496 1467 1617 4375 5919 9599 3.6 各種排序算法小結(jié)3.6.1 冒泡排序冒泡排序的名字來源于其工作方式，在這種排序算法中，較小的數(shù)一個(gè)一個(gè)往水面上“冒”，最終所有數(shù)均變成了由小到大排列。在冒泡排序算法中我們要對(duì)待排序的對(duì)象序列進(jìn)行若干遍處理，處理的過程是：自底向上