【正文】 畢業(yè)設(shè)計(jì) ( 論文 ) 多種排序算法動(dòng)態(tài)演示軟件的設(shè)計(jì)與開(kāi)發(fā) 論文作者姓名： 申請(qǐng)學(xué)位專(zhuān)業(yè)： 申請(qǐng)學(xué)位類(lèi)別： 指導(dǎo)教師姓名（職稱(chēng)）： 論文提交日期： 多種排序算法動(dòng)態(tài)演示軟件的設(shè)計(jì)與開(kāi)發(fā) 摘 要 隨著計(jì)算機(jī)科學(xué)技術(shù)的不斷提高和發(fā)展，其強(qiáng)大的運(yùn)算功能已經(jīng)逐漸融入人類(lèi)社會(huì)的各個(gè)領(lǐng)域，并且在各個(gè)領(lǐng)域中發(fā)揮越來(lái)越重要的作用。當(dāng)然，高效的運(yùn)算速度并不代表無(wú)限快，在有限的資源空間里，要大大提高運(yùn)算處理數(shù)據(jù)的速率，就需要我們使用那些在時(shí)間和空間上體現(xiàn)出高效的算法。本系統(tǒng)是為了 演示在同一問(wèn)題上，不同的算法在效率上存在的巨大差異。本系統(tǒng)采用 Visual C++ 中文版為開(kāi)發(fā)工具，實(shí)現(xiàn)三種不同排序算法，即：冒泡排序算法、選擇排序算法和快速排序算法，以及這三種排序?qū)ν粏?wèn)題的處理并且以圖形的形式給出快慢比較，實(shí)現(xiàn)排序算法的動(dòng)態(tài)演示 。其目的是為了讓我們?cè)谑褂糜?jì)算機(jī)處理規(guī)模越來(lái)越大的數(shù)據(jù)問(wèn)題上，能夠清楚什么樣的算法適合當(dāng)前的處理系統(tǒng)。 關(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 ++ 。 Sorting Algorithm。 Dynamic Demonstration 目錄 論文總頁(yè)數(shù)： 21 頁(yè) 1 引言 ................................................................... 1 系統(tǒng)背景 ........................................................... 1 系統(tǒng)開(kāi)發(fā)的意義 ...................................................... 1 系統(tǒng)開(kāi)發(fā)的相關(guān)技術(shù) .................................................. 1 系統(tǒng)開(kāi)發(fā)的相關(guān)概念 .................................................. 1 2 系統(tǒng)需求及分析 ......................................................... 2 系統(tǒng)需求 ........................................................... 2 系統(tǒng)開(kāi)發(fā)環(huán)境 選擇 .................................................... 2 系統(tǒng)的總體規(guī)劃 ...................................................... 2 3 系統(tǒng)設(shè)計(jì)思想 ........................................................... 2 冒泡算法及思想 ...................................................... 2 選擇算法及思想 ...................................................... 4 快速算法及思想 ...................................................... 5 4 詳細(xì)設(shè)計(jì) ............................................................... 8 系統(tǒng)的文件的組織 .................................................... 8 動(dòng)態(tài)演示冒泡算法模塊設(shè)計(jì) ............................................ 8 動(dòng)態(tài)演示選擇算法模塊設(shè)計(jì) ........................................... 11 動(dòng)態(tài)演示快速算法模塊設(shè)計(jì) ........................................... 13 同時(shí)比較三種算法模塊設(shè)計(jì) ........................................... 16 系統(tǒng)的測(cè)試 ........................................................ 16 系統(tǒng)的特點(diǎn) ........................................................ 18 結(jié) 論 .................................................................. 19 參考文獻(xiàn) .................................................................. 19 致 謝 .................................................................. 20 聲 明 ................................................................... 0 第 1 頁(yè) 共 21 頁(yè) 1 引言 系統(tǒng)背景 由于排序在計(jì)算機(jī)圖形、計(jì)算機(jī)輔助設(shè)計(jì)、機(jī)器人、模式識(shí)別、基因排序工程及統(tǒng)計(jì)學(xué)等領(lǐng)域具有廣泛應(yīng)用，所以對(duì)排序的研究既有理論上的重要意義，又有實(shí)際應(yīng)用價(jià)值。再加上現(xiàn)在信息產(chǎn)業(yè)的迅速發(fā)展，信息的流通量越來(lái)越大，如此龐大并且雜亂無(wú)章的信息數(shù)據(jù)十分難以管理和查詢(xún)，就更加需要一種十分快捷而有效的編排手段來(lái)整理這些數(shù)據(jù)信息，讓我們的工作效率得 以提高。 系統(tǒng)開(kāi)發(fā)的意義 在現(xiàn)代信息發(fā)達(dá)的今天，面對(duì)接受到大量的無(wú)序的信息，沒(méi)有一個(gè)規(guī)則來(lái)編排和查詢(xún)，會(huì)給我們的工作和信息交流帶來(lái)十分的不便。因此，利用計(jì)算機(jī)的高速運(yùn)用和計(jì)算能力，編寫(xiě)出一種合適的排序軟件，能十分快捷的給我們?cè)谛畔⒔涣骱筒樵?xún)帶來(lái)便利。例如在互聯(lián)網(wǎng)上為了使人們能夠快速的訪(fǎng)問(wèn)和檢索大量的信息，人們會(huì)運(yùn)用許多快速并且優(yōu)秀的算法對(duì)這些數(shù)據(jù)進(jìn)行管理和操縱。優(yōu)秀的算法還能幫助我們?cè)诨ヂ?lián)網(wǎng)上快速找到最好的發(fā)送數(shù)據(jù)路線(xiàn)，以及怎么用搜索引擎來(lái)快速地找到信息所在的頁(yè)面。 系統(tǒng)開(kāi)發(fā)的相關(guān)技術(shù) 本系統(tǒng)利用 Visual C++ 作為開(kāi)發(fā)平臺(tái)，利用它的可視化界面，在其MFC 環(huán)境下開(kāi)發(fā)的一個(gè)演示三種不同排序算法，利用畫(huà)刷畫(huà)出三種不同的排序算法在排列隨即產(chǎn)生的 070 個(gè)數(shù)的過(guò)程，并且能夠?qū)Ρ冗@三種排序算法在相同的條件下，排序速率的快慢 。運(yùn)用 VC 編程語(yǔ)言，把一個(gè)程序中的算法和程序框架有效的結(jié)合起來(lái)，并且實(shí)現(xiàn)排序算法的動(dòng)態(tài)演示。 系統(tǒng)開(kāi)發(fā)的相關(guān)概念 首先我們要了解排序到底是什么？它的主要功能和目的是什么？簡(jiǎn)單的說(shuō)，排序是利用一種算法，將一個(gè)無(wú)規(guī)則的序列排成一個(gè)有序序列的過(guò)程。而算法則是以一組值或者一個(gè)值的集合作為輸入 ，經(jīng)過(guò)一系列計(jì)算得到的一組值作為輸出的過(guò)程，即是指那一系列將輸入轉(zhuǎn)化為輸出的計(jì)算過(guò)程。 排序的方法有很多種，但是沒(méi)有一種排序算法是通用的，即在任何情況下都能保持最快的排序速度。因此我們必須根據(jù)需要處理數(shù)據(jù)的特點(diǎn)來(lái)選擇合適的算法。在排序的過(guò)程中，我們一般需要用到的兩個(gè)基本操作步驟是：比較兩個(gè)關(guān)鍵字的大小和將記錄從一個(gè)位子移至另一個(gè)位子，即比較和交換。本系統(tǒng)設(shè)定的情況為，記錄關(guān)鍵字都為整數(shù)，排序的結(jié)果是從大到小的排列，用到的三種排序算法為：冒泡排序法、選擇排序法、快速排序法。 第 2 頁(yè) 共 21 頁(yè) 2 系統(tǒng)需求及分析 系統(tǒng)需求 本系統(tǒng)的 硬件環(huán)境： CPU AMD 2800+，內(nèi)存 512M 以上，硬盤(pán) 80G 以上。 本系統(tǒng)的軟件環(huán)境：操作系統(tǒng) Windows XP,Visual C++ 中文版。 系統(tǒng)開(kāi)發(fā)環(huán)境選擇 本系統(tǒng)運(yùn)用的是 Visual C++ 中文版，它是微軟公司開(kāi)發(fā)出的一種集成開(kāi)發(fā)環(huán)境，它擁有良好的可視化界面，它用來(lái)在 Windows 環(huán)境下開(kāi)發(fā)應(yīng)用程序，是一種功能強(qiáng)大、行之有效的可視化編程工具。在 Visual C++ 中能夠進(jìn)行多種操作，它的特點(diǎn)就是能夠把原來(lái)抽象的數(shù)字、表格、功能邏輯等用直觀的圖形、圖象的形式表現(xiàn)出來(lái)。排序 算法本來(lái)就是一種抽象的邏輯功能，想要直觀的把它演示出來(lái)，選擇利用 Visual C++ 的可視化編程是非常明智的。而且本系統(tǒng)在開(kāi)發(fā)過(guò)程中，能夠用鼠標(biāo)點(diǎn)擊按鈕和拖放圖形化的對(duì)象，修改他們的屬性和行為過(guò)程。這種可視化的編程方法簡(jiǎn)單、易學(xué)、易用，可以大大提高我們的工作效率。 系統(tǒng)的總體規(guī)劃 本系統(tǒng)的總體結(jié)構(gòu)如圖 21 所示： 圖 21 系統(tǒng)總體結(jié)構(gòu) 3 系統(tǒng)設(shè)計(jì)思想 冒泡算法及思想 冒泡排序算法的基本思想：冒泡法的原理很簡(jiǎn)單，基本思想就是比較相臨的兩個(gè)記錄的關(guān)鍵字， 若前者比后者小則交換，若前者比后者大則保持不變。先將第一個(gè)記錄與第二個(gè)記錄比較，然后是第二個(gè)與第三個(gè)比較，直到倒數(shù)第二個(gè)與最后一個(gè)記錄。比較一輪結(jié)束之后，關(guān)鍵字大的記錄均向前移動(dòng)。然后開(kāi)始新一輪的比較，知道一輪比較下來(lái)，不再有記錄的交換發(fā)生為止。整個(gè)過(guò) 冒泡排序 選擇排序 同時(shí)進(jìn)行 動(dòng)態(tài)演示排序系統(tǒng) 快速排序 第 3 頁(yè) 共 21 頁(yè) 程就有點(diǎn)象水中的氣泡上升的過(guò)程，輕的往上浮，重的向下沉，這個(gè)算法的名字也就由此得來(lái)。 算法的步驟如下： （ 1）假設(shè)要排序的數(shù)列為 A[1]?? A[N]，我們把相鄰的兩個(gè)數(shù)兩兩進(jìn)行比較。即把 A[1]和 A[2]比較，對(duì)比完后把 A[2]和 A[3]進(jìn)行比較， ?? 直到 A[N1]和 A[N]比較完為止。在相鄰的兩個(gè)數(shù)兩兩進(jìn)行比較的過(guò)程中，如果前面的一個(gè)數(shù)比后面一個(gè)數(shù)大，則把這兩鄰的兩個(gè)數(shù)交換，也就是說(shuō)，我們把較小的數(shù)放在前面，把較大的數(shù)調(diào)到后面。即，如果在一次比較中，如果 A[1]比 A[2]大的情況下，把 A[1]和 A[2]交換， ?? 以此類(lèi)推，直到一輪 A[N1]和 A[N]比較完。 （ 2）再次重復(fù)（ 1），直到相鄰兩數(shù)之間不再發(fā)生交換為止。 例如：一組待排序數(shù)列為： 圖 31 待排序組 根據(jù)算法思路（ 1）第一次對(duì)比后無(wú)變化； 根據(jù)算法思路（ 1）第二次對(duì)比發(fā)生變化：由于 A[2]=8 A[3]=5,所以?xún)烧呓粨Q 圖 32 第一次交換 根據(jù)算法思路（ 1）第三次對(duì)比發(fā)生變化：由于 A[3