1、多種排序算法動(dòng)態(tài)演示軟件的設(shè)計(jì)與開(kāi)發(fā)摘要隨著計(jì)算機(jī)科學(xué)技術(shù)的不斷提高和發(fā)展，其強(qiáng)大的運(yùn)算功能已經(jīng)逐漸融入 人類(lèi)社會(huì)的各個(gè)領(lǐng)域，并且在各個(gè)領(lǐng)域中發(fā)揮越來(lái)越重要的作用。當(dāng)然，高效 的運(yùn)算速度并不代表無(wú)限快，在有限的資源空間里，要大大提高運(yùn)算處理數(shù)據(jù) 的速率，就需要我們使用那些在時(shí)間和空間上體現(xiàn)出高效的算法。本系統(tǒng)是為 了演示在同一問(wèn)題上，不同的算法在效率上存在的巨大差異。本系統(tǒng)采用Visual C+ 6.0中文版為開(kāi)發(fā)工具，實(shí)現(xiàn)三種不同排序算法，即：冒泡排序算法、選 擇排序算法和快速排序算法，以及這三種排序?qū)ν粏?wèn)題的處理并且以圖形的 形式給出快慢比較，實(shí)現(xiàn)排序算法的動(dòng)態(tài)演示。其目的是為了讓我們?cè)?/p>

2、使用計(jì) 算機(jī)處理規(guī)模越來(lái)越大的數(shù)據(jù)問(wèn)題上，能夠清楚什么樣的算法適合當(dāng)前的處理 系統(tǒng)。關(guān)鍵詞：Visual C+ ;排序算法；動(dòng)態(tài)演示The Design and Development of Dynamic SortingAlgorithm DemoAbstractWith computer scie nee and tech no logy improveme nt and developme nt, its powerful computing has gradually integrate into human society in various fields, and play an

3、 increasingly important role. Of course, efficient computational speed does not mean unlimited fast, and the limited resources of space, Operators must sig nifica ntly improve process ing speed, we n eed to use the time and space reflects efficie nt algorithms. The system is to dem on strate on the

4、same issues in differe nt algorithm efficiency in the enormous differenee. The system uses Visual C +6.0 for the development of the Chinese version of tools to achieve three different sorting algorithms, namely : The Bubble Sorting Algorithm, The Select Sorting Algorithm and The Quick Sorting Algori

5、thm, and three ranking on the same issue to deal with and the graphics are presented in the form of speed, Sorting Algorithm to achieve the dyn amic prese ntati on .Its purpose is that en able us to use computers to han dle the increasingly large scale data problems, to know what kind of algorithm i

6、s suitable for the curre nt system.Key words： Visual C + ; Sort ing Algorithm; Dyn amic Dem on strati on目錄論文總頁(yè)數(shù)：21頁(yè) TOC o 1-5 h z 弓I言 1 HYPERLINK l bookmark8 o Current Document 系統(tǒng)背景 1 HYPERLINK l bookmark10 o Current Document 系統(tǒng)開(kāi)發(fā)的意義 1 HYPERLINK l bookmark12 o Current Document 系統(tǒng)開(kāi)發(fā)的相關(guān)技術(shù) 1 HYPERLINK

7、l bookmark14 o Current Document 系統(tǒng)開(kāi)發(fā)的相關(guān)概念 1 HYPERLINK l bookmark16 o Current Document 系統(tǒng)需求及分析 2 HYPERLINK l bookmark18 o Current Document 系統(tǒng)需求 2 HYPERLINK l bookmark20 o Current Document 系統(tǒng)開(kāi)發(fā)環(huán)境選擇 2 HYPERLINK l bookmark22 o Current Document 系統(tǒng)的總體規(guī)劃 2 HYPERLINK l bookmark24 o Current Document 系統(tǒng)設(shè)計(jì)思想 2

8、 HYPERLINK l bookmark26 o Current Document 冒泡算法及思想 2 HYPERLINK l bookmark34 o Current Document 選擇算法及思想 4 HYPERLINK l bookmark40 o Current Document 快速算法及思想 5 HYPERLINK l bookmark42 o Current Document 詳細(xì)設(shè)計(jì) 8 HYPERLINK l bookmark44 o Current Document 系統(tǒng)的文件的組織 8 HYPERLINK l bookmark46 o Current Document

