【正文】 畢業(yè)設(shè)計 ( 論文 ) 多種排序算法動態(tài)演示軟件的設(shè)計與開發(fā) 論文作者姓名： 申請學(xué)位專業(yè)： 申請學(xué)位類別： 指導(dǎo)教師姓名（職稱）： 論文提交日期： 多種排序算法動態(tài)演示軟件的設(shè)計與開發(fā) 摘 要 隨著計算機科學(xué)技術(shù)的不斷提高和發(fā)展，其強大的運算功能已經(jīng)逐漸融入人類社會的各個領(lǐng)域，并且在各個領(lǐng)域中發(fā)揮越來越重要的作用。當(dāng)然，高效的運算速度并不代表無限快，在有限的資源空間里，要大大提高運算處理數(shù)據(jù)的速率，就需要我們使用那些在時間和空間上體現(xiàn)出高效的算法。本系統(tǒng)是為了 演示在同一問題上，不同的算法在效率上存在的巨大差異。本系統(tǒng)采用 Visual C++ 中文版為開發(fā)工具，實現(xiàn)三種不同排序算法，即：冒泡排序算法、選擇排序算法和快速排序算法，以及這三種排序?qū)ν粏栴}的處理并且以圖形的形式給出快慢比較，實現(xiàn)排序算法的動態(tài)演示 。其目的是為了讓我們在使用計算機處理規(guī)模越來越大的數(shù)據(jù)問題上，能夠清楚什么樣的算法適合當(dāng)前的處理系統(tǒ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 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 目錄 論文總頁數(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 頁 1 引言 系統(tǒng)背景 由于排序在計算機圖形、計算機輔助設(shè)計、機器人、模式識別、基因排序工程及統(tǒng)計學(xué)等領(lǐng)域具有廣泛應(yīng)用，所以對排序的研究既有理論上的重要意義，又有實際應(yīng)用價值。再加上現(xiàn)在信息產(chǎn)業(yè)的迅速發(fā)展，信息的流通量越來越大，如此龐大并且雜亂無章的信息數(shù)據(jù)十分難以管理和查詢，就更加需要一種十分快捷而有效的編排手段來整理這些數(shù)據(jù)信息，讓我們的工作效率得 以提高。 系統(tǒng)開發(fā)的意義 在現(xiàn)代信息發(fā)達的今天，面對接受到大量的無序的信息，沒有一個規(guī)則來編排和查詢，會給我們的工作和信息交流帶來十分的不便。因此，利用計算機的高速運用和計算能力，編寫出一種合適的排序軟件，能十分快捷的給我們在信息交流和查詢帶來便利。例如在互聯(lián)網(wǎng)上為了使人們能夠快速的訪問和檢索大量的信息，人們會運用許多快速并且優(yōu)秀的算法對這些數(shù)據(jù)進行管理和操縱。優(yōu)秀的算法還能幫助我們在互聯(lián)網(wǎng)上快速找到最好的發(fā)送數(shù)據(jù)路線，以及怎么用搜索引擎來快速地找到信息所在的頁面。 系統(tǒng)開發(fā)的相關(guān)技術(shù) 本系統(tǒng)利用 Visual C++ 作為開發(fā)平臺，利用它的可視化界面，在其MFC 環(huán)境下開發(fā)的一個演示三種不同排序算法，利用畫刷畫出三種不同的排序算法在排列隨即產(chǎn)生的 070 個數(shù)的過程，并且能夠?qū)Ρ冗@三種排序算法在相同的條件下，排序速率的快慢 。運用 VC 編程語言，把一個程序中的算法和程序框架有效的結(jié)合起來，并且實現(xiàn)排序算法的動態(tài)演示。 系統(tǒng)開發(fā)的相關(guān)概念 首先我們要了解排序到底是什么？它的主要功能和目的是什么？簡單的說，排序是利用一種算法，將一個無規(guī)則的序列排成一個有序序列的過程。而算法則是以一組值或者一個值的集合作為輸入 ，經(jīng)過一系列計算得到的一組值作為輸出的過程，即是指那一系列將輸入轉(zhuǎn)化為輸出的計算過程。 排序的方法有很多種，但是沒有一種排序算法是通用的，即在任何情況下都能保持最快的排序速度。因此我們必須根據(jù)需要處理數(shù)據(jù)的特點來選擇合適的算法。在排序的過程中，我們一般需要用到的兩個基本操作步驟是：比較兩個關(guān)鍵字的大小和將記錄從一個位子移至另一個位子，即比較和交換。本系統(tǒng)設(shè)定的情況為，記錄關(guān)鍵字都為整數(shù)，排序的結(jié)果是從大到小的排列，用到的三種排序算法為：冒泡排序法、選擇排序法、快速排序法。 第 2 頁 共 21 頁 2 系統(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++ 中能夠進行多種操作，它的特點就是能夠把原來抽象的數(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) 3 系統(tǒng)設(shè)計思想 冒泡算法及思想 冒泡排序算法的基本思想：冒泡法的原理很簡單，基本思想就是比較相臨的兩個記錄的關(guān)鍵字， 若前者比后者小則交換，若前者比后者大則保持不變。先將第一個記錄與第二個記錄比較，然后是第二個與第三個比較，直到倒數(shù)第二個與最后一個記錄。比較一輪結(jié)束之后，關(guān)鍵字大的記錄均向前移動。然后開始新一輪的比較，知道一輪比較下來，不再有記錄的交換發(fā)生為止。整個過 冒泡排序 選擇排序 同時進行 動態(tài)演示排序系統(tǒng) 快速排序 第 3 頁 共 21 頁 程就有點象水中的氣泡上升的過程，輕的往上浮，重的向下沉，這個算法的名字也就由此得來。 算法的步驟如下： （ 1）假設(shè)要排序的數(shù)列為 A[1]?? A[N]，我們把相鄰的兩個數(shù)兩兩進行比較。即把 A[1]和 A[2]比較，對比完后把 A[2]和 A[3]進行比較， ?? 直到 A[N1]和 A[N]比較完為止。在相鄰的兩個數(shù)兩兩進行比較的過程中，如果前面的一個數(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