【正文】 若設(shè) t(n) 是對 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 詳細設(shè)計 系統(tǒng)的文件的組織 本系統(tǒng)所含文件的組織如圖 41 所示： 動態(tài)演示冒泡算法模塊設(shè)計 首先，本系統(tǒng)是在 Visual C++ 中文版下 MFC 環(huán)境下，設(shè)置的“ MFC AppWizard(exe)”工程，工程名為 :“ tt”。以“ 50”為數(shù)軸，把原序列分成了兩子序列，即： low{28 39 14},high{76 98 66},再遞歸的方法分別對前子表 low 和后子表 high 進行類似的快速排序，從而完成所有數(shù)據(jù)序列的快速排序，最后把原來這個無序的數(shù)據(jù)序列排列成為一組有序 的序列： 圖 316最終序列 分析快速排序算法的效率，如果每次劃分對一個對象定位后，該對象的左側(cè)子序列與右側(cè)子序列的長度相同，則下一步將是對兩個長度減半的子序列進行排序，這是最理想的情況。 例如，一組待排序數(shù)據(jù)為：（設(shè)初始關(guān)鍵數(shù)據(jù)： key=50） 圖 310待排序列 根據(jù)步驟（ 3）進行第一次 交換后： 圖 311第一次交換 （關(guān)鍵數(shù)據(jù) key=50 和 28發(fā)生交換，此時 j=6） 根據(jù)步驟（ 4）進行第二次交換 后： 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）進行第三次交換： 圖 313第三次交換 （關(guān)鍵數(shù)據(jù) key=50 和 14發(fā)生交換，此時 j=5） 根據(jù)步驟（ 5）又將執(zhí)行一次算法（ 4）進行第四次交換： 圖 314第四次交換 （關(guān)鍵數(shù)據(jù) key=50 和 98發(fā)生交換，此時 i=5） 此時我們可以看見 j=i，所以此時結(jié)束此趟快速排序。然后將所有小于它的數(shù)據(jù)放在它前面，所有大于它的數(shù)放在它后面，這個過程就稱為一趟快速排序。然后再按此方法對 low和 high 兩部分數(shù)據(jù)分別進行快速排序，其整個過程可以遞歸進行，從而使整個數(shù)列變成有序序列。因此選擇排序算法的復(fù)雜度為 O(n n). 快速算法及思想 快速排序算法的基本思想：采用分而治之的辦法對一個表進行排序，任取待排序?qū)ο笮蛄兄械哪硞€對象（例如取第一個對象）作為基準，按照該對象的關(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)鍵碼都小于或等于基準對象的關(guān)鍵碼； （ 2）右側(cè)子序列 high 中所有對象的關(guān)鍵碼都大于或等于基準對象的關(guān)鍵碼。 例如，一組待排數(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]進行比較，得出： 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 進行比較，得出： A[2]=8 A[3]=5，所以把 A[2]和 A[3]對調(diào) 圖 38第二次交換 ?? 重復(fù)選擇排序算法思路（ 4） ,直到上面的排序工作不再有交換為止，得到最后序列為： 圖 39最終序列 分析選擇排序算法效率，它實現(xiàn)的方式是：令 i 從 1 到 n1，進行 n1 次選擇操作。 （ 4）、重復(fù)此算法，但每重復(fù)一次，進行比較的數(shù)列范圍就向后移動一個位置。 （ 2）、依次把 A[P]和 A[N]（ A[N]從 1變化到 N）進行比較，每次比較時，若 A[N]的數(shù)比 A[P]中的數(shù)小，則把 N 的值賦給 P，使 P 總是指向當前所掃描過的最小數(shù)的位置，也就是說 A[P]總是等于所有掃描過的數(shù)最小的那個數(shù)。 我們選擇一種把最小的數(shù)放在第一個位置上的選擇排序算法，其思想是先并不急于調(diào)換位置，先從第一個數(shù)開始逐個向后掃描整個序 列，看哪個數(shù)最小就記下該數(shù)所在的位置，等一趟掃描完畢，再把第一個數(shù)和在他后面最小對調(diào)，這時此無序序列中最小的數(shù)據(jù)就換到了最前面的位置。算法的負責(zé)度為 O（ n n） . 選擇算法及思想 選擇排序算法的基本思想： 每一趟 (例如第 i 趟， i = 0, 1, ?, n2) 在后面 ni 個待排序?qū)ο笾羞x出關(guān)鍵碼最小的對象 , 作為有序?qū)ο笮蛄械牡? i 個對象。 （ 2）再次重復(fù)（ 1），直到相鄰兩數(shù)之間不再發(fā)生交換為止。在相鄰的兩個數(shù)兩兩進行比較的過程中，如果前面的一個數(shù)比后面一個數(shù)大，則把這兩鄰的兩個數(shù)交換，也就是說，我們把較小的數(shù)放在前面，把較大的數(shù)調(diào)到后面。 算法的步驟如下： （ 1）假設(shè)要排序的數(shù)列為 A[1]?? A[N]，我們把相鄰的兩個數(shù)兩兩進行比較。然后開始新一輪的比較，知道一輪比較下來，不再有記錄的交換發(fā)生為止。先將第一個記錄與第二個記錄比較，然后是第二個與第三個比較，直到倒數(shù)第二個與最后一個記錄。這種可視化的編程方法簡單、易學(xué)、易用，可以大大提高我們的工作效率。排序算法本來就是一種抽象的邏輯功能，想要直觀的把它演示出來，選擇利用 Visual C++ 的可視化編程是非常明智的。 系統(tǒng)開發(fā)環(huán)境選擇 本系統(tǒng)運用的是 Visual C++ 中文版，它是微軟公司開發(fā)出的一種集成開發(fā)環(huán)境，它擁有良好的可視化界面，它用來在 Windows 環(huán)境下開發(fā)應(yīng)用程序，是一種功能強大、行之有效的可視化編程工具。 第 2 頁 共 21 頁 6 系統(tǒng)需求及分析 系統(tǒng)需求 本系統(tǒng)的硬件環(huán)境： CPU AMD 2800+，內(nèi)存 512M 以上，硬盤 80G 以上。在排序的過程中，我們一般需要用到的兩個基本操作步驟是：比較兩個關(guān)鍵字的大小和 將記錄從一個位子移至另一個位子，即比較和交換。 排序的方法有很多種，但是沒有一種排序算法是通用的，即在任何情況下都能保持最快的排序速度。 系統(tǒng)開發(fā)的相關(guān)概念 首先我們要了解排序到底是什么？它的主要功能和目的是什么？簡單的說，排序是利用一種算法，將一個無規(guī)則的序列排成一個有序序列的過程。 系統(tǒng)開發(fā)的相關(guān)技術(shù) 本系統(tǒng)利用 Visual C++ 作為開發(fā)平臺，利用它的可視化界面，在其MFC 環(huán)境下開發(fā)的一個演示三種不同排序算法，利用畫刷畫出三種不同的排序算法在排列隨即產(chǎn)生的 070 個數(shù)的過程，并且能夠?qū)Ρ冗@三種排序算法在相同的條件下，排序速率的快慢 。例如在互聯(lián)網(wǎng)上為了使人們能夠快速的訪問和檢索大量的信 息，人們會運用許多快速并且優(yōu)秀的算法對這些數(shù)據(jù)進行管理和操縱。 系統(tǒng)開發(fā)的意義 在現(xiàn)代信息發(fā)達的今天，面對接受到大量的無序的信息，沒有一個規(guī)則來編排和查詢，會給我們的工作和信息交流帶來十分的不便。 Dynamic Demonstration 目錄 論文總頁數(shù)： 21 頁 1 引言 ................................................................... 1 系統(tǒng)背景 ........................................................... 1 系統(tǒng)開發(fā)的意義 ...................................................... 1 系統(tǒng)開發(fā)的相關(guān)技術(shù) .................................................. 1 系統(tǒng)開發(fā)的相關(guān)概念 .................................................. 1 2 系統(tǒng)需求及分析 ......................................................... 2 系統(tǒng)需求 ........................................................... 2 系統(tǒng)開發(fā)環(huán)境選擇 .................................................... 2 系統(tǒng)的總體規(guī)劃 ...................................................... 2 3 系統(tǒng)設(shè) 計思想 ........................................................... 2 冒泡算法及思想 ...................................................... 2 選擇算法及思想 ...................................................... 4 快速算法及思想 ...................................................... 5 4 詳細設(shè)計 ............................................................... 8 系統(tǒng)的文件的組織 .................................................... 8 動態(tài)演示冒泡算法模塊設(shè)計 ............................................ 8 動態(tài)演示選擇算法模塊設(shè)計 ........................................... 11 動態(tài)演示快速算法模塊設(shè)計 ........................................... 13 同時比較三種算法模塊設(shè)計 ........................................... 16 系統(tǒng)的測試 ........................................................ 16 系統(tǒng)的特點 ........................................................ 18 結(jié) 論 .................................................................. 19 參考文獻 .................................................................. 19 致 謝 .................................................................. 20 聲 明 ................................................................... 0 第 1 頁 共 21 頁 5 引言 系統(tǒng)背景 由于排序在計算機圖形、計算機輔助設(shè)計、機器人、模式識別、基因排序工程及統(tǒng)計學(xué)等領(lǐng)域具有廣泛應(yīng)用，所以對排序的研究既有理論上 的重要意義，又有實際應(yīng)用價值。 關(guān)鍵詞 ： Visual C++；排序算法；動態(tài)演示The Design and Development of Dynamic Sorting Algorithm Demo Abstract With puter science and technology improvement and development, its powerful puting has gradually integrate into human society in various fields, and play an increasingly important role. Of course, efficient putational speed does not mean unlimited fast, and the limited