9、 動(dòng)態(tài)演示冒泡算法模塊設(shè)計(jì) 8 HYPERLINK l bookmark48 o Current Document 動(dòng)態(tài)演示選擇算法模塊設(shè)計(jì) 11 HYPERLINK l bookmark50 o Current Document 動(dòng)態(tài)演示快速算法模塊設(shè)計(jì) 13 HYPERLINK l bookmark52 o Current Document 同時(shí)比較三種算法模塊設(shè)計(jì) 16 HYPERLINK l bookmark54 o Current Document 系統(tǒng)的測(cè)試 16 HYPERLINK l bookmark66 o Current Document 系統(tǒng)的特點(diǎn) 18 HYPERLIN

10、K l bookmark68 o Current Document 結(jié)論 19 HYPERLINK l bookmark70 o Current Document 參考文獻(xiàn) 19 HYPERLINK l bookmark72 o Current Document 致謝 20 HYPERLINK l bookmark74 o Current Document 聲明 21第 頁(yè)共21頁(yè)1 引言1.1系統(tǒng)背景由于排序在計(jì)算機(jī)圖形、計(jì)算機(jī)輔助設(shè)計(jì)、機(jī)器人、模式識(shí)別、基因排序 工程及統(tǒng)計(jì)學(xué)等領(lǐng)域具有廣泛應(yīng)用，所以對(duì)排序的研究既有理論上的重要意義， 又有實(shí)際應(yīng)用價(jià)值。再加上現(xiàn)在信息產(chǎn)業(yè)的迅速發(fā)展，信息的流

11、通量越來(lái)越大, 如此龐大并且雜亂無(wú)章的信息數(shù)據(jù)十分難以管理和查詢(xún)，就更加需要一種十分 快捷而有效的編排手段來(lái)整理這些數(shù)據(jù)信息，讓我們的工作效率得以提高。1.2系統(tǒng)開(kāi)發(fā)的意義在現(xiàn)代信息發(fā)達(dá)的今天，面對(duì)接受到大量的無(wú)序的信息，沒(méi)有一個(gè)規(guī)則來(lái) 編排和查詢(xún)，會(huì)給我們的工作和信息交流帶來(lái)十分的不便。因此，利用計(jì)算機(jī) 的高速運(yùn)用和計(jì)算能力，編寫(xiě)出一種合適的排序軟件，能十分快捷的給我們?cè)?信息交流和查詢(xún)帶來(lái)便利。例如在互聯(lián)網(wǎng)上為了使人們能夠快速的訪(fǎng)問(wèn)和檢索 大量的信息，人們會(huì)運(yùn)用許多快速并且優(yōu)秀的算法對(duì)這些數(shù)據(jù)進(jìn)行管理和操縱。 優(yōu)秀的算法還能幫助我們?cè)诨ヂ?lián)網(wǎng)上快速找到最好的發(fā)送數(shù)據(jù)路線(xiàn)，以及怎么 用搜索引擎

12、來(lái)快速地找到信息所在的頁(yè)面。1.3系統(tǒng)開(kāi)發(fā)的相關(guān)技術(shù)本系統(tǒng)利用Visual C+ 6.0 作為開(kāi)發(fā)平臺(tái)，利用它的可視化界面，在其 MFC環(huán)境下開(kāi)發(fā)的一個(gè)演示三種不同排序算法，利用畫(huà)刷畫(huà)出三種不同的排序 算法在排列隨即產(chǎn)生的0-70個(gè)數(shù)的過(guò)程，并且能夠?qū)Ρ冗@三種排序算法在相同 的條件下，排序速率的快慢。運(yùn)用 VC編程語(yǔ)言，把一個(gè)程序中的算法和程序框 架有效的結(jié)合起來(lái)，并且實(shí)現(xiàn)排序算法的動(dòng)態(tài)演示。1.4系統(tǒng)開(kāi)發(fā)的相關(guān)概念首先我們要了解排序到底是什么？它的主要功能和目的是什么？簡(jiǎn)單的 說(shuō)，排序是利用一種算法，將一個(gè)無(wú)規(guī)則的序列排成一個(gè)有序序列的過(guò)程。而 算法則是以一組值或者一個(gè)值的集合作為輸入，經(jīng)過(guò)

