【正文】 to demonstrate on the same issues in different algorithm efficiency in the enormous difference. The system uses Visual C ++ 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 Algorithm, 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 dynamic presentation. Its purpose is that enable us to use puters to handle the increasingly large scale data problems, to know what kind of algorithm is suitable for the current system. Key words: Visual C ++ 。 系統(tǒng)開發(fā)的相關(guān)技術(shù) 本系統(tǒng)利用 Visual C++ 作為開發(fā)平臺(tái)，利用它的可視化界面，在其MFC 環(huán)境下開發(fā)的一個(gè)演示三種不同排序算法，利用畫刷畫出三種不同的排序算法在排列隨即產(chǎn)生的 070 個(gè)數(shù)的過程，并且能夠?qū)Ρ冗@三種排序算法在相同的條件下，排序速率的快慢 。 第 2 頁 共 21 頁 2 系統(tǒng)需求及分析 系統(tǒng)需求 本系統(tǒng)的 硬件環(huán)境： CPU AMD 2800+，內(nèi)存 512M 以上，硬盤 80G 以上。先將第一個(gè)記錄與第二個(gè)記錄比較，然后是第二個(gè)與第三個(gè)比較，直到倒數(shù)第二個(gè)與最后一個(gè)記錄。 （ 2）再次重復(fù)（ 1），直到相鄰兩數(shù)之間不再發(fā)生交換為止。 （ 4）、重復(fù)此算法，但每重復(fù)一次，進(jìn)行比較的數(shù)列范圍就向后移動(dòng) 一個(gè)位置。 然后將所有小于它的數(shù)據(jù)放在它前面，所有大于它的數(shù)放在它后面，這個(gè)過程就稱為一趟快速排序。 由于開啟多線程時(shí)，使用的都是全局函數(shù)，想要獲得當(dāng)前視圖類中的數(shù)據(jù)，并實(shí)時(shí)更新試圖的顯示，就必須獲取當(dāng)前試圖對(duì)象。i++) { tag=0。 tag++。iN。 AfxBeginThread(ThreadSortBubble,GetSafeHwnd())。i++) { =170。 } 動(dòng)態(tài)演示選擇算法模塊設(shè)計(jì) 表 44 為工程添加 IDR_MAINFRAME的菜單選項(xiàng) ID 說明文字 功能描述 IDC_SORT_SELECT 選擇法排序 選擇法排序 表 45 打開類向?qū)В?Class Wizard）對(duì)話框向視圖類添加響應(yīng)函數(shù) Object ID Messages Messages 的描述 函數(shù)名 IDC_SORT_SELECT COMMAND 選擇該菜單 OnSortSelect 表 46 通過類查看（ ClassView）選項(xiàng)卡，向視圖類添加成員變量 變量類型 變量名 功能描述 int m_SortSelect[N] 記錄關(guān)鍵字 CRect m_SortSelectRect 動(dòng)態(tài)演示矩形范圍 BOOL IsSortSelect TRUE 表示進(jìn)行選擇排序 在 頭文件，聲明選擇排序的全局函數(shù)： UINT ThreadSortSelect(LPVOID lp)。jN。 } Sleep(DELAY)。 pView=this。 CTtDoc* pDoc = GetDocument()。 =+1。 第 14 頁 共 21 頁 在 構(gòu)建文件中添加實(shí)現(xiàn)快速排序算法的函數(shù)：ThreadSortSelect 和 QuickSort,代碼為： void QuickSort(int * data,int low,int high) { int i=low,j=high。 data[j]=key。 第 15 頁 共 21 頁 data[j]=key。 Sleep(DELAY)。 pView=this。 CTtDoc* pDoc = GetDocument()。 =+1。 OnSortSelect1()。 （ 3）選擇“快速法排序”時(shí)，可以看見整個(gè)序列在經(jīng)過 i=j 的過程后，被分成了 2 個(gè)子序列，再排列兩個(gè)子序列后完成排序，這個(gè)也驗(yàn)證了快速排序算法的思想。 [3] 數(shù)據(jù)結(jié)構(gòu)和算法 [OL].中國 *源碼 , [4] 侯俊杰 .深入淺出 MFC（第 2版） [M].武漢 ：華中科技大學(xué)出版社 ,20205。 關(guān)于學(xué)位論文使用權(quán)和研究成果知識(shí)產(chǎn)權(quán)的說明： 本人完全了解成都信息工程學(xué)院有關(guān)保管使用學(xué)位論文的規(guī)定，其中包括： （ 1）學(xué)校有權(quán)保管并向有關(guān)部門遞交學(xué)位論文的原件與復(fù)印件。本系統(tǒng)是為了演示在同一問題上，不同的算法在效率上存在的巨大差異。因此，利用計(jì)算機(jī)的高速運(yùn)用和計(jì)算能力，編寫出一種合適的排序軟件，能十分快捷的給我們?cè)谛畔⒔涣骱筒樵儙肀憷Ｒ虼宋覀儽仨毟鶕?jù)需要處理數(shù)據(jù)的特點(diǎn)來選擇合適的算法。而且本系統(tǒng)在開發(fā)過程中，能夠用鼠標(biāo)點(diǎn)擊按鈕和拖放圖形化的對(duì)象，修改他們的屬性和行為過程。即把 A[1]和 A[2]比較，對(duì)比完后把 A[2]和 A[3]進(jìn)行比較， ?? 直到 A[N1]和 A[N]比較完為止。算法的步驟如下： （ 1）、先從 A[1]開始向后檢查，檢查出在 A[1]后面的最小數(shù)的位子，我們?cè)O(shè)此位子為 A[P]。 基準(zhǔn)對(duì)象則排在這兩個(gè)子序列中間。在 n 個(gè)元素的序列中，對(duì)一個(gè)對(duì)象定位所需時(shí)間為 O(n)。 算法的步驟如下： （ 1）、設(shè)置兩個(gè)變量 int=i， j，在排序開始的時(shí)候， i=1,j=N； （ 2）、以第一個(gè)數(shù)據(jù)為關(guān)鍵數(shù)據(jù)，定義為 key，即 key=A[1]； （ 3）、從變量 j 向前搜索，即由右至左的搜索 (j:=j1)，找到小于 key 的數(shù)據(jù)，兩者交換； （ 4）、從變量 i 向后搜索，即由左至右的搜索 (i:=i+1)，找到大于 key 的數(shù)據(jù)，兩者交換； （ 5）、重復(fù)排序步驟（ 3）和（ 4），直到 i=j。即第二遍比較時(shí)范圍就從第 2 個(gè)數(shù)一直到第 N 個(gè)數(shù)，在此范圍內(nèi)找最小的數(shù)的位置 P，然后把 A[P]與 A[2]對(duì)調(diào)，這樣從第 2個(gè)數(shù)開始到第 N 個(gè)數(shù)中最小數(shù)就在 A[2]中了，第三遍就從第 3個(gè)數(shù)到第 N個(gè)數(shù)中去找最小的數(shù)，再把 A[P]與 A[3]對(duì)調(diào)??此過程重復(fù) N1 次后，就把 A 數(shù)組中 N 個(gè)數(shù)按從小到大的順序排好 了。 例如：一組待排序數(shù)列為： 圖 31 待排序組 根據(jù)算法思路（ 1）第一次對(duì)比后無變化； 根據(jù)算法思路（ 1）第二次對(duì)比發(fā)生變化：由于 A[2]=8 A[3]=5,所以兩者交換 圖 32 第一次交換 根據(jù)算法思路（ 1）第三次對(duì)比發(fā)生變化：由于 A[3]=8 A[4]=4,所以兩者交換 圖 33第二次交換 根據(jù)算法思路（ 1）第四次對(duì)比無變化； 根據(jù)算法思路（ 1）第五次對(duì)比發(fā)生變化：由于 A[5]=9 A[6]=7，所有兩者交換 圖 34第三次交換 到此第一輪的排序結(jié)束，根據(jù)算法思路（ 2），重新對(duì)以交換排列后的數(shù)列6 5 4 8 7 9 6 5 4 8 9 7 6 5 8 4 9 7 6 8 5 4 9 7 第 4 頁 共 21 頁 進(jìn)行排序直到?jīng)]有變化為止，生成最后的序列： 圖 35最后有序序列 分析冒泡排序法的效率，若記錄一開始就是從大到小排列，則一次循環(huán)就能完成排序；若記錄是“ 逆序”排列的，即是沖小到大的排列，則需 n1 次循環(huán)（ n為需要排序的記錄總數(shù)），共 n(n1)/2 次比較和交換。比較一輪結(jié)束之后，關(guān)鍵字大的記錄均向前移動(dòng)。 本系統(tǒng)的軟件環(huán)境：操作系統(tǒng) Windows XP,Visual C++ 中文版。運(yùn)用 VC 編程語言，把一個(gè)程序中的算法和程序框架有效的結(jié)合起來，并且實(shí)現(xiàn)排序算 法的動(dòng)態(tài)演示。 Sorting Algorithm。 （ 5）學(xué)?？梢怨紝W(xué)位論文的 全部或部分內(nèi)容（保密學(xué)位論文在解密后遵守此規(guī)定）。 第 20 頁 共 21 頁 致 謝 本文是在郭濤和王永麗老師的熱情關(guān)心和指導(dǎo)下完成的，他們淵博的知識(shí)和嚴(yán)謹(jǐn)?shù)闹螌W(xué)作風(fēng)使我受益匪淺，對(duì)順利完成本系統(tǒng)起到了極大的作用。由于冒泡算法記錄的交換次數(shù)最多，所以它排序的速率最慢；選擇算法不用記錄太多的交換次數(shù)，所以他的效率比冒泡算法快一些；快速算法比上面兩種排序記錄 和比較次數(shù)都大大縮小了很多，所以它的效率是最高的，排序的速度是最快的。 圖 49 快速排序結(jié)束 （ 3）第二個(gè)排序 —— 選擇排序完畢。BlueBrush)。// for(i=0。i++) { m_SortQuick[i]=(int)((double)rand()*(double)RAND_MAX)。 srand((unsigned)time(NULL))。 QuickSort(data,i+1,high)。 Sleep(DELAY1)。 Sleep(DELAY1)。BlueBrush)。 for(i=0。i++) { m_SortSelect[i]=(int)((double)rand()*(double)RAND_MAX)。 srand((unsigned)time(NULL))。 } Sleep(DELAY)。 for(i=0。 pDCFillRect(amp。 if(IsSortBubble) { CBrush BlueBrush(RGB(0,255,0))。 } 為了讓大家看清楚排序之間對(duì)比和交換的過程，修改響應(yīng)函數(shù)“ OnSortBubble” ,產(chǎn)生 070隨即整數(shù)來進(jìn)行排序： void CTtView::OnSortBubble() { for(int i=0。 return 0。 data[j]=data[j1]。 int tag。以“ 50”為數(shù)軸，把原序列分成了兩子序列，即： low{28 39 14},high{76 98 66},再遞歸的方法分別對(duì)前子表 low 和后子表 high 進(jìn)行類似的快速排序，從而完成所有數(shù)據(jù)序列的快速排序，最后把原來這個(gè)無序的數(shù)據(jù)序列排列成為一組有序的序列： 圖 316最終序列 分析快速排序算法的效率，如果每次劃分對(duì)一個(gè)對(duì)象定位后，該對(duì)象的左側(cè)子序列與右側(cè)子序列的長度相同，則下一步將是對(duì)兩個(gè)長度減 半的子序列進(jìn)行排序，這是最理想的情況。因此選擇排序算法的復(fù)雜度為 O(n n). 快速算法及思想 快速排序算法的基本思想：采用分而治之的辦法對(duì)一個(gè)表進(jìn)行排序，任取待排序?qū)ο笮蛄兄械哪硞€(gè)對(duì)象 （例如取第一個(gè)對(duì)象）作為基準(zhǔn)，按照該對(duì)象的關(guān)鍵碼大小，將整個(gè)對(duì)象序列劃分為左右兩個(gè)子表－ low 和 high： 4 5 6 6 7 8 9 4 5 8 6 9 7 4 8 5 6 9 7 6 8 5 4 9 7 不動(dòng) 第 6 頁 共 21 頁 （ 1）左側(cè)子序列 low 中所有對(duì)象的關(guān)鍵碼都小于或等于基準(zhǔn)對(duì)象的關(guān)鍵碼； （ 2）右側(cè)子序列 high 中所有對(duì)象的關(guān)鍵碼都大于或等于基準(zhǔn)對(duì)象的關(guān)鍵碼。 我們選擇一種把最小的數(shù)放在第一個(gè)位置上的選擇排序算法，其思想是先并不急于調(diào)換位置，先從第一個(gè)數(shù)開始逐個(gè)向后掃描整個(gè)序列，看哪個(gè)數(shù)最小就記下該數(shù)所在的位置，等一趟掃描完畢，再把第一個(gè)數(shù)和在他后面最小對(duì)調(diào)，這時(shí)此無序序列中最小的數(shù)據(jù)就換到了最前面的位置。 算法的步驟如下： （ 1）假設(shè)要排序的數(shù)列為 A[1]?? A[N]，我們把相鄰的兩個(gè)數(shù)兩兩進(jìn)行比較。排序 算法本來就是一種抽象的邏輯功能，想要直觀的把它演示出來，選擇利用 Visual C++ 的可視化編程是非常明智的。 排序的方法有很多種，但是沒有一種排序算法是通用的，即在任何情況下都能保持最快的排序速度。 系統(tǒng)開發(fā)的意義 在現(xiàn)代信息發(fā)達(dá)的今天，面對(duì)接受到大量的無序的信息，沒有一個(gè)規(guī)則來編排和查詢，會(huì)給我們的工作和信息交流帶來十分的不便。當(dāng)然，高效的運(yùn)算速度并不代表無限快，在有限的資源空間里，要大大提高運(yùn)算處理數(shù)據(jù)的速率，就需要我們使用那些在時(shí)間和空間上體現(xiàn)出高效的算法。 Sorting Algorithm。運(yùn)用 VC 編程語言，把一個(gè)程序中的算法和程序框架有效的結(jié)合起來，并且實(shí)現(xiàn)排序算法的動(dòng)態(tài)演示。 本系統(tǒng)的軟件環(huán)境：操作系統(tǒng) Windows XP,Visual C++ 中文版。比較一輪結(jié)束之后，關(guān)鍵字大的記錄均向前移動(dòng)。 例如：一組待排序數(shù)列為： 圖 31 待排序組