【正文】 ery和主流的 Javascript 庫(kù)。它是功能豐富的 JavaEE 集成開(kāi)發(fā)環(huán)境 ，包括了完備的編碼、調(diào)試、測(cè)試和發(fā)布功能，完整支持 HTML,Struts,JSP,CSS,Javascript,Spring,SQL,Hibernate。 Javah：產(chǎn)生可以調(diào)用 Java 過(guò)程的 C 過(guò)程，或建立能被 Java 程序調(diào)用的 C過(guò)程的頭文件。 javadoc – 文檔生成器，從源碼注釋中提取文檔。 ME(J2ME)，micro edition，主要用于移動(dòng)設(shè)備、嵌入式設(shè)備上的 java 應(yīng)用程序，從 JDK 開(kāi)始，改名為 Java ME。特別是 Java 企業(yè)應(yīng)用編程接口（ Java Enterprise APIs）為企業(yè)計(jì)算及 電子商務(wù)應(yīng)用 系統(tǒng)提供了有關(guān)技術(shù)和豐富的類庫(kù)。另外， Java 中的類有一個(gè)運(yùn)行時(shí)刻的表示，能進(jìn)行運(yùn)行時(shí)刻的類型檢查。 Java 語(yǔ)言是動(dòng)態(tài)的 [10]。通常有兩種方法來(lái)創(chuàng)建線程：其一，使用型構(gòu)為 Thread(Runnable)的構(gòu)造子將一個(gè)實(shí)現(xiàn)了 Runnable 接口的對(duì)象包裝成一個(gè)線程，其二，從 Thread 類派生出子類并重寫(xiě) run方法，使用該子類創(chuàng)建的對(duì)象即為線程。 Java 是性能略高的 [10]。 Java 系統(tǒng)本身也具有很強(qiáng)的可移植性， Java 編譯器是用 Java 實(shí)現(xiàn)的， Java陜西理工學(xué)院畢業(yè)設(shè)計(jì) 第 3 頁(yè) 共 80 頁(yè) 的運(yùn)行環(huán)境是用 ANSIC 實(shí)現(xiàn)的。 Java 程序（后綴為 java 的文件）在 Java 平臺(tái)上被編譯為體系結(jié)構(gòu)中立的 字節(jié)碼 格式（后綴為 class 的文件），然后可以在實(shí)現(xiàn)這個(gè) Java 平臺(tái)的任何系統(tǒng)中運(yùn)行。 Java 語(yǔ)言是安全的。 Java 語(yǔ)言是健壯的 [10]?？傊?， Java語(yǔ)言是一個(gè)純的 面向?qū)ο蟪绦蛟O(shè)計(jì) 語(yǔ)言。并提供了自動(dòng)的廢料收集，使得程序員不必為 內(nèi)存管理 而擔(dān)憂。主要特性： Java 語(yǔ)言是易學(xué)的 [10]。Java 自面世后就非常流行，發(fā)展迅速，對(duì) C++語(yǔ)言形成了有力沖擊。排序算法在計(jì)算機(jī)科學(xué)中有非常重要的地位 ，且排序在人們的日常 生活和學(xué)習(xí)、科研、生產(chǎn)等各個(gè)方面有著重要的應(yīng)用，因此掌握常用的排序算法是很有必要。 因此，本文以 java 為開(kāi)發(fā)語(yǔ)言，設(shè)計(jì)開(kāi)發(fā)了 基于姓名排序算法動(dòng)態(tài)演示系統(tǒng)，有助于初學(xué)者的形象直觀的學(xué)習(xí)排序算法。 各個(gè)應(yīng)用領(lǐng)域迫切需要解決的問(wèn)題，也是當(dāng)前數(shù)據(jù)結(jié)構(gòu)基本的研究?jī)?nèi)容之一在計(jì)算機(jī)科學(xué)與信息融為一體的今天，研究數(shù)據(jù)結(jié)構(gòu)，既要 從 計(jì)算機(jī)技術(shù)的發(fā)展考慮，也要從信息技術(shù)的發(fā)展考慮，特別需要重視從理論到實(shí)際的轉(zhuǎn)化研究。數(shù)據(jù)結(jié)構(gòu)從一維二維向三維和多維數(shù)據(jù)結(jié)構(gòu)的研究意義以及如何實(shí)現(xiàn)它們等等，都是數(shù)據(jù)結(jié)構(gòu)今后研究的重要內(nèi)容 [2]。 其 加強(qiáng)對(duì)新數(shù)據(jù)類型的研究和尋找更適用更完善的數(shù)據(jù)結(jié)構(gòu)類型，也是今后數(shù)據(jù)結(jié)構(gòu)研究的重要內(nèi)容 .抽象數(shù)據(jù)結(jié)構(gòu)類型的出現(xiàn)，使得在面向?qū)ο蟮恼Z(yǔ)言中 ,值和變量的類型不再單一，語(yǔ)言中的操作可以作用于多種類型的對(duì)象 [1]。 Sorting Algorithm。本文以 Java 作為開(kāi)發(fā)工具，設(shè)計(jì)與開(kāi)發(fā)了基于姓名排序算法動(dòng)態(tài)演示系統(tǒng)。該系統(tǒng)實(shí)現(xiàn)了 插入排序（鏈表插入排序、直接插入排序、折半插入排序等）、交換排序、選擇排序、歸并排序、堆排序等算法的動(dòng)態(tài)演示。Dynamic Presentation 陜西理工學(xué)院畢業(yè)設(shè)計(jì) 目 錄 引言 ...................................................... 1 1 系統(tǒng)背景及意義 ........................................... 2 ............................................. 2 ....................................... 2 ......................................... 2 2 排序算法 ................................................. 5 ......................................... 5 ......................................... 6 ............................................. 6 ............................................. 8 ............................................. 9 ........................................ 10 .............................................. 11 （ MSD） ..................................... 12 3 系統(tǒng)設(shè)計(jì) ................................................ 14 ........................................ 14 模塊算法流程圖 ...................................... 14 4 實(shí)現(xiàn) .................................................... 21 直接插入排序 ........................................ 21 折半插入排序 ........................................ 21 ............................................ 22 ............................................ 22 ............................................ 23 ........................................ 23 .............................................. 24 （ MSD） ..................................... 25 5 測(cè)試 .................................................... 26 總結(jié) ..................................................... 34 致謝 ..................................................... 35 參考文獻(xiàn) ................................................. 36 科技外文文獻(xiàn) ............................................. 37 附錄 A:基于姓名排序算法動(dòng)態(tài)演示系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)源代碼 ..... 47 附錄 B:使用說(shuō)明書(shū) ......................................... 80 陜西理工學(xué)院畢業(yè)設(shè)計(jì) 第 1 頁(yè) 共 80 頁(yè) 引言 計(jì)算機(jī)技術(shù)的日益發(fā)展，其應(yīng)用早已不局限于簡(jiǎn)單的數(shù)值運(yùn)算。因此 ,要建立良好的數(shù)據(jù)結(jié)構(gòu)，首先對(duì)系統(tǒng)按某種原則進(jìn)行分解，使系統(tǒng)中各模塊間獨(dú)立性強(qiáng)，依賴性小，結(jié)構(gòu)靈活 ,易于維護(hù)。 數(shù)據(jù)結(jié)構(gòu)基本元素內(nèi)容的發(fā)展變化 ， 為數(shù)據(jù)結(jié)構(gòu)的研究開(kāi)拓 了 一個(gè)新的方向 [1]。許多諸如數(shù)據(jù)工程多 媒介數(shù)據(jù)庫(kù)和知識(shí)工程等等新發(fā)展起來(lái)的學(xué)科，也都大量涉及封數(shù)據(jù)結(jié)構(gòu)的理論和技術(shù) , 迫切要求開(kāi)拓與之對(duì)適應(yīng)的數(shù)據(jù)結(jié)構(gòu) [11]。陜西理工學(xué)院畢業(yè)設(shè)計(jì) 第 2 頁(yè) 共 80 頁(yè) 1 系 統(tǒng)背景及意義 系統(tǒng)背景 由于排序在計(jì)算機(jī)圖形、計(jì)算機(jī)輔助設(shè)計(jì)、機(jī)器人、模式識(shí)別、基因排序工程及統(tǒng)計(jì)學(xué)等領(lǐng)域具有廣泛應(yīng)用，所以對(duì)排序的研究既有理論上的重要意義，又有實(shí)際應(yīng)用價(jià)值。在以后的發(fā)展中，排序?qū)ξ覀兊膶W(xué)習(xí)和生活的影響會(huì)逐漸增大，因此設(shè)計(jì)開(kāi)發(fā)一個(gè)排序算法動(dòng)畫(huà)演示系統(tǒng)，以提高自己對(duì)排序算法的掌握程度 ,并希望該系統(tǒng)有助于初學(xué)者直觀學(xué)習(xí)排序算法。 Java 技術(shù)具有卓越的通用性、高效性、平臺(tái)移植性和 安全 性，廣泛應(yīng)用于個(gè)人 PC、 數(shù)據(jù)中心 、 游戲 控制臺(tái)、 科學(xué) 超級(jí)計(jì)算機(jī) 、 移動(dòng)電話 和 互聯(lián)網(wǎng) ，同時(shí)擁有全球最大的開(kāi)發(fā)者專業(yè)社群。 Java 語(yǔ)言的語(yǔ)法與 C 語(yǔ)言 和 C++語(yǔ)言很接近，使得大多數(shù)程序員很容易學(xué)習(xí)和使用 Java。 Java 語(yǔ)言是強(qiáng)制面向?qū)ο蟮?[8]。 Java 語(yǔ)言是分布式的 [10]。 Java 的 強(qiáng)類型 機(jī)制、 異常處理 、垃圾的自動(dòng)收集等是 Java 程序健壯性的重要保證。 Java 通常被用在網(wǎng)絡(luò)環(huán)境中，為此， Java 提供了一個(gè)安全機(jī)制以防 惡意代碼的攻擊。這種途徑適合于異構(gòu)的網(wǎng)絡(luò)環(huán)境和軟件的分發(fā)。 Java 語(yǔ)言是解釋型的 [10]。與那些解釋型的高級(jí) 腳本語(yǔ)言 相比， Java 的性能還是較優(yōu)的。值得注意的是 Thread 類已經(jīng)實(shí)現(xiàn)了 Runnable 接口，因此，任何一個(gè)線程均有它的 run 方法，而 run 方法中包含了線程所要運(yùn)行的 代碼 。 Java 語(yǔ)言的設(shè)計(jì)目標(biāo)之一是適應(yīng)于動(dòng)態(tài)變化的環(huán)境。 Java 語(yǔ)言的優(yōu)良特性使得 Java 應(yīng)用具有無(wú)比的健壯性和 可靠性 ， 這也減少了應(yīng)用系統(tǒng)的維護(hù)費(fèi)用。 (2) JDK 運(yùn)行環(huán)境 JDK[8](Java Development Kit) 是 Java 語(yǔ)言的軟件開(kāi)發(fā)工具包 (SDK)。 沒(méi)有 JDK 的話，無(wú)法編譯 Java 程序，如果想只運(yùn)行 Java 程序，要確保已安裝相應(yīng)的 JRE。 jdb – debugger，查錯(cuò)工具。 Javap： Java 反匯編器 ，顯示編譯類文件中的可訪問(wèn)功能和數(shù)據(jù)，同時(shí)顯示 字節(jié)代碼 含義。 MyEclipse 是一個(gè)十分優(yōu)秀的用于開(kāi)發(fā) Java, J2EE 的 Eclipse 插件集合， MyEclipse 的功能非常強(qiáng)大，支持也十分廣泛，尤其是對(duì)各種開(kāi)源產(chǎn)品的支持十分不錯(cuò)。隨著 MyEclipse 20xx支持 Html5，你可以添加音頻、視頻和 API 元素到你的項(xiàng)目，從而為移動(dòng)設(shè)備創(chuàng)建復(fù)雜的 Web 應(yīng)用程序。每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當(dāng)位置，直到全部記錄插入完成為止，為了在查找插入位置的過(guò)程中避免數(shù)組下標(biāo)出界，在 l[0]處設(shè)置監(jiān)視哨 [1]。 i 。 for (。 } } } (3) 時(shí)間復(fù)雜度分析 陜西理工學(xué)院畢業(yè)設(shè)計(jì) 第 6 頁(yè) 共 80 頁(yè) 直接插入排序算法必須 進(jìn)行 n1 趟。 折半插入排序 (1) 基本思想 是對(duì) 直接 插入排序算法的一種改進(jìn)，由于排序算法過(guò)程中，就是不斷的依次將元素插入前面已排好序的序列中。 i 。 if (src[0].pareTo(src[m]) 0) {// high = m 1。 j) { src[j + 1] = src[j]。 快速排序 (1) 基本原理 對(duì)起泡排序的一種改進(jìn)。這個(gè)過(guò)程稱一趟快速排序 [11]。 //軸記錄關(guān)鍵字 String pivotkey = l[low]。 } //將比軸記錄大的記錄移到高端 l[low] = l[high]。 } l[high] = l[low]。如果選擇左邊第一個(gè)元素為主元，則快速排序的最壞情況發(fā)生在原始序列正向有序或反向有序時(shí)。 圖 選擇排序示例 (2)算法描述 對(duì)字符串順序鏈表 src作選擇排序，返回值為空。 if (j != i) { String temp = src[i]。不論初始排列如何，該算法都必須執(zhí)行 n1 趟，每趟執(zhí)行 ni1 次關(guān)鍵字的比較，這樣總的比較次數(shù)為：所以，簡(jiǎn)單選擇排序的最好、最壞和平均情況的時(shí)間復(fù)雜度都為 O(n2)。 //臨時(shí)數(shù)據(jù)存儲(chǔ) int i=s, k = 0,j = m+1。 j = t。 j++。 k++。 k++。 圖 鏈表插入排序示例 (2) 算法描述 對(duì)有序 靜態(tài)鏈表 nodes作鏈表插入排序，返回值為空。 int p = nodes[0].getNext()。 nodes[i].setNext(p)。 for (int j = 2 * i。 num[j].pareTo(num[j + 1])0) j = j + 1。 num[j] = x。堆排序的平均性能較接近于最壞性能。排序示例見(jiàn)圖 。 int pos = 0。 i 。 } 陜西理工學(xué)院畢業(yè)設(shè)計(jì) 第 13 頁(yè) 共 80 頁(yè) temp[pos][order[pos]] = dat