13、一系列計(jì)算得到的一組值 作為輸出的過(guò)程，即是指那一系列將輸入轉(zhuǎn)化為輸出的計(jì)算過(guò)程。排序的方法有很多種，但是沒(méi)有一種排序算法是通用的，即在任何情況下 都能保持最快的排序速度。因此我們必須根據(jù)需要處理數(shù)據(jù)的特點(diǎn)來(lái)選擇合適 的算法。在排序的過(guò)程中，我們一般需要用到的兩個(gè)基本操作步驟是：比較兩 個(gè)關(guān)鍵字的大小和將記錄從一個(gè)位子移至另一個(gè)位子，即比較和交換。本系統(tǒng) 設(shè)定的情況為，記錄關(guān)鍵字都為整數(shù)，排序的結(jié)果是從大到小的排列，用到的 三種排序算法為：冒泡排序法、選擇排序法、快速排序法。2系統(tǒng)需求及分析2.1系統(tǒng)需求本系統(tǒng)的硬件環(huán)境：CPU AMD 2800+內(nèi)存512M以上，硬盤(pán)80G以上。 本系統(tǒng)的軟

14、件環(huán)境：操作系統(tǒng) Win dows XP,Visual C+ 6.0 中文版。2.2系統(tǒng)開(kāi)發(fā)環(huán)境選擇本系統(tǒng)運(yùn)用的是Visual C+6.0中文版，它是微軟公司開(kāi)發(fā)出的一種集成 開(kāi)發(fā)環(huán)境，它擁有良好的可視化界面，它用來(lái)在Windows環(huán)境下開(kāi)發(fā)應(yīng)用程序， 是一種功能強(qiáng)大、行之有效的可視化編程工具。在Visual C+6.0中能夠進(jìn)行多種操作，它的特點(diǎn)就是能夠把原來(lái)抽象的數(shù)字、表格、功能邏輯等用直觀的 圖形、圖象的形式表現(xiàn)出來(lái)。排序算法本來(lái)就是一種抽象的邏輯功能，想要直 觀的把它演示出來(lái)，選擇利用 Visual C+6.0的可視化編程是非常明智的。而 且本系統(tǒng)在開(kāi)發(fā)過(guò)程中，能夠用鼠標(biāo)點(diǎn)擊按鈕和拖放

15、圖形化的對(duì)象，修改他們 的屬性和行為過(guò)程。這種可視化的編程方法簡(jiǎn)單、易學(xué)、易用，可以大大提高 我們的工作效率。2.3系統(tǒng)的總體規(guī)劃本系統(tǒng)的總體結(jié)構(gòu)如圖2-1所示：圖2-1系統(tǒng)總體結(jié)構(gòu)3系統(tǒng)設(shè)計(jì)思想3.1冒泡算法及思想冒泡排序算法的基本思想：冒泡法的原理很簡(jiǎn)單，基本思想就是比較相臨 的兩個(gè)記錄的關(guān)鍵字，若前者比后者小則交換，若前者比后者大則保持不變。 先將第一個(gè)記錄與第二個(gè)記錄比較，然后是第二個(gè)與第三個(gè)比較，直到倒數(shù)第 二個(gè)與最后一個(gè)記錄。比較一輪結(jié)束之后，關(guān)鍵字大的記錄均向前移動(dòng)。然后 開(kāi)始新一輪的比較，知道一輪比較下來(lái)，不再有記錄的交換發(fā)生為止。整個(gè)過(guò)程就有點(diǎn)象水中的氣泡上升的過(guò)程，輕的往上

16、浮，重的向下沉，這個(gè)算法的名 字也就由此得來(lái)。算法的步驟如下：（1）假設(shè)要排序的數(shù)列為 A1 , AN，我們把相鄰的兩個(gè)數(shù)兩兩進(jìn)行比較。即把A1和A2比較，對(duì)比完后把A2和A3進(jìn)行比較，”直到 AN-1 和AN比較完為止。在相鄰的兩個(gè)數(shù)兩兩進(jìn)行比較的過(guò)程中，如果前面的一個(gè) 數(shù)比后面一個(gè)數(shù)大，則把這兩鄰的兩個(gè)數(shù)交換，也就是說(shuō)，我們把較小的數(shù)放 在前面，把較大的數(shù)調(diào)到后面。即，如果在一次比較中，如果A1比A2大的情況下，把A1和A2交換，”以此類(lèi)推，直到一輪AN-1和AN比較完。（2）再次重復(fù)（1），直到相鄰兩數(shù)之間不再發(fā)生交換為止。例如：一組待排序數(shù)列為：E E E E E E圖3-1待排序組根

