【正文】 ................. 20 聲 明 ................................................................... 0 第 1 頁 共 21 頁 5 引言 系統(tǒng)背景 由于排序在計(jì)算機(jī)圖形、計(jì)算機(jī)輔助設(shè)計(jì)、機(jī)器人、模式識(shí)別、基因排序工程及統(tǒng)計(jì)學(xué)等領(lǐng)域具有廣泛應(yīng)用，所以對排序的研究既有理論上 的重要意義，又有實(shí)際應(yīng)用價(jià)值。例如在互聯(lián)網(wǎng)上為了使人們能夠快速的訪問和檢索大量的信 息，人們會(huì)運(yùn)用許多快速并且優(yōu)秀的算法對這些數(shù)據(jù)進(jìn)行管理和操縱。 系統(tǒng)開發(fā)的相關(guān)概念 首先我們要了解排序到底是什么？它的主要功能和目的是什么？簡單的說，排序是利用一種算法，將一個(gè)無規(guī)則的序列排成一個(gè)有序序列的過程。在排序的過程中，我們一般需要用到的兩個(gè)基本操作步驟是：比較兩個(gè)關(guān)鍵字的大小和 將記錄從一個(gè)位子移至另一個(gè)位子，即比較和交換。 系統(tǒng)開發(fā)環(huán)境選擇 本系統(tǒng)運(yùn)用的是 Visual C++ 中文版，它是微軟公司開發(fā)出的一種集成開發(fā)環(huán)境，它擁有良好的可視化界面，它用來在 Windows 環(huán)境下開發(fā)應(yīng)用程序，是一種功能強(qiáng)大、行之有效的可視化編程工具。這種可視化的編程方法簡單、易學(xué)、易用，可以大大提高我們的工作效率。然后開始新一輪的比較，知道一輪比較下來，不再有記錄的交換發(fā)生為止。在相鄰的兩個(gè)數(shù)兩兩進(jìn)行比較的過程中，如果前面的一個(gè)數(shù)比后面一個(gè)數(shù)大，則把這兩鄰的兩個(gè)數(shù)交換，也就是說，我們把較小的數(shù)放在前面，把較大的數(shù)調(diào)到后面。算法的負(fù)責(zé)度為O（ n n） . 選擇算法及思想 選擇排序算法的基本思想： 每一趟 (例如第 i 趟， i = 0, 1, ?, n2) 在后面 ni 個(gè)待排序?qū)ο笾羞x出關(guān)鍵碼最小的對象 , 作為有序?qū)ο笮蛄械牡? i 個(gè)對象。 （ 2）、依次把 A[P]和 A[N]（ A[N]從 1變化到 N）進(jìn)行比較，每次比較時(shí)，若 A[N]的數(shù)比 A[P]中的數(shù)小，則把 N 的值賦給 P，使 P 總是指向當(dāng)前所掃描過的最小數(shù)的位置，也就是說 A[P]總是等于所有掃描過的數(shù)最小的那個(gè)數(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 最終序列 分析選擇排序算法效率，它實(shí)現(xiàn)的方式是：令 i從 1到 n1，進(jìn)行 n1次選擇操作。然后再按此方法對 low和 high 兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，其整個(gè)過程可以遞歸進(jìn)行，從而使整個(gè)數(shù)列變成有序序列。 例如，一組待排序數(shù)據(jù)為：（設(shè)初始關(guān)鍵數(shù)據(jù)： key=50） 圖 310待排序列 根據(jù)步驟（ 3）進(jìn)行第一次 交換后： 圖 311第一次交換 （關(guān)鍵數(shù)據(jù) key=50 和 28發(fā)生交換，此時(shí) 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ā)生交換，此時(shí) i=4） 根據(jù)步驟（ 5）將又一次執(zhí)行算法（ 3）進(jìn)行第三次交換： 圖 313第三次交換 （關(guān)鍵數(shù)據(jù) key=50 和 14發(fā)生交換，此時(shí) j=5） 根據(jù)步驟（ 5）又將執(zhí)行一次算法（ 4）進(jìn)行第四次交換： 圖 314第四次交換 （關(guān)鍵數(shù)據(jù) key=50 和 98發(fā)生交換，此時(shí) i=5） 此時(shí)我們可以看見 j=i，所以此時(shí)結(jié)束此趟快速排序。若設(shè) t(n) 是對 n 個(gè)元素的序列進(jìn)行排序所需的時(shí)間，而且每次對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 頁 一個(gè)對象正確定位后，正好把序列劃分為長度相等的兩個(gè)子序列，此時(shí)，總的計(jì)算時(shí)間為： T(n) + 2 t(n/2 ) // c 是一個(gè)常數(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è)計(jì) 系統(tǒng)的文件的組織 本系統(tǒng)所含文件的組織如圖 41 所示： 動(dòng)態(tài)演示冒泡算法模塊設(shè)計(jì) 首先，本系統(tǒng)是在 Visual C++ 中文版下 MFC 環(huán)境下，設(shè)置的“ MFC AppWizard(exe)”工程，工程名為 :“ tt”。以“ 50”為數(shù)軸，把原序列分成了兩子序列，即： low{28 39 14},high{76 98 66},再遞歸的方法分別對前子表 low 和后子表 high 進(jìn)行類似的快速排序，從而完成所有數(shù)據(jù)序列的快速排序，最后把原來這個(gè)無序的數(shù)據(jù)序列排列成為一組有序 的序列： 圖 316最終序列 分析快速排序算法的效率，如果每次劃分對一個(gè)對象定位后，該對象的左側(cè)子序列與右側(cè)子序列的長度相同，則下一步將是對兩個(gè)長度減半的子序列進(jìn)行排序，這是最理想的情況。然后將所有小于它的數(shù)據(jù)放在它前面，所有大于它的數(shù)放在它后面，這個(gè)過程就稱為一趟快速排序。因此選擇排序算法的復(fù)雜度為 O(n n). 快速算法及思想 快速排序算法的基本思想：采用分而治之的辦法對一個(gè)表進(jìn)行排序，任取待排序?qū)ο笮蛄兄械哪硞€(gè)對象（例如取第一個(gè)對象）作為基準(zhǔn)，按照該對象的關(guān)鍵碼大小，將整個(gè)對象序列劃分為左右兩個(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中所有對象的關(guān)鍵碼都小于或等于基準(zhǔn)對象的關(guān)鍵碼； （ 2）右側(cè)子序列 high 中所有對象的關(guān)鍵碼都大于或等于基準(zhǔn)對象的關(guān)鍵碼。 （ 4）、重復(fù)此算法，但每重復(fù)一次，進(jìn)行比較的數(shù)列范圍就向后移動(dòng)一個(gè)位置。 我們選擇一種把最小的數(shù)放在第一個(gè)位置上的選擇排序算法，其思想是先并不急于調(diào)換位置，先從第一個(gè)數(shù)開始逐個(gè)向后掃描整個(gè)序 列，看哪個(gè)數(shù)最小就記下該數(shù)所在的位置，等一趟掃描完畢，再把第一個(gè)數(shù)和在他后面最小對調(diào)，這時(shí)此無序序列中最小的數(shù)據(jù)就換到了最前面的位置。 （ 2）再次重復(fù)（ 1），直到相鄰兩數(shù)之間不再發(fā)生交換為止。 算法的步驟如下： （ 1）假設(shè)要排序的數(shù)列為 A[1]?? A[N]，我們把相鄰的兩個(gè)數(shù)兩兩進(jìn)行比較。先將第一個(gè)記錄與第二個(gè)記錄比較，然后是第二個(gè)與第三個(gè)比較，直到倒數(shù)第二個(gè)與最后一個(gè)記錄。排序算法本來就是一種抽象的邏輯功能，想要直觀的把它演示出來，選擇利用 Visual C++ 的可視化編程是非常明智的。 第 2 頁 共 21 頁 6 系統(tǒng)需求及分析 系統(tǒng)需求 本系統(tǒng)的硬件環(huán)境： CPU AMD 2800+，內(nèi)存 512M 以上，硬盤 80G 以上。 排序的方法有很多種，但是沒有一種排序算法是通用的，即在任何情況下都能保持最快的排序速度。 系統(tǒng)開發(fā)的相關(guān)技術(shù) 本系統(tǒng)利用 Visual C++ 作為開發(fā)平臺(tái)，利用它的可視化界面，在其MFC 環(huán)境下開發(fā)的一個(gè)演示三種不同排序算法，利用畫刷畫出三種不同的排序算法在排列隨即產(chǎn)生的 070 個(gè)數(shù)的過程，并且能夠?qū)Ρ冗@三種排序算法在相同的條件下，排序速率的快慢 。 系統(tǒng)開發(fā)的意義 在現(xiàn)代信息發(fā)達(dá)的今天，面對接受到大量的無序的信息，沒有一個(gè)規(guī)則來編排和查詢，會(huì)給我們的工作和信息交流帶來十分的不便。 關(guān)鍵詞 ： Visual C++；排序算法；動(dòng)態(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 resources of space, Operators must significantly improve processing speed, we need to use the time and space reflects efficient algorithms. The system is 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 ++ 。當(dāng)然，高效的運(yùn)算速度并不代表無限快，在有限的資源空間里，要大大提高運(yùn)算處理數(shù)據(jù)的速率，就需要我們使用那些在時(shí)間和空間上體現(xiàn)出高效的算法。 （ 4）學(xué)校可允許學(xué)位論文被查閱或借閱。除非另有說明，本文的工作是原始性工作。 [7] 黃福員 .冒泡排序算法的改進(jìn) [J].微機(jī)發(fā)展 ,2020,13(11):6667。 [2] [美 ].數(shù)據(jù)結(jié)構(gòu) — C++版 [M].王海 濤 ,丁炎炎譯 .北京：清華大學(xué)出版社 ,2020。 結(jié) 論 通過本次系統(tǒng)的研究，可以看出各個(gè)不同的排序算法排序的過程，以及之間在排列整數(shù)時(shí)的差異。 （ 2）選擇“選擇法排序”時(shí)，可以看見綠色的長條是被交換到左邊的過程，這個(gè)也完全證明了選擇排序算法的思 想。 圖 48 同時(shí)比較三種排序開始 （ 2）第一個(gè)排序 —— 快速排序完畢。 OnSortQuick1()。m_SortQuickRect,amp。 =450+i*2。 pDCTextOut(450,200,快速排序演示 )。 } 第 16 頁 共 21 頁 最后修改 OnDraw 函數(shù)，利用畫刷實(shí)現(xiàn)動(dòng)態(tài)繪制： void CTtView::OnDraw(CDC* pDC) { int i。iN。i++) m_SortQuick[i] =0。 } 打開類（ Class View） 中視圖類 CTtView，在其中修改構(gòu)建函數(shù)，實(shí)現(xiàn)變量初始化： CTtView::CTtView() { int i。 pViewInvalidate(TRUE)。 } QuickSort(data,low,i1)。 第 15 頁 共 21 頁 data[i]=data[j]。 while(ij) { if(data[i]=tmp)