【正文】 義，又有實際應(yīng)用價值。 系統(tǒng)開發(fā)的意義 在現(xiàn)代信息發(fā)達(dá)的今天，面對接受到大量的無序的信息，沒有一個規(guī)則來編排和查詢，會給我們的工作和信息交流帶來十分的不便。例如在互聯(lián)網(wǎng)上為了使人們能夠快速的訪問和檢索大量的信息，人們會運(yùn)用許多快速并且優(yōu)秀的算法對這些數(shù)據(jù)進(jìn)行管理和操縱。 系統(tǒng)開發(fā)的相關(guān)技術(shù) 本系統(tǒng)利用 Visual C++ 作為開發(fā)平臺，利用它的可視化界面，在其MFC 環(huán)境下開發(fā)的一個演示三種不同排序算法，利用畫刷畫出三種不同的排序算法在排列隨即產(chǎn)生的 070 個數(shù)的過程，并且能夠?qū)Ρ冗@三種排序算法在相同的條件下，排序速率的快慢 。 系統(tǒng)開發(fā)的相關(guān)概念 首先我們要了解排序到底是什么？它的主要功能和目的是什么？簡單的說，排序是利用一種算法，將一個無規(guī)則的序列排成一個有序序列的過程。 排序的方法有很多種，但是沒有一種排序算法是通用的，即在任何情況下都能保持最快的排序速度。在排序的過程中，我們一般需要用到的兩個基本操作步驟是：比較兩個關(guān)鍵字的大小和將記錄從一個位子移至另一個位子，即比較和交換。 第 2 頁 共 21 頁 2 系統(tǒng)需求及分析 系統(tǒng)需求 本系統(tǒng)的 硬件環(huán)境： CPU AMD 2800+，內(nèi)存 512M 以上，硬盤 80G 以上。 系統(tǒng)開發(fā)環(huán)境選擇 本系統(tǒng)運(yùn)用的是 Visual C++ 中文版，它是微軟公司開發(fā)出的一種集成開發(fā)環(huán)境，它擁有良好的可視化界面，它用來在 Windows 環(huán)境下開發(fā)應(yīng)用程序，是一種功能強(qiáng)大、行之有效的可視化編程工具。排序 算法本來就是一種抽象的邏輯功能，想要直觀的把它演示出來，選擇利用 Visual C++ 的可視化編程是非常明智的。這種可視化的編程方法簡單、易學(xué)、易用，可以大大提高我們的工作效率。先將第一個記錄與第二個記錄比較，然后是第二個與第三個比較，直到倒數(shù)第二個與最后一個記錄。然后開始新一輪的比較，知道一輪比較下來，不再有記錄的交換發(fā)生為止。 算法的步驟如下： （ 1）假設(shè)要排序的數(shù)列為 A[1]?? A[N]，我們把相鄰的兩個數(shù)兩兩進(jìn)行比較。在相鄰的兩個數(shù)兩兩進(jìn)行比較的過程中，如果前面的一個數(shù)比后面一個數(shù)大，則把這兩鄰的兩個數(shù)交換，也就是說，我們把較小的數(shù)放在前面，把較大的數(shù)調(diào)到后面。 （ 2）再次重復(fù)（ 1），直到相鄰兩數(shù)之間不再發(fā)生交換為止。算法的負(fù)責(zé)度為 O（ n n） . 選擇算法及思想 選擇排序算法的基本思想： 每一趟 (例如第 i 趟 ， i = 0, 1, ?, n2) 在后面 ni 個待排序?qū)ο笾羞x出關(guān)鍵碼最小的對象 , 作為有序?qū)ο笮蛄械牡? i 個對象。 我們選擇一種把最小的數(shù)放在第一個位置上的選擇排序算法，其思想是先并不急于調(diào)換位置，先從第一個數(shù)開始逐個向后掃描整個序列，看哪個數(shù)最小就記下該數(shù)所在的位置，等一趟掃描完畢，再把第一個數(shù)和在他后面最小對調(diào)，這時此無序序列中最小的數(shù)據(jù)就換到了最前面的位置。 （ 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ù)。 （ 4）、重復(fù)此算法，但每重復(fù)一次，進(jì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 次選擇操作。因此選擇排序算法的復(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)鍵碼。然后再按此方法對 low和 high 兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，其整個過程可以遞歸進(jìn)行，從而使整個數(shù)列變成有序序列。 然后將所有小于它的數(shù)據(jù)放在它前面，所有大于它的數(shù)放在它后面，這個過程就稱為一趟快速排序。 例如，一組待排序數(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é)束此趟快速排序。以“ 50”為數(shù)軸，把原序列分成了兩子序列，即： low{28 39 14},high{76 98 66},再遞歸的方法分別對前子表 low 和后子表 high 進(jìn)行類似的快速排序，從而完成所有數(shù)據(jù)序列的快速排序，最后把原來這個無序的數(shù)據(jù)序列排列成為一組有序的序列： 圖 316最終序列 分析快速排序算法的效率，如果每次劃分對一個對象定位后，該對象的左側(cè)子序列與右側(cè)子序列的長度相同，則下一步將是對兩個長度減 半的子序列進(jì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 ) 4 詳細(xì)設(shè)計 系統(tǒng)的文件的組織 本系統(tǒng)所含文件的組織如圖 41 所示： 動態(tài)演示冒泡算法模塊設(shè)計 首先，本系統(tǒng)是在 Visual C++ 中文版下 MFC 環(huán)境下，設(shè)置的“ MFC AppWizard(exe)”工程，工程名為 :“ tt”。 由于開啟多線程時，使用的都是全局函數(shù)，想要獲得當(dāng)前視圖類中的數(shù)據(jù)，并實時更新試圖的顯示，就必須獲取當(dāng)前試圖對象。 然后，系統(tǒng)在 構(gòu)建文件中添加實現(xiàn)冒泡排序算法的函數(shù)：ThreadSortBubble,代碼為： UINT ThreadSortBubble(LPVOID lp) { int * data。 int tag。 for(i=0。i++) { tag=0。ji。 data[j]=data[j1]。 第 10 頁 共 21 頁 Sleep(DELAY)。 tag++。 } if(tag==0) break。 return 0。 srand((unsigned)time(NULL))。iN。 pView=this。 } 為了讓大家看清楚排序之間對比和交換的過程，修改響應(yīng)函數(shù)“ OnSortBubble” ,產(chǎn)生 070隨即整數(shù)來進(jìn)行排序： void CTtView::OnSortBubble() { for(int i=0。i++) { m_SortBubble[i]=(int)((double)rand()*(double)RAND_MAX)。 AfxBeginThread(ThreadSortBubble,GetSafeHwnd())。 CTtDoc* pDoc = GetDocument()。 if(IsSortBubble) { CBrush BlueBrush(RGB(0,255,0))。// for(i=0。i++) { =170。 =+1。 pDCFillRect(amp。BlueBrush)。 } 動態(tài)演示選擇算法模塊設(shè)計 表 44 為工程添加 IDR_MAINFRAME的菜單選項 ID 說明文字 功能描述 IDC_SORT_SELECT 選擇法排序 選擇法排序 表 45 打開類向?qū)В?Class Wizard）對話框向視圖類添加響應(yīng)函數(shù) Object ID Messages Messages 的描述 函數(shù)名 IDC_SORT_SELECT COMMAND 選擇該菜單 OnSortSelect 表 46 通過類查看（ ClassView）選項卡，向視圖類添加成員變量 變量類型 變量名 功能描述 int m_SortSelect[N] 記錄關(guān)鍵字 CRect m_SortSelectRect 動態(tài)演示矩形范圍 BOOL IsSortSelect TRUE 表示進(jìn)行選擇排序 在 頭文件，聲明選擇排序的全局函數(shù)： UINT ThreadSortSelect(LPVOID lp)。 int *data。 for(i=0。i++) 第 12 頁 共 21 頁 { key=i。jN。 pViewInvalidate(TRUE)。 } Sleep(DELAY)。 data[i]=data[key]。 } Sleep(DELAY)。 return 0。 srand((unsigned)time(NULL))。iN。 pView=this。 } 修改響應(yīng)函數(shù)“ OnSortSelect” ,產(chǎn)生 070隨即整數(shù)來進(jìn)行排序： void CTtView::OnSortSelect() { for(int i=0。i++) { m_SortSelect[i]=(int)((double)rand()*(double)RAND_MAX)。 第 13 頁 共 21 頁 AfxBeginThread(ThreadSortSelect,GetSafeHwnd())。 CTtDoc* pDoc = GetDocument()。 if(IsSortSelect) { CBrush BlueBrush(RGB(0,255,0))。 for(i=0。i++) { =170。 =+1。 pDCFillRect(amp。BlueBrush)。 } 動態(tài)演示快速算法模塊設(shè)計 表 47 為工程添加 IDR_MAINFRAME的菜單選項 ID 說明文字 功能描述 IDC_SORT_QUICK 快速法排序 快速法排序 表 48 打開類向?qū)В?Class Wizard）對話框向視圖類添加響應(yīng)函數(shù) Object ID Messages Messages 的描述 函數(shù)名 IDC_SORT_QUICK COMMAND 快速該菜單 OnSortQuick 表 49 通過類查看（ ClassView）選項卡，向視圖類添加成員變量 變量類型 變量名 功能描述 int m_SortQuick[N] 記錄關(guān)鍵字 CRect m_SortQuickRect 動態(tài)演示矩形范圍 BOOL IsSor