17、據(jù)算法思路（1）第一次對(duì)比后無(wú)變化；A2=8 A3=5, 所以?xún)筛鶕?jù)算法思路（1）第二次對(duì)比發(fā)生變化：由于者交換58圖3-2第一次交換根據(jù)算法思路（1）第三次對(duì)比發(fā)生變化：由于A3=8 A4=4, 所以?xún)烧呓粨Q圖3-3第二次交換根據(jù)算法思路（1）第四次對(duì)比無(wú)變化；根據(jù)算法思路（1）第五次對(duì)比發(fā)生變化：由于 A 5=9 A6=7 ，所有兩 者交換叵叵E叵FJ圖3-4第三次交換到此第一輪的排序結(jié)束，根據(jù)算法思路（2），重新對(duì)以交換排列后的數(shù)列進(jìn)行排序直到?jīng)]有變化為止，生成最后的序列:E E E E E E圖3-5最后有序序列分析冒泡排序法的效率，若記錄一開(kāi)始就是從大到小排列，則一次循環(huán)就 能完成排

18、序；若記錄是“逆序”排列的，即是沖小到大的排列，則需n-1次循環(huán)(n為需要排序的記錄總數(shù))，共n(n-1)/2次比較和交換。算法的負(fù)責(zé)度為03.2選擇算法及思想選擇排序算法的基本思想：每一趟(例如第i趟，i = 0, 1, ,n-2)在后面n-i個(gè)待排序?qū)ο笾羞x出關(guān)鍵碼最小的對(duì)象，作為有序?qū)ο笮蛄械牡趇個(gè)對(duì)象。待到第n-2趟作完，待排序?qū)ο笾皇Ｏ?個(gè)，就不用再選了。我們選擇一種把最小的數(shù)放在第一個(gè)位置上的選擇排序算法，其思想是先 并不急于調(diào)換位置，先從第一個(gè)數(shù)開(kāi)始逐個(gè)向后掃描整個(gè)序列，看哪個(gè)數(shù)最小 就記下該數(shù)所在的位置，等一趟掃描完畢，再把第一個(gè)數(shù)和在他后面最小對(duì)調(diào)， 這時(shí)此無(wú)序序列中最小的數(shù)

19、據(jù)就換到了最前面的位置。算法的步驟如下：、先從A1開(kāi)始向后檢查，檢查出在 A1后面的最小數(shù)的位子，我 們?cè)O(shè)此位子為AP。、依次把AP和AN (AN從1變化到N)進(jìn)行比較，每次比較時(shí)，若AN的數(shù)比AP中的數(shù)小，則把N的值賦給P,使P總是指向當(dāng)前所掃描過(guò) 的最小數(shù)的位置，也就是說(shuō) AP總是等于所有掃描過(guò)的數(shù)最小的那個(gè)數(shù)。在依 次比較后，P就指向N個(gè)數(shù)中最小的數(shù)所在位置，即 AP就是N個(gè)數(shù)中最小的那個(gè)數(shù)；、把AP和A1的數(shù)對(duì)調(diào)，那么最小的數(shù)就在 A1中去了，也就是 在最前面了。、重復(fù)此算法，但每重復(fù)一次，進(jìn)行比較的數(shù)列范圍就向后移動(dòng)一個(gè) 位置。即第二遍比較時(shí)范圍就從第 2個(gè)數(shù)一直到第N個(gè)數(shù)，在此范圍

20、內(nèi)找最小 的數(shù)的位置P,然后把AP與A2對(duì)調(diào)，這樣從第2個(gè)數(shù)開(kāi)始到第N個(gè)數(shù)中最 小數(shù)就在A2中了，第三遍就從第3個(gè)數(shù)到第N個(gè)數(shù)中去找最小的數(shù)，再把AP 與A3對(duì)調(diào),此過(guò)程重復(fù) N-1次后，就把A數(shù)組中N個(gè)數(shù)按從小到大的順序 排好了。例如，一組待排數(shù)據(jù)為：E E E E E E圖3-6待排序列根據(jù)選擇排序算法思路（1）,從A1=6向后檢查，發(fā)現(xiàn)最小的數(shù)為A4=4 ; 根據(jù)選擇排序算法思路（2），把A1和A4進(jìn)行比較，得出：A1=6 A4=4，所以把A4和A1對(duì)調(diào)，得到新的序列：4856圖3-7第一次交換根據(jù)選擇排序算法思路（3）:即從A2=8向后檢查，從 A3-A6從找到最小的數(shù) A3=5，把A

