【導(dǎo)讀】人類社會的各個領(lǐng)域，并且在各個領(lǐng)域中發(fā)揮越來越重要的作用。的速率，就需要我們使用那些在時間和空間上體現(xiàn)出高效的算法。了演示在同一問題上，不同的算法在效率上存在的巨大差異。形式給出快慢比較，實現(xiàn)排序算法的動態(tài)演示。其目的是為了讓我們在使用計

　　

【正文】 操作步驟是：比較兩個關(guān)鍵字的大小和 將記錄從一個位子移至另一個位子，即比較和交換。本系統(tǒng)設(shè)定的情況為，記錄關(guān)鍵字都為整數(shù)，排序的結(jié)果是從大到小的排列，用到的三種排序算法為：冒泡排序法、選擇排序法、快速排序法。 第 2 頁 共 21 頁 6 系統(tǒng)需求及分析 系統(tǒng)需求 本系統(tǒng)的硬件環(huán)境： CPU AMD 2800+，內(nèi)存 512M 以上，硬盤 80G 以上。 本系統(tǒng)的軟件環(huán)境：操作系統(tǒng) Windows XP,Visual C++ 中文版。 系統(tǒng)開發(fā)環(huán)境選擇 本系統(tǒng)運用的是 Visual C++ 中文版，它是微軟公司開發(fā)出的一種集成開發(fā)環(huán)境，它擁有良好的可視化界面，它用來在 Windows 環(huán)境下開發(fā)應(yīng)用程序，是一種功能強大、行之有效的可視化編程工具。在 Visual C++ 中能夠進(jìn)行多種操作，它的特點就是能夠把原來抽象的數(shù)字、表格、功能邏輯等用直觀的圖形、圖象的形式表現(xiàn)出來。排序算法本來就是一種抽象的邏輯功能，想要直觀的把它演示出來，選擇利用 Visual C++ 的可視化編程是非常明智的。而且本系統(tǒng)在開發(fā)過程中，能夠用鼠標(biāo)點擊按鈕和拖放圖形化的對象，修改他們的屬性和行為過程。這種可視化的編程方法簡單、易學(xué)、易用，可以大大提高我們的工作效率。 系統(tǒng)的總體規(guī)劃 本系統(tǒng)的總體結(jié) 構(gòu)如圖 21 所示： 圖 21 系統(tǒng)總體結(jié)構(gòu) 7 系統(tǒng)設(shè)計思想 冒泡算法及思想 冒泡排序算法的基本思想：冒泡法的原理很簡單，基本思想就是比較相臨的兩個記錄的關(guān)鍵字，若前者比后者小則交換，若前者比后者大則保持不變。先將第一個記錄與第二個記錄比較，然后是第二個與第三個比較，直到倒數(shù)第二個與最后一個記錄。比較一輪結(jié)束之后，關(guān)鍵字大的記錄均向前移動。然后開始新一輪的比較，知道一輪比較下來，不再有記錄的交換發(fā)生為止。整個過 冒泡排序 選擇排序 同時進(jìn)行 動態(tài)演示排序系統(tǒng) 快速排序 第 3 頁 共 21 頁 程就有點象水中的氣泡上升的過程，輕的往上浮，重的向下 沉，這個算法的名字也就由此得來。 算法的步驟如下： （ 1）假設(shè)要排序的數(shù)列為 A[1]?? A[N]，我們把相鄰的兩個數(shù)兩兩進(jìn)行比較。即把 A[1]和 A[2]比較，對比完后把 A[2]和 A[3]進(jìn)行比較， ?? 直到 A[N1]和 A[N]比較完為止。在相鄰的兩個數(shù)兩兩進(jìn)行比較的過程中，如果前面的一個數(shù)比后面一個數(shù)大，則把這兩鄰的兩個數(shù)交換，也就是說，我們把較小的數(shù)放在前面，把較大的數(shù)調(diào)到后面。即，如果在一次比較中，如果 A[1]比 A[2]大的情況下，把 A[1]和 A[2]交換， ?? 以此類推，直到一輪 A[N1]和 A[N]比較 完。 （ 2）再次重復(fù)（ 1），直到相鄰兩數(shù)之間不再發(fā)生交換為止。 例如：一組待排序數(shù)列為： 圖 31 待排序組 根據(jù)算法思路（ 1）第一次對比后無變化； 根據(jù)算法思路（ 1）第二次對比發(fā)生變化：由于 A[2]=8 A[3]=5,所以兩者交換 圖 32 第一次交換 根據(jù)算法思路（ 1）第三次對比發(fā)生變化：由于 A[3]=8 A[4]=4,所以兩者交換 圖 33 第二次交換 根據(jù)算法思路（ 1）第四次對比無變化； 根據(jù)算法思路（ 1）第五次對比發(fā)生變化：由于 A[5]=9 A[6]=7，所有兩者交換 圖 34 第三次交換 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 頁 到此第一輪的排序結(jié)束，根據(jù)算法思路（ 2），重新對以交換排列后的數(shù)列進(jìn)行排序直到?jīng)]有變化為止，生成最后的序列： 圖 35 最后有序序列 分析冒泡排序法的效率，若記錄一開始就是從大到小排列，則一次循環(huán)就能完成排序；若記錄是“ 逆序”排列的，即是沖小到大的排列，則需 n1 次循環(huán)（ n為需要排序的記錄總數(shù)），共 n(n1)/2 次比較和交換。算法的負(fù)責(zé)度為O（ n n） . 選擇算法及思想 選擇排序算法的基本思想： 每一趟 (例如第 i 趟， i = 0, 1, ?, n2) 在后面 ni 個待排序?qū)ο笾羞x出關(guān)鍵碼最小的對象 , 作為有序?qū)ο笮蛄械牡? i 個對象。待到第 n2 趟作完，待排序?qū)ο笾皇Ｏ?1 個，就不用再選了。 我們選擇一種把最小的數(shù)放在第一個位置上的選擇排序算法，其思想是先并不急于調(diào)換位置，先從第一個數(shù)開始逐個向后掃描整個序 列，看哪個數(shù)最小就記下該數(shù)所在的位置，等一趟掃描完畢，再把第一個數(shù)和在他后面最小對調(diào)，這時此無序序列中最小的數(shù)據(jù)就換到了最前面的位置。算法的步驟如下： （ 1）、先從 A[1]開始向后檢查，檢查出在 A[1]后面的最小數(shù)的位子，我們設(shè)此位子為 A[P]。 （ 2）、依次把 A[P]和 A[N]（ A[N]從 1變化到 N）進(jìn)行比較，每次比較時，若 A[N]的數(shù)比 A[P]中的數(shù)小，則把 N 的值賦給 P，使 P 總是指向當(dāng)前所掃描過的最小數(shù)的位置，也就是說 A[P]總是等于所有掃描過的數(shù)最小的那個數(shù)。在依次一一比較后， P 就指向 N 個數(shù)中最小 的數(shù)所在位置，即 A[P]就是 N 個數(shù)中最小的那個數(shù)； （ 3）、把 A[P]和 A[1]的數(shù)對調(diào)，那么最小的數(shù)就在 A[1]中去了，也就是在最前面了。 （ 4）、重復(fù)此算法，但每重復(fù)一次，進(jìn)行比較的數(shù)列范圍就向后移動一個位置。即第二遍比較時范圍就從第 2 個數(shù)一直到第 N個數(shù)，在此范圍內(nèi)找最小的數(shù)的位置 P，然后把 A[P]與 A[2]對調(diào)，這樣從第 2個數(shù)開始到第 N 個數(shù)中最小數(shù)就在 A[2]中了，第三遍就從第 3個數(shù)到第 N個數(shù)中去找最小的數(shù)，再把 A[P]與 A[3]對調(diào)??此過程重復(fù) N1 次后，就把 A 數(shù)組中 N 個數(shù)按從小到大的順序排好 了。 例如，一組待排數(shù)據(jù)為： 4 5 6 7 8 9 第 5 頁 共 21 頁 圖 36 待排序列 根據(jù)選擇排序算法思路（ 1），從 A[1]=6 向后檢查，發(fā)現(xiàn)最小的數(shù)為 A[4]=4； 根據(jù)選擇排序算法思路（ 2），把 A[1]和 A[4]進(jìn)行比較，得出： A[1]=6 A[4]=4，所以把 A[4]和 A[1]對調(diào)，得到新的序列： 圖 37 第一次交換 根據(jù)選擇排序算法思路（ 3）： 即從 A[2]=8 向后檢查，從 A[3]A[6]從找到最小的數(shù) A[3]=5， 把 A[2]=8和 A[3]=5 進(jìn)行比較，得出： A[2]=8 A[3]=5，所以把 A[2]和 A[3]對調(diào) 圖 38 第二次交換 ?? 重復(fù)選擇排序算法思路（ 4） ,直到上面的排序工作不再有交換為止，得到最后序列為： 圖 39 最終序列 分析選擇排序算法效率，它實現(xiàn)的方式是：令 i從 1到 n1，進(jìn)行 n1次選擇操作。在選擇排序算法的過程中，所需進(jìn)行記錄移動的造作次數(shù)比較少，但是，無論記錄的初始排列如 何，所需進(jìn)行記錄關(guān)鍵字間的比較次數(shù)均為n(n1)/2。因此選擇排序算法的復(fù)雜度為 O(n n). 快速算法及思想 快速排序算法的基本思想：采用分而治之的辦法對一個表進(jìn)行排序，任取待排序?qū)ο笮蛄兄械哪硞€對象（例如取第一個對象）作為基準(zhǔn)，按照該對象的關(guān)鍵碼大小，將整個對象序列劃分為左右兩個子表－ 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 不動 第 6 頁 共 21 頁 （ 1）左側(cè)子序列 low中所有對象的關(guān)鍵碼都小于或等于基準(zhǔn)對象的關(guān)鍵碼； （ 2）右側(cè)子序列 high 中所有對象的關(guān)鍵碼都大于或等于基準(zhǔn)對象的關(guān)鍵碼。 基準(zhǔn)對象則排在這兩個子序列中間。然后再按此方法對 low和 high 兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，其整個過程可以遞歸進(jìn)行，從而使整個數(shù)列變成有序序列。 假設(shè)要排序的數(shù)列為 A[1]?? A[N],我們首先要取一個數(shù)據(jù)作為關(guān)鍵數(shù)據(jù)，一般情況下都是取第一個數(shù)據(jù)為關(guān)鍵數(shù)據(jù)。然后將所有小于它的數(shù)據(jù)放在它前面，所有大于它的數(shù)放在它后面，這個過程就稱為一趟快速排序。 算法的步驟如下： （ 1）、設(shè)置兩個變量 int=i， j，在排序開始的時候， i=1,j=N； （ 2）、以第一個數(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ù)據(jù)為：（設(shè)初始關(guān)鍵數(shù)據(jù)： key=50） 圖 310待排序列 根據(jù)步驟（ 3）進(jìn)行第一次 交換后： 圖 311第一次交換 （關(guān)鍵數(shù)據(jù) key=50 和 28發(fā)生交換，此時 j=6） 根據(jù)步驟（ 4）進(jìn)行第二次交換 后： 28 39 50 98 76 14 66 28 39 66 98 76 14 50 50 39 66 98 76 14 28 第 7 頁 共 21 頁 圖 312第二次交換 （關(guān)鍵數(shù)據(jù) key=50 和 66發(fā)生交換，此時 i=4） 根據(jù)步驟（ 5）將又一次執(zhí)行算法（ 3）進(jìn)行第三次交換： 圖 313第三次交換 （關(guān)鍵數(shù)據(jù) key=50 和 14發(fā)生交換，此時 j=5） 根據(jù)步驟（ 5）又將執(zhí)行一次算法（ 4）進(jìn)行第四次交換： 圖 314第四次交換 （關(guān)鍵數(shù)據(jù) key=50 和 98發(fā)生交換，此時 i=5） 此時我們可以看見 j=i，所以此時結(jié)束此趟快速排序。在經(jīng)過這趟快速排序后的結(jié)果是： 圖 315第五次交換 即所有大于初始關(guān)鍵數(shù)據(jù)“ 50”的數(shù)據(jù)全在其右邊，所有小于初始關(guān)鍵數(shù)據(jù)“ 50”的數(shù)據(jù)全部在其左邊。以“ 50”為數(shù)軸，把原序列分成了兩子序列，即： low{28 39 14},high{76 98 66},再遞歸的方法分別對前子表 low 和后子表 high 進(jìn)行類似的快速排序，從而完成所有數(shù)據(jù)序列的快速排序，最后把原來這個無序的數(shù)據(jù)序列排列成為一組有序 的序列： 圖 316最終序列 分析快速排序算法的效率，如果每次劃分對一個對象定位后，該對象的左側(cè)子序列與右側(cè)子序列的長度相同，則下一步將是對兩個長度減半的子序列進(jìn)行排序，這是最理想的情況。在 n個元素的序列中，對一個對象定位所需時間為 O(n)。若設(shè) t(n) 是對 n 個元素的序列進(jìn)行排序所需的時間，而且每次對28 39 14 50 76 98 66 14 28 39 50 66 76 98 28 39 14 50 76 98 66 28 39 14 98 76 50 66 第 8 頁 共 21 頁 一個對象正確定位后，正好把序列劃分為長度相等的兩個子序列，此時，總的計算時間為： T(n) + 2 t(n/2 ) // c 是一個常數(shù) Cn + 2 ( /2 + 2t(n/4) ) = 2 + 4t(n/4) 2 + 4 ( /4 +2t(n/8) ) = 3 + 8t(n/8) ??? Cn log2n + nt(1) = o(n log2n ) 因此該算法的算法復(fù)雜度為 O(n log2n ) 8 詳細(xì)設(shè)計 系統(tǒng)的文件的組織 本系統(tǒng)所含文件的組織如圖 41 所示： 動態(tài)演示冒泡算法模塊設(shè)計 首先，本系統(tǒng)是在 Visual C++ 中文版下 MFC 環(huán)境下，設(shè)置的“ MFC AppWizard(exe)”工程，工程名為 :“ tt”。相關(guān)的 ID 如表 4_1,4_2 所示 表 41 為工程添加 IDR_MAINFRAME的菜單選項 ID 說明文字 功能描述 IDC_SORT_BUBBLE 冒泡法排序 冒泡法排序 創(chuàng)建視圖框資源 添加新的菜單資源 創(chuàng)建視圖框類 添加菜單響應(yīng)函數(shù) 添加菜單中成員變量 源文件 添加全局指針 添加算法函數(shù)代碼 修改構(gòu)建函數(shù)實現(xiàn)演示 頭文件 添加定義常量 添加全局函數(shù) 圖 41 文件的組織 第 9 頁 共 21 頁 表 42 打開類向?qū)В?Class Wizard）對話框向視圖類添加響應(yīng)函數(shù) Object ID Messages Messages 的描述 函數(shù)名 IDC_SORT_BUBBLE COMMAND 選擇 該菜單 OnSortBubble 表 43 通過類查看（ ClassView）選項卡，向視圖類添加成員變量 變量類型 變量名 功能描述 int m_SortBubble[N] 記錄關(guān)鍵字 CRect m_SortBubbleRect 動態(tài)演示矩形范圍 BOOL IsSortBubble TRUE 表示進(jìn)行冒泡排序 打開