21、2=8 和A3=5進(jìn)行比較，得出：A2=8 A3=5 ，所以把A2和A3對(duì)調(diào)0 0 0 0 0 0圖3-8第二次交換重復(fù)選擇排序算法思路（4）,直到上面的排序工作不再有交換為止，得到最后序列為：叵叵叵E叵叵圖3-9最終序列分析選擇排序算法效率，它實(shí)現(xiàn)的方式是：令 i從1到n-1，進(jìn)行n-1次 選擇操作。在選擇排序算法的過(guò)程中，所需進(jìn)行記錄移動(dòng)的造作次數(shù)比較少， 但是，無(wú)論記錄的初始排列如何，所需進(jìn)行記錄關(guān)鍵字間的比較次數(shù)均為 n（n-1）/2。因此選擇排序算法的復(fù)雜度為 0（n x n）.3.3快速算法及思想快速排序算法的基本思想：采用分而治之的辦法對(duì)一個(gè)表進(jìn)行排序，任取 待排序?qū)ο笮蛄兄械哪?/p>

22、個(gè)對(duì)象（例如取第一個(gè)對(duì)象）作為基準(zhǔn)，按照該對(duì)象的 關(guān)鍵碼大小，將整個(gè)對(duì)象序列劃分為左右兩個(gè)子表 low和high :（1）左側(cè)子序列l(wèi)ow中所有對(duì)象的關(guān)鍵碼都小于或等于基準(zhǔn)對(duì)象的關(guān)鍵 碼；（2）右側(cè)子序列high中所有對(duì)象的關(guān)鍵碼都大于或等于基準(zhǔn)對(duì)象的關(guān)鍵 碼?；鶞?zhǔn)對(duì)象則排在這兩個(gè)子序列中間。然后再按此方法對(duì)low和high兩部分 數(shù)據(jù)分別進(jìn)行快速排序，其整個(gè)過(guò)程可以遞歸進(jìn)行，從而使整個(gè)數(shù)列變成有序 序列。假設(shè)要排序的數(shù)列為A1 ,AN,我們首先要取一個(gè)數(shù)據(jù)作為關(guān)鍵數(shù)據(jù)，一般情況下都是取第一個(gè)數(shù)據(jù)為關(guān)鍵數(shù)據(jù)。然后將所有小于它的數(shù)據(jù)放在它前 面，所有大于它的數(shù)放在它后面，這個(gè)過(guò)程就稱(chēng)為一趟快速排

23、序。算法的步驟 如下：（1） 、設(shè)置兩個(gè)變量int=i ，j，在排序開(kāi)始的時(shí)候，i=1,j=N ；（2）、以第一個(gè)數(shù)據(jù)為關(guān)鍵數(shù)據(jù)，定義為 key，即key=A1；（3） 、從變量j向前搜索，即由右至左的搜索（j:=j-1），找到小于key的 數(shù)據(jù)，兩者交換；（4） 、從變量i向后搜索，即由左至右的搜索（i:=i+1），找到大于key的 數(shù)據(jù)，兩者交換；（5）、重復(fù)排序步驟（3）和（4），直到i=j 0例如，一組待排序數(shù)據(jù)為：（設(shè)初始關(guān)鍵數(shù)據(jù)：key=50）| 50| 39| 66| 98| 76| 14| 28圖3-10待排序列根據(jù)步驟（3）進(jìn)行第一次交換后:（關(guān)鍵數(shù)據(jù)key=50和28發(fā)生交

24、換，此時(shí)j=6 ） 根據(jù)步驟（4）進(jìn)行第二次交換后：圖3-12第二次交換（關(guān)鍵數(shù)據(jù)key=50和66發(fā)生交換，此時(shí)i=4 ）根據(jù)步驟（5）將又一次執(zhí)行算法（3）進(jìn)行第三次交換:圖3-13第三次交換（關(guān)鍵數(shù)據(jù)key=50和14發(fā)生交換，此時(shí)j=5）根據(jù)步驟（5）又將執(zhí)行一次算法（4）進(jìn)行第四次交換:圖3-14第四次交換（關(guān)鍵數(shù)據(jù)key=50和98發(fā)生交換，此時(shí)i=5 ）此時(shí)我們可以看見(jiàn)j=i ，所以此時(shí)結(jié)束此趟快速排序。在經(jīng)過(guò)這趟快速排 序后的結(jié)果是：圖3-15第五次交換即所有大于初始關(guān)鍵數(shù)據(jù)“ 50”的數(shù)據(jù)全在其右邊，所有小于初始關(guān)鍵數(shù) 據(jù)“50”的數(shù)據(jù)全部在其左邊。以“ 50”為數(shù)軸，把原序

25、列分成了兩子序列， 即：low28 39 14,high76 98 66,再遞歸的方法分別對(duì)前子表low和后子表high進(jìn)行類(lèi)似的快速排序，從而完成所有數(shù)據(jù)序列的快速排序，最后把原來(lái)這個(gè)無(wú)序的數(shù)據(jù)序列排列成為一組有序的序列：分析快速排序算法的效率，如果每次劃分對(duì)一個(gè)對(duì)象定位后，該對(duì)象的左 側(cè)子序列與右側(cè)子序列的長(zhǎng)度相同，則下一步將是對(duì)兩個(gè)長(zhǎng)度減半的子序列進(jìn) 行排序，這是最理想的情況。在n個(gè)元素的序列中，對(duì)一個(gè)對(duì)象定位所需時(shí)間為0（n）。若設(shè)t（n）是對(duì)n個(gè)兀素的序列進(jìn)行排序所需的時(shí)間，而且每次對(duì)一個(gè)對(duì)象正確定位后，正好把序列劃分為長(zhǎng)度相等的兩個(gè)子序列，此時(shí)，總的計(jì)算時(shí)間為：T( n) cn +

26、 2 t(n/2 )/ c 是一個(gè)常數(shù)Cn + 2 ( cn/2 + 2t( n/4) ) = 2cn + 4t( n/4)2cn + 4 ( cn/4 +2t( n/8) ) = 3cn + 8t( n/8)J J JCn Iog2n + nt(1) = o(n Iog2n )因此該算法的算法復(fù)雜度為0(n Iog2n )4詳細(xì)設(shè)計(jì)4.1系統(tǒng)的文件的組織本系統(tǒng)所含文件的組織如圖4-1所示：圖4-1文件的組織4.2動(dòng)態(tài)演示冒泡算法模塊設(shè)計(jì)首先，本系統(tǒng)是在 Visual C+ 6.0 中文版下MFC環(huán)境下，設(shè)置的“ MFCAppWizard(exe) ”工程，工程名為：“tt ”。相關(guān)的ID如表

27、4_1,4_2所示表4-1為工程添加IDR MAINFRAM的菜單選項(xiàng)ID說(shuō)明文字功能描述IDC_SORT_BUBBLE冒泡法排序冒泡法排序表4-2打開(kāi)類(lèi)向?qū)?Class Wizard )對(duì)話(huà)框向視圖類(lèi)添加響應(yīng)函數(shù)Object IDMessagesMessages的描述函數(shù)名IDC_SORT_BUBBLECOMMAND選擇該菜單OnSortBubble表4-3通過(guò)類(lèi)查看(ClassView )選項(xiàng)卡，向視圖類(lèi)添加成員變量變量類(lèi)型變量名功能描述intm_SortBubbleN記錄關(guān)鍵字CRectm_SortBubbleRect動(dòng)態(tài)演示矩形范圍BOOLIsSortBubbleTRUE表示進(jìn)行冒泡排

28、序打開(kāi)ttView.h頭文件，在文件開(kāi)始部分定義兩個(gè)常量:設(shè)定排序的記錄次數(shù)每次交換操作所耗每次比較操作所耗的時(shí)間 TOC o 1-5 h z #defi ne N 70II#defi ne DELAY 3II#defi ne DELAY1 1II并在其下聲明冒泡排序的全局函數(shù)：UINT ThreadSortBubble(LPVOID Ip);由于開(kāi)啟多線(xiàn)程時(shí)，使用的都是全局函數(shù)，想要獲得當(dāng)前視圖類(lèi)中的數(shù)據(jù)， 并實(shí)時(shí)更新試圖的顯示，就必須獲取當(dāng)前試圖對(duì)象。所以本系統(tǒng)要定義一個(gè)全 局指針，打開(kāi)ttView.cpp構(gòu)建函數(shù)中加入語(yǔ)句“ CTtView *pView ”用來(lái)獲取當(dāng) 前視圖。然后，系統(tǒng)

29、在ttView.cpp 構(gòu)建文件中添加實(shí)現(xiàn)冒泡排序算法的函數(shù):ThreadSortBubble,代碼為:UINT ThreadSortBubbIe(LPVOID Ip) int * data;int i,j,key;int tag;data=pView-m_SortBubbIe; for(i=0;ii;j-)if(datajdataj-1)key=dataj; dataj=dataj-1; dataj-1=key;Sleep(DELAY);pView-l nv alidate(TRUE); tag+;Sleep(DELAY1);if(tag=0) break;pView-l nv alidat

30、e(TRUE);return 0;在類(lèi)中查看(Class View)選項(xiàng)，打開(kāi)視圖類(lèi)CTtView，在其中修改構(gòu) 建函數(shù)，實(shí)現(xiàn)變量初始化：CTtView:CTtView()int i;sran d( un sig ned)time(NULL);for(i=0;iN;i+)m_SortBubblei =0;pView=this;IsSortBubble=FALSE;為了讓大家看清楚排序之間對(duì)比和交換的過(guò)程，修改響應(yīng)函數(shù) OnSortBubble ” ,產(chǎn)生0-70隨即整數(shù)來(lái)進(jìn)行排序：void CTtView:O nSortBubble()for(int i=0;iTextOut(250,200,

31、冒泡排序演示);/ for(i=0;iFillRect(&m _SortBubbleRect，&BlueBrush); _BlueBrush.DeleteObject();4.3動(dòng)態(tài)演示選擇算法模塊設(shè)計(jì)表4-4為工程添加IDR MAINFRAM的菜單選項(xiàng)ID說(shuō)明文字功能描述IDC_SORT_SELECT選擇法排序選擇法排序表4-5打開(kāi)類(lèi)向?qū)?Class Wizard )對(duì)話(huà)框向視圖類(lèi)添加響應(yīng)函數(shù)Object IDMessagesMessages的描述函數(shù)名IDC_SORT_SELECTCOMMAND選擇該菜單OnSortSelect表4-6通過(guò)類(lèi)查看(ClassView )選項(xiàng)卡，向視圖類(lèi)添加

32、成員變量變量類(lèi)型變量名功能描述intm_SortSelectN記錄關(guān)鍵字CRectm_SortSelectRect動(dòng)態(tài)演示矩形范圍BOOLIsSortSelectTRUE表示進(jìn)行選擇排序在TtView.h頭文件，聲明選擇排序的全局函數(shù):UINT ThreadSortSelect(LPVOID lp);然后，在TtView.cpp構(gòu)建文件中添加實(shí)現(xiàn)選擇排序算法的函數(shù)：ThreadSortSelect,代碼為：UINT ThreadSortSelect(LPVOID lp)int i,j,key,tmp;int *data;data=pView-m_SortSelect;for(i=0;iN-1;

33、i+) key=i;for(j=i+1;jdatakey)key=j;pView-l nv alidate(TRUE);Sleep(DELAY1);Sleep(DELAY);tmp=datai;datai=datakey;datakey=tmp;Sleep(DELAY);pView-l nvalidate(TRUE);return 0;在類(lèi)中查看(Class View)選項(xiàng)，打開(kāi)視圖類(lèi)CTtView，在其中修改構(gòu) 建函數(shù)，實(shí)現(xiàn)變量初始化：CTtView:CTtView()int i;sran d( un sig ned)time(NULL);for(i=0;iN;i+)m_SortSelect

34、i =0;pView=this;IsSortSelect=FALSE;修改響應(yīng)函數(shù)“ OnSortSelect ” ,產(chǎn)生0-70隨即整數(shù)來(lái)進(jìn)行排序：void CTtView:O nSortSelect()for(int i=0;iTextOut(5O,2OO,選擇排序演示); for(i=0;iFillRect(&m _SortSelectRect,&BlueBrush); _BlueBrush.DeleteObject();4.4動(dòng)態(tài)演示快速算法模塊設(shè)計(jì)表4-7為工程添加IDR MAINFRAM的菜單選項(xiàng)ID說(shuō)明文字功能描述IDC_SORT_QUICK快速法排序快速法排序表4-8打開(kāi)類(lèi)向?qū)?/p>

35、(Class Wizard )對(duì)話(huà)框向視圖類(lèi)添加響應(yīng)函數(shù)Object IDMessagesMessages的描述函數(shù)名IDC_SORT_QUICKCOMMAND快速該菜單OnSortQuick表4-9通過(guò)類(lèi)查看(ClassView )選項(xiàng)卡，向視圖類(lèi)添加成員變量變量類(lèi)型變量名功能描述intm_SortQuickN記錄關(guān)鍵字CRectm_SortQuickRect動(dòng)態(tài)演示矩形范圍BOOLIsSortQuickTRUE表示進(jìn)行選擇排序在TtView.h頭文件，聲明選擇排序的全局函數(shù): UINT ThreadSortQuick(LPVOID lp);void QuickSort(i nt * dat

36、a,i nt s,i nt t);在TtView.cpp 構(gòu)建文件中添加實(shí)現(xiàn)快速排序算法的函數(shù)：ThreadSortSelect 和 Quicksort,代碼為：void QuickSort(i nt * data,i nt low,i nt high)int i=low,j=high;int tmp,key;if(lowvhigh)tmp=datalow;while(ij)while(ij)if(datajl nv alidate(TRUE);while(i=tmp)i+;Sleep(DELAY1);elsebreak;key=datai;datai=dataj;dataj=key;Slee

37、p(DELAY);pView-l nv alidate(TRUE);QuickSort(data,low,i-1);QuickSort(data,i+1,high);UINT ThreadSortQuick(LPVOID lp)int * data;data=pView-m_SortQuick;pView-I nv alidate(TRUE);Sleep(DELAY);QuickSort(data,0,N-1);return 0;打開(kāi)類(lèi)(Class View)中視圖類(lèi)CTtView，在其中修改構(gòu)建函數(shù)，實(shí)現(xiàn)變量初始化：CTtView:CTtView()int i;sran d( un sig

38、ned)time(NULL);for(i=0;iN;i+)m_SortQuicki =0;pView=this;IsSortQuick=FALSE;修改響應(yīng)函數(shù)“ OnSortQuick ” ,產(chǎn)生0-70隨即整數(shù)來(lái)進(jìn)行排序：void CTtView:O nSortQuick()for(int i=0;iTextOut(45O,2OO,快速排序演示);/ for(i=0;iFillRect(&m _SortQuickRect,&BlueBrush); _BlueBrush.DeleteObject();4.5同時(shí)比較三種算法模塊設(shè)計(jì)表4-10 為工程添加IDR MAINFRAM的菜單選項(xiàng)ID說(shuō)

39、明文字功能描述IDC_SORT_ALL同時(shí)比較三種方法同時(shí)進(jìn)行比較表4-11打開(kāi)類(lèi)向?qū)В–lass Wizard ）對(duì)話(huà)框向視圖類(lèi)添加響應(yīng)函數(shù)Object IDMessagesMessages的描述函數(shù)名IDC_SORT_ALLCOMMAND快速該菜單OnSortAll同時(shí)比較這三種排序，就是同時(shí)調(diào)用這三種排序演示線(xiàn)程，修改響應(yīng)函數(shù)On SortAll:void CTtView:O nSortAII()/ TODO: Add your comma nd han dler code hereOn SortBubble1();On SortQuick1();On SortSelect1();4.6

40、系統(tǒng)的測(cè)試每一個(gè)紅色（同時(shí)排序的藍(lán)色）的豎條都代表一個(gè)隨即數(shù)（以下相同）(1)冒泡排序的動(dòng)態(tài)演示開(kāi)始冒泡排序的動(dòng)態(tài)演示結(jié)束冒泡排序演示圖4-3冒泡演示結(jié)束選擇排序的動(dòng)態(tài)演示結(jié)束冒泡排序演示圖4-2冒泡演示開(kāi)始選擇排序的動(dòng)態(tài)演示開(kāi)始選擇排序演示圖4-5選擇演示結(jié)束快速排序的動(dòng)態(tài)演結(jié)束選擇檸序演示圖4-4選擇演示開(kāi)始快速排序的動(dòng)態(tài)演示開(kāi)始快速排序演示快速毎序演示圖4-7快速演示結(jié)束圖4-6快速演示開(kāi)始同時(shí)演示三種排序，比較他們的排序過(guò)程的快慢開(kāi)始序演示II1 IlliIlli lull1 11 llllllllh.圖4-8同時(shí)比較三種排序開(kāi)始第一個(gè)排序快速排序完畢?？焖倥判驒M示選擇護(hù)序廣不圖4-9快速排序結(jié)束第二個(gè)排序一一選擇排序完畢。迭擇樓序演示冒ia推序離示圖4-10選擇排序結(jié)束最后一個(gè)排序一一冒泡排序完畢快速梓序橫示llllllllllllllllimin,.圖4-11冒泡排序結(jié)束4.7系統(tǒng)的特點(diǎn)在運(yùn)行本系統(tǒng)的時(shí)候，選擇不同的菜單選項(xiàng)，能夠清楚的看出各種排序過(guò) 程的變化，例如：選擇“冒泡法排序”時(shí)，可以看見(jiàn)綠色的長(zhǎng)條逐漸向左移動(dòng)，完全驗(yàn) 證了冒泡排序算法的思想。選擇“選擇法排序”時(shí)，可以看見(jiàn)綠色的長(zhǎng)條是被交換到左邊的過(guò)程， 這個(gè)也完全證明了選擇排序算法的思想。選擇“快速法排序”時(shí)，可以看見(jiàn)整個(gè)序列在經(jīng)過(guò) i=j的過(guò)程后，被 分成了 2個(gè)子序列，再排列兩