基于姓名排序算法動態(tài)演示系統(tǒng)的設(shè)計與實現(xiàn)畢業(yè)設(shè)計說明書

畢業(yè)設(shè)計說明書基于姓名排序算法動態(tài)演示系統(tǒng)的設(shè)計與實現(xiàn)

[摘要]在有限的資源空間里,為了提高運算處理數(shù)據(jù)的速率，使用高效算法必不可少。本文以Java作為開發(fā)工具，設(shè)計與開發(fā)了基于姓名排序算法動態(tài)演示系統(tǒng)。該系統(tǒng)實現(xiàn)了插入排序（鏈表插入排序、直接插入排序、折半插入排序等）、交換排序、選擇排序、歸并排序、堆排序等算法的動態(tài)演示。系統(tǒng)界面美觀，操作簡單，可作為排序可視化教學演示軟件。[關(guān)鍵詞]Java；排序算法；動態(tài)演示TheDesignandImplementationofDynamicPresentationSystemsbasedonNameSortingAlgorithmAbstract：Inthespacelimitedresources,inordertoimprovetherateofoperationofthedataprocessing,theuseofefficientalgorithmisessential.Inthispaper,Javaasadevelopmenttool,designedanddevelopedbasedonthenameofsortingalgorithmdynamicpresentationsystems.Thesystemimplementsinsertionsort(listinsertionsort,insertionsort,binaryinsertionsort,etc.),exchangesort,selectionsort,mergesort,heapsort,suchasdynamicpresentationsalgorithm.Systeminterfaceisbeautiful,simpleoperation,canbeusedassortofteachingvisualpresentationsoftware.Keywords:Java;SortingAlgorithm;DynamicPresentation目錄TOC\o"1-3"\h\u30451引言 1228061系統(tǒng)背景及意義 2252831.1系統(tǒng)背景 2154691.2系統(tǒng)目的及意義 2303481.3開發(fā)工具介紹 2126172排序算法 5190612.1直接插入排序 5216862.2折半插入排序 6242792.3快速排序 618552.4選擇排序 8136532.5歸并排序 95352.6鏈表插入排序 1028658 11241712.8基數(shù)排序（MSD） 1234783系統(tǒng)設(shè)計 14266933.1系統(tǒng)模塊結(jié)構(gòu) 14224853.2模塊算法流程圖 1486324實現(xiàn) 21297034.1直接插入排序 21164204.2折半插入排序 21230114.3選擇排序 22319504.4快速排序 22174774.5歸并排序 2369574.6鏈表插入排序 2353124.7堆排序 24231854.8基數(shù)排序（MSD） 25105425測試 2630227總結(jié) 3423139致謝 3511499參考文獻 3621914科技外文文獻 3724230附錄A:基于姓名排序算法動態(tài)演示系統(tǒng)的設(shè)計與實現(xiàn)源代碼 4720076附錄B:使用說明書 80引言計算機技術(shù)的日益發(fā)展，其應(yīng)用早已不局限于簡單的數(shù)值運算。涉及到問題的分析、數(shù)據(jù)結(jié)構(gòu)框架、以及插入、刪除、排序查詢等復雜的非數(shù)值處理和操作?！皵?shù)據(jù)結(jié)構(gòu)”是計算機程序設(shè)計的重要基礎(chǔ)，也是計算機相關(guān)專業(yè)的一門重要基礎(chǔ)課程和核心課程。其加強對新數(shù)據(jù)類型的研究和尋找更適用更完善的數(shù)據(jù)結(jié)構(gòu)類型，也是今后數(shù)據(jù)結(jié)構(gòu)研究的重要內(nèi)容.抽象數(shù)據(jù)結(jié)構(gòu)類型的出現(xiàn)，使得在面向?qū)ο蟮恼Z言中,值和變量的類型不再單一，語言中的操作可以作用于多種類型的對象[1]。因此,要建立良好的數(shù)據(jù)結(jié)構(gòu)，首先對系統(tǒng)按某種原則進行分解，使系統(tǒng)中各模塊間獨立性強，依賴性小，結(jié)構(gòu)靈活,易于維護。然而，一個良好的分解，要依賴于抽象，只有對系統(tǒng)抽象到一定的程度，才能更好地分解。由于不以記錄為基礎(chǔ)的遞歸數(shù)據(jù)類型的出現(xiàn)，給許多高級應(yīng)用領(lǐng)域提供了更好地表達復雜數(shù)據(jù)對象的方法。數(shù)據(jù)結(jié)構(gòu)從一維二維向三維和多維數(shù)據(jù)結(jié)構(gòu)的研究意義以及如何實現(xiàn)它們等等，都是數(shù)據(jù)結(jié)構(gòu)今后研究的重要內(nèi)容[2]。數(shù)據(jù)結(jié)構(gòu)基本元素內(nèi)容的發(fā)展變化，為數(shù)據(jù)結(jié)構(gòu)的研究開拓了一個新的方向[1]。許多國內(nèi)外學者都把數(shù)據(jù)結(jié)構(gòu)的基本元素——數(shù)據(jù)，進一步擴充為知識,提出了知識的數(shù)據(jù)結(jié)構(gòu)概念,這樣就在更高層次上表示信息的知識代替了明顯表示信息邏輯數(shù)據(jù)，把表示方法更加復雜的知識代替了較為簡單的數(shù)據(jù),開拓了數(shù)據(jù)結(jié)構(gòu)研究的新方向.在原有的數(shù)據(jù)擴展到知識以后，除了基本元素結(jié)構(gòu)表示的不同需要研究以外，更多地應(yīng)加強對于基本元素間關(guān)系和運算以及它們的多種限定性和變化性方面的研究?？傊?，數(shù)據(jù)結(jié)構(gòu)由于其基本元素的內(nèi)容和本質(zhì)的不斷變化，它作為一門學科也要不斷變化和適應(yīng)新的要求。 各個應(yīng)用領(lǐng)域迫切需要解決的問題，也是當前數(shù)據(jù)結(jié)構(gòu)基本的研究內(nèi)容之一在計算機科學與信息融為一體的今天，研究數(shù)據(jù)結(jié)構(gòu)，既要從計算機技術(shù)的發(fā)展考慮，也要從信息技術(shù)的發(fā)展考慮，特別需要重視從理論到實際的轉(zhuǎn)化研究。許多諸如數(shù)據(jù)工程多媒介數(shù)據(jù)庫和知識工程等等新發(fā)展起來的學科，也都大量涉及封數(shù)據(jù)結(jié)構(gòu)的理論和技術(shù),迫切要求開拓與之對適應(yīng)的數(shù)據(jù)結(jié)構(gòu)[11]。對于初學者，它對程序設(shè)計思想的建立、提升有著重要的作用，既為后續(xù)的計算機課程奠定了一個較為扎實的基礎(chǔ)，又可提高分析問題和解決問題的能力，而排序更是“數(shù)據(jù)結(jié)構(gòu)”里面的核心內(nèi)容。排序算法的學習就是為以后利用計算機資源高效開發(fā)非數(shù)值處理的計算機程序打下堅定的理論、方法和技術(shù)基礎(chǔ)。因此，本文以java為開發(fā)語言，設(shè)計開發(fā)了基于姓名排序算法動態(tài)演示系統(tǒng)，有助于初學者的形象直觀的學習排序算法。1系統(tǒng)背景及意義由于排序在計算機圖形、計算機輔助設(shè)計、機器人、模式識別、基因排序工程及統(tǒng)計學等領(lǐng)域具有廣泛應(yīng)用，所以對排序的研究既有理論上的重要意義，又有實際應(yīng)用價值。再加上現(xiàn)在信息產(chǎn)業(yè)的迅速發(fā)展，信息的流通量越來越大，如此龐大并且雜亂無章的信息數(shù)據(jù)十分難以管理和查詢，就更加需要一種十分快捷而有效的編排手段來整理這些數(shù)據(jù)信息，讓我們的工作效率得以提高[4]。目的及意義隨著計算機技術(shù)的發(fā)展，各種排序算法不斷的被提出。排序算法在計算機科學中有非常重要的地位，且排序在人們的日常生活和學習、科研、生產(chǎn)等各個方面有著重要的應(yīng)用，因此掌握常用的排序算法是很有必要。在以后的發(fā)展中，排序?qū)ξ覀兊膶W習和生活的影響會逐漸增大，因此設(shè)計開發(fā)一個排序算法動畫演示系統(tǒng)，以提高自己對排序算法的掌握程度,并希望該系統(tǒng)有助于初學者直觀學習排序算法。此次畢業(yè)設(shè)計一方面使自己更好的掌握排序的知識，另一方面鍛煉一下獨立開發(fā)系統(tǒng)的能力。工具介紹(1)Java語言Java[8]是一種可以撰寫跨平臺應(yīng)用軟件的面向?qū)ο蟮某绦蛟O(shè)計語言，是由SunMicrosystems公司于1995年5月推出的Java程序設(shè)計語言和Java平臺（即tm"JavaEE,JavaME,JavaSE）的總稱。Java自面世后就非常流行，發(fā)展迅速，對C++語言形成了有力沖擊。Java技術(shù)具有卓越的通用性、高效性、平臺移植性和安全性，廣泛應(yīng)用于個人PC、數(shù)據(jù)中心、游戲控制臺、科學超級計算機、移動和互聯(lián)網(wǎng)，同時擁有全球最大的開發(fā)者專業(yè)社群。在全球云計算和移動互聯(lián)網(wǎng)的產(chǎn)業(yè)環(huán)境下，Java更具備了顯著優(yōu)勢和廣闊前景。Java分為三個體系JavaSE（J2SE）（Java2PlatformStandardEdition，java平臺標準版），JavaEE(J2EE)(Java2Platform,EnterpriseEdition，java平臺企業(yè)版)，JavaME(iew/7125.htm"J2ME)(Java2PlatformMicroEdition，java平臺微型版)。主要特性：Java語言是易學的[10]。Java語言的語法與C語言和C++語言很接近，使得大多數(shù)程序員很容易學習和使用Java。另一方面，Java丟棄了C++中很少使用的、很難理解的、令人迷惑的那些特性，如操作符重載、多繼承、自動的強制類型轉(zhuǎn)換。特別地，Java語言不使用指針，而是引用。并提供了自動的廢料收集，使得程序員不必為內(nèi)存管理而擔憂。Java語言是強制面向?qū)ο蟮腫8]。Java語言提供類、接口和繼承等原語，為了簡單起見，只支持類之間的單繼承，但支持接口之間的多繼承，并支持類與接口之間的實現(xiàn)機制（關(guān)鍵字為implements）。Java語言全面支持動態(tài)綁定，而C++語言只對w/161302.htm"虛函數(shù)使用動態(tài)綁定[10]。總之，Java語言是一個純的面向?qū)ο蟪绦蛟O(shè)計語言。Java語言是分布式的[10]。Java語言支持Internet應(yīng)用的開發(fā)，在基本的Java應(yīng)用編程接口中有一個網(wǎng)絡(luò)應(yīng)用編程接口（javanet），它提供了用于網(wǎng)絡(luò)應(yīng)用編程的類庫，包括URL、URLConnection、om/view/13870.htm"Socket、ServerSocket等。Java的RMI（遠程方法激活）機制也是開發(fā)分布式應(yīng)用的重要手段。Java語言是健壯的[10]。Java的強類型機制、tm"異常處理、垃圾的自動收集等是Java程序健壯性的重要保證。對指針的丟棄是Java的明智選擇。Java的安全檢查機制使得Java更具健壯性。Java語言是安全的。Java通常被用在網(wǎng)絡(luò)環(huán)境中，為此，Java提供了一個安全機制以防惡意代碼的攻擊。除了Java語言具有的許多安全特性以外，Java對通過網(wǎng)絡(luò)下載的類具有一個安全防范機制（類ClassLoader），如分配不同的名字空間以防替代本地的同名類、字節(jié)代碼檢查，并提供安全管理機制（類SecurityManager）讓Java應(yīng)用設(shè)置安全哨兵。Java語言是體系結(jié)構(gòu)中立的[10]。Java程序（后綴為java的文件）在Java平臺上被編譯為體系結(jié)構(gòu)中立的330.htm"字節(jié)碼格式（后綴為class的文件），然后可以在實現(xiàn)這個Java平臺的任何系統(tǒng)中運行。這種途徑適合于異構(gòu)的網(wǎng)絡(luò)環(huán)境和軟件的分發(fā)。Java語言是可移植的[10]。這種可移植性來源于體系結(jié)構(gòu)中立性，另外，Java還嚴格規(guī)定了各個基本數(shù)據(jù)類型的長度。Java系統(tǒng)本身也具有很強的可移植性，Java編譯器是用Java實現(xiàn)的，Java的運行環(huán)境是用e.baidu/view/3979609.htm"ANSIC實現(xiàn)的。Java語言是解釋型的[10]。如前所述，Java程序在Java平臺上被編譯為字節(jié)碼格式，然后可以在實現(xiàn)這個Java平臺的任何系統(tǒng)中運行。在運行時，Java平臺中的Java解釋器對這些字節(jié)碼進行解釋執(zhí)行，執(zhí)行過程中需要的類在聯(lián)接階段被載入到運行環(huán)境中。Java是性能略高的[10]。與那些解釋型的高級腳本語言相比，Java的性能還是較優(yōu)的。Java語言是原生支持多線程的[10]。在Java語言中，線程是一種特殊的對象，它必須由Thread類或其子（孫）類來創(chuàng)建。通常有兩種方法來創(chuàng)建線程：其一，使用型構(gòu)為Thread(Runnable)的構(gòu)造子將一個實現(xiàn)了Runnable接口的對象包裝成一個線程，其二，從Thread類派生出子類并重寫run方法，使用該子類創(chuàng)建的對象即為線程。值得注意的是Thread類已經(jīng)實現(xiàn)了Runnable接口，因此，任何一個線程均有它的run方法，而run方法中包含了線程所要運行的代碼。線程的活動由一組方法來控制。Java語言支持多個線程的同時執(zhí)行，并提供多線程之間的同步機制（關(guān)鍵字為synchronized）。Java語言是動態(tài)的[10]。Java語言的設(shè)計目標之一是適應(yīng)于動態(tài)變化的環(huán)境。Java程序需要的類能夠動態(tài)地被載入到運行環(huán)境，也可以通過網(wǎng)絡(luò)來載入所需要的類。這也有利于軟件的升級。另外，Java中的類有一個運行時刻的表示，能進行運行時刻的類型檢查。Java語言的優(yōu)良特性使得Java應(yīng)用具有無比的健壯性和10.htm"可靠性，這也減少了應(yīng)用系統(tǒng)的維護費用。Java對對象技術(shù)的全面支持和Java平臺內(nèi)嵌的API能縮短應(yīng)用系統(tǒng)的開發(fā)時間并降低成本。Java的編譯一次，到處可運行的特性使得它能夠提供一個隨處可用的開放結(jié)構(gòu)和在多平臺之間傳遞信息的低成本方式。特別是Java企業(yè)應(yīng)用編程接口（JavaEnterpriseAPIs）為企業(yè)計算及電子商務(wù)應(yīng)用系統(tǒng)提供了有關(guān)技術(shù)和豐富的類庫。JDK運行環(huán)境JDK[8](JavaDevelopmentKit)是Java語言的軟件開發(fā)工具包(SDK)。SE(J2SE)，standardedition，標準版，是我們通常用的一個版本，從JDK5.0開始，改名為JavaSE。EE(J2EE)，enterpriseedition，企業(yè)版，使用這種JDK開發(fā)J2EE應(yīng)用程序，從JDK5.0開始，改名為JavaEE。ME(J2ME)，microedition，主要用于移動設(shè)備、嵌入式設(shè)備上的java應(yīng)用程序，從JDK5.0開始，改名為JavaME。沒有JDK的話，無法編譯Java程序，如果想只運行Java程序，要確保已安裝相應(yīng)的JRE。JDK包含的基本組件包括：javac–編譯器，將源程序轉(zhuǎn)成字節(jié)碼。jar–打包工具，將相關(guān)的類文件打包成一個文件。javadoc–文檔生成器，從源碼注釋中提取文檔。jdb–debugger，查錯工具。java–運行編譯后的java程序（.class后綴的）。appletviewer：小程序瀏覽器，一種執(zhí)行HTML文件上的Java小程序的Java瀏覽器。Javah：產(chǎn)生可以調(diào)用Java過程的C過程，或建立能被Java程序調(diào)用的C過程的頭文件。Javap：Java反匯編器，顯示編譯類文件中的可訪問功能和數(shù)據(jù)，同時顯示字節(jié)代碼含義。Jconsole:Java進行系統(tǒng)調(diào)試和監(jiān)控的工具。(3)MyEclipse開發(fā)工具MyEclipse企業(yè)級工作平臺（MyEclipseEnterpriseWorkbench，簡稱MyEclipse）是對EclipseIDE的擴展，利用它我們可以在數(shù)據(jù)庫和JavaEE的開發(fā)、發(fā)布以及應(yīng)用程序服務(wù)器的整合方面極大的提高工作效率。它是功能豐富的JavaEE集成開發(fā)環(huán)境，包括了完備的編碼、調(diào)試、測試和發(fā)布功能，完整支持HTML,Struts,JSP,CSS,Javascript,Spring,SQL,Hibernate。MyEclipse是一個十分優(yōu)秀的用于開發(fā)Java,J2EE的Eclipse插件集合，MyEclipse的功能非常強大，支持也十分廣泛，尤其是對各種開源產(chǎn)品的支持十分不錯。MyEclipse目前支持JavaServlet,AJAX,JSP,JSF,Struts,Spring,Hibernate,EJB3,JDBC數(shù)據(jù)庫鏈接工具等多項功能?？梢哉fMyEclipse是幾乎囊括了目前所有主流開源產(chǎn)品的專屬eclipse開發(fā)工具。根據(jù)官方最新消息，MyEclipse2013已經(jīng)正式發(fā)布！MyEclipse2013[2]支持HTML5、JQuery和主流的Javascript庫。隨著MyEclipse2013支持Html5，你可以添加音頻、視頻和API元素到你的項目，從而為移動設(shè)備創(chuàng)建復雜的Web應(yīng)用程序。你甚至還可以通過HTML5可視化設(shè)計器設(shè)計令人難以置信的用戶界面。同時，隨著MyEclipse2013支持JQuery，你可以通過插件提升性能，并添加動畫效果到設(shè)計中。2排序算法(1)基本原理假設(shè)待排序的n個記錄{L0，L1，…，Ln}順序存放在數(shù)組中，直接插入法在插入記錄Li(i=1，2，…，n-1)時，記錄被劃分為兩個區(qū)間[L0,Li-1]和[Li+1,Ln-1],其中，前一個子區(qū)間已經(jīng)排好序，后一個子區(qū)間是當前未排序的部分，將關(guān)鍵碼Ki與Ki-1Ki-2，…，K0依次比較，找出應(yīng)該插入的位置，將記錄Li插，然后將剩下的i-1個元素按關(guān)鍵詞大小依次插入該有序序列，沒插入一個元素后依然保持該序列有序，經(jīng)過i-1趟排序后即成為有序序列。每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當位置，直到全部記錄插入完成為止，為了在查找插入位置的過程中避免數(shù)組下標出界，在l[0]處設(shè)置監(jiān)視哨[1]。排序示例見圖2.1。圖2.1直接插入排序示例(2)算法描述對字符串順序鏈表src作直接插入排序,返回值為空。publicvoidinsertSort(String[]src){;i++){ if(src[i]pareTo(src[i-1])<0){ src[0]=src[i]; src[i]=src[i-1]; intj=i-2; for(;src[0]pareTo(src[j])<0;j--){ src[j+1]=src[j]; } src[j+1]=src[0]; } } }(3)時間復雜度分析直接插入排序算法必須進行n-1趟。最好情況下，即初始序列有序，執(zhí)行n-1趟，但每一趟只比較一次，移動元素兩次，總的比較次數(shù)是(n-1)，移動元素次數(shù)是2(n-1)。因此最好情況下的時間復雜度就是O(n)。最壞情況(非遞增)下，最多比較i次，因此需要的比較次數(shù)是：所以，時間復雜度為O(n2)。(1)基本思想是對直接插入排序算法的一種改進，由于排序算法過程中，就是不斷的依次將元素插入前面已排好序的序列中。由于前半部分為已排好序的數(shù)列，這樣我們不用按順序依次尋找插入點，可以采用折半查找的方法來加快尋找插入點的速度[2]。(2)算法描述對字符串順序鏈表src作折半插入排序,返回值為空。publicvoidbinaryInsertionSort(String[]src){ for(inti=2;i<src.length;i++){ //將src[i]暫存在src[0] src[0]=src[i]; intlow=1,high=i-1; while(low<=high){ intm=(low+high)/2; if(src[0]pareTo(src[m])<0){// high=m-1; }else{ low=m+1; } } //記錄后移 for(intj=i-1;j>=high+1;j--){ src[j+1]=src[j]; } //插入 src[high+1]=src[0]; } }(3)時間空間復雜度折半插入排序算法是一種穩(wěn)定的排序算法，比直接插入算法明顯減少了關(guān)鍵字之間比較的次數(shù)，因此速度比直接插入排序算法快，但記錄移動的次數(shù)沒有變，所以折半插入排序算法的時間復雜度仍然為O(n^2)，與直接插入排序算法相同。附加空間O(1);(1)基本原理對起泡排序的一種改進。它的基本思想是，通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小則可分別對兩部分記錄繼續(xù)進行排序，以達到整個序列有序。假設(shè)待排序的序列為{K.r[s],K.r[s+1],...,K.r[t]},首先任意選取一個記錄（通常選第一個）作為支點，然后按下述原則重新排列其余記錄：將所有關(guān)鍵字比它小的記錄都安置在它的位置之前，將所有關(guān)鍵字較它打的記錄都安置在它的位置之后。由此可以將位置i作分界線，將序列{K.r[s],K.r[s+1],...,K.r[t]}分割成兩個子序列{K.r[s],K.r[s+1],...,K.r[i-1]}和{K.r[i+1],K.r[s+1],...,K.r[t]}。這個過程稱一趟快速排序[11]。排序示例見圖2.2。圖2.2快速排序示例(2)算法描述交換順序表L中子表l[low...high]的記錄，樞軸記錄到位，并返回其所在位置，此時在它之前（后）的記錄均不大（?。┯谒?。publicintpartition(String[]l,intlow,inthigh) { //用字表的第一個記錄軸的記錄 l[0]=l[low]; //軸記錄關(guān)鍵字 Stringpivotkey=l[low]; //從表的兩端交替向中間掃描 while(low<high) { //將比軸記錄小的記錄移到低端 while(low<high&&l[high]pareTo(pivotkey)>=0) { --high; } //將比軸記錄大的記錄移到高端 l[low]=l[high]; while(low<high&&l[low]pareTo(pivotkey)<=0) { ++low; } l[high]=l[low]; } //軸記錄到位 l[low]=l[0]; //返回軸的位置 returnlow; }(3)時間復雜度分析如果每一次分劃操作后，左、右兩個子序列的長度基本相等，則快速排序的效率最高，其最好情況時間復雜度為O(nlog2n)；反之，如果每次分劃操作所產(chǎn)生的兩個子序列，其中之一為空序列，此時，快速排序效率最低，其最壞情況時間復雜度為O(n2)。如果選擇左邊第一個元素為主元，則快速排序的最壞情況發(fā)生在原始序列正向有序或反向有序時。快速排序的平均情況時間復雜度為O(nlog2n)。(1)基本原理待排序的一組數(shù)據(jù)元素中，選出最小的一個數(shù)據(jù)元素與第一個位置的數(shù)據(jù)元素交換；然后在剩下的數(shù)據(jù)元素當中再找最小的與第二個位置的數(shù)據(jù)元素交換，循環(huán)到只剩下最后一個數(shù)據(jù)元素為止，依次類推直到所有記錄[12]。排序示例見圖2.3。圖2.3選擇排序示例(2)算法描述對字符串順序鏈表src作選擇排序，返回值為空。publicvoidselectSort(String[]src){ for(inti=0;i<src.length;i++){ intj=selectMinKey(src,i); if(j!=i){ Stringtemp=src[i]; src[i]=src[j]; src[j]=temp; }}}(3)時間復雜度分析該算法運行時間與元素的初始排列無關(guān)。不論初始排列如何，該算法都必須執(zhí)行n-1趟，每趟執(zhí)行n-i-1次關(guān)鍵字的比較，這樣總的比較次數(shù)為：所以，簡單選擇排序的最好、最壞和平均情況的時間復雜度都為O(n2)。(1)基本原理是將兩個或兩個以上的有序表組合成一個有序的表。利用歸并思想實現(xiàn)排序，假設(shè)初始序列含有n/2個長度為2或1的有序子列表；再兩兩歸并，，如此重復直到得到長度為n的有序列表為止；排序示例見圖2.4。圖2.4歸并排序示例(2)算法描述將有序順序鏈表sr[i...m]和sr[m+1...n]歸并為有序的sr[i...n]privatevoidmerge(String[]sr,ints,intm,intt){ String[]tmp=newString[t-s+1];//臨時數(shù)據(jù)存儲 inti=s,k=0,j=m+1; for(;i<=m&&j<=t;k++) { if(sr[i]pareTo(sr[j])<0){ tmp[k]=sr[i]; i++; }else{ tmp[k]=sr[j]; j++; } }//forend if(i<=m){//將剩余的sr[i...m]復制到tmp中 for(;i<=m;i++){ tmp[k]=sr[i]; k++; }//forend }//ifend if(j<=t){//將剩余的sr[j...t]復制到tmp中 for(;j<=t;j++){ tmp[k]=sr[j]; k++; }//forend }//ifend System.arraycopy(tmp,0,sr,s,tmp.length); }(3)時間復雜度分析一趟歸并排序的操作是，調(diào)用n/2h次算法merge將sr[1...n]中前后相鄰且長度為h的有序段進行兩兩歸并得到前后相鄰，長度為2h的有序段并存放在Tr[1...n]中整個歸并排序需進行l(wèi)og2n趟，可見需要和待排序等數(shù)量的輔助空間，其時間復雜度為O(nlogn)基本原理設(shè)數(shù)組中下標為0的分量為表頭結(jié)點，并令表頭結(jié)點記錄的關(guān)鍵字取最大整數(shù)MAX，則表的插入過程描述如下：首先將靜態(tài)鏈表中的數(shù)組下標為1的分量和表頭結(jié)點構(gòu)成一個循環(huán)鏈表，然后依次將下標為2至n的分量按記錄關(guān)鍵字非遞減有序插入到循環(huán)鏈表中[1]。排序示例見圖2.5。圖2.5鏈表插入排序示例(2)算法描述對有序靜態(tài)鏈表nodes作鏈表插入排序，返回值為空。privatevoidupdateNext(Node[]nodes){ for(inti=2;i<nodes.length;i++){ intq=0; intp=nodes[0].getNext(); while(nodes[i].getValue()pareTo(nodes[p].getValue())>0){ q=p; p=nodes[p].getNext(); } nodes[q].setNext(i); nodes[i].setNext(p); } }(3)時間復雜度分析和直接插入排序相比，不同之處僅是以修改2n次指針值代替移動記錄，排序過程中所需進行的關(guān)鍵字間的比較次數(shù)相同，因此，表插入排序的時間復雜度仍是O(n2)；(1)基本原理堆含義表明，所有非終點結(jié)點的值均不大于（或不小于）其左右孩子結(jié)點；若輸出堆頂?shù)淖钚≈抵?，使得剩余n-1個元素的序列重又建成一個堆，則得到n個元素中的次小值，如此反復執(zhí)行，便得到一個有序序列；堆排序解決2個問題：1.如何由一個無序序列建成一個堆；2.如何在輸出堆頂之后，調(diào)整剩余元素成為一個新的堆；堆調(diào)整示例見圖。圖2.6堆調(diào)整示例(2)算法描述 已知字符串順序鏈表num[s...m]中記錄的關(guān)鍵字除num[s]之外均滿足堆的定義，本函數(shù)調(diào)整num[s]的關(guān)鍵字，使num[s...m]成為一個大頂堆。publicvoidadjustHeap(String[]num,ints,intt) { inti=s; for(intj=2*i;j<=t;j=2*j){ if(j<t&&num[j]pareTo(num[j+1])<0) j=j+1;//找出較大者把較大者給num[i] if(num[i]pareTo(num[j])>0) break; Stringx=num[i]; num[i]=num[j]; num[j]=x; i=j; } }(3)時間復雜度分析堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構(gòu)成，它們均是通過調(diào)用Heapify實現(xiàn)的。堆排序的最壞時間復雜度為O(nlogn)。堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序是不穩(wěn)定的，算法時間復雜度O(nlogn)。2.8基數(shù)排序（MSD）基本原理是一種借助多關(guān)鍵字排序的思想對單邏輯關(guān)鍵字進行排序的方法；MSD：先對最主要位關(guān)鍵字K0進行排序，將序列分成若干子序列，每個子序列中的記錄都具有相同的K0值，然后分別就每個子序列對關(guān)鍵字K1進行排序，按K1值得不同再分成若干更小的子序列，依次重復直至每個子序列中都有相同的關(guān)鍵字[1]。排序示例見圖2.7。圖2.7MSD排序示例(2)算法描述對字符串順序鏈表data每個關(guān)鍵字第power的字符比較排序，返回值為空。publicvoidmsd(String[]data,intpower){ String[][]temp=newString[26][data.length]; int[]order=newint[26]; intpos=0; intk=0; if(power<0) return; for(inti=0;i<data.length;i++){ if(data[i]==null||"".equals(data[i])) break; if(power<data[i].length()){ pos=(int)data[i].charAt(power)-97; }else{ pos=0; } temp[pos][order[pos]]=data[i]; order[pos]++; } ++power; for(inti=0;i<26;i++){ if(order[i]>1&&power<getStringMaxLength(temp[i])){ path.setHigh(1); msd(temp[i],power);//msdineverysiblingbucks } } for(inti=0;i<26;i++){ for(intj=0;j<data.length;j++){ if(temp[i][j]!=null){ data[k++]=temp[i][j];//regainthesortednumbers } } } }(3)時間復雜度分析對于n個記錄（假設(shè)每個記錄含d個關(guān)鍵字，每個關(guān)鍵字的取值范圍為rd個值），時間復雜度為O(d(n+rd)),其中每一趟分配的時間復雜度為O(n),輔助存儲O(rd);

3系統(tǒng)設(shè)計模塊結(jié)構(gòu)根據(jù)需求分析，按功能劃分8個模塊，分別是：鏈表插入排序模塊、直接插入排序模塊、折半插入排序模塊、選擇排序模塊、歸并排序模塊、堆排序模塊、基數(shù)排序模塊。排序算法動態(tài)演示系統(tǒng)功能模塊結(jié)構(gòu)圖如圖3.1所示。排序算法動態(tài)演示系統(tǒng)排序算法動態(tài)演示系統(tǒng)鏈

表

插

入

排

序直

接

插

入

排

序折

半

插

入

排

序交

換

排

序選

擇

排

序歸

并

排

序堆

排

序基

數(shù)

排

序圖3.1系統(tǒng)模塊結(jié)構(gòu)圖3.2模塊算法流程圖(1)直接插入排序直接插入排序算法流程圖如圖3.2所示。圖3.2直接插入排序算法流程圖(2)折半插入排序折半插入排序算法流程圖如圖3.3所示。圖3.3折半插入排序算法流程圖(3)選擇排序選擇排序算法流程圖如圖3.4所示。圖3.4選擇排序算法流程圖(4)快速排序快速排序算法流程圖如圖3.5所示。圖3.5快速排序算法流程圖(5)歸并排序歸并排序算法流程圖如圖3.6所示。圖3.6歸并排序算法流程圖(6)堆排序堆排序算法流程圖如圖3.7所示。圖3.7堆排序算法流程圖(7)鏈表插入排序鏈表插入排序算法流程圖如圖3.8所示。圖3.8鏈表插入排序算法流程圖(8)基數(shù)（MSD）排序基數(shù)（MSD）排序算法流程圖如圖3.9所示。圖3.9基數(shù)MSD排序算法流程圖

4實現(xiàn)4.1直接插入排序?qū)⒆址當?shù)組封裝為Vector<Unit>，同時利用GUI在ContentPanel（中間JPanel）中繪制數(shù)據(jù)；將SortUtils.copyUnit()切入到排序代碼中，完成數(shù)組拷貝與賦值。AccessoryPanel（右邊JPanel）中加入JList，通過JList.setSelectedIndices(int[]i)完成代碼跟隨。將MyFactory.getAccessoryPanel().setSelectIndexs(newint[]{});該方法切入到排序代碼完成排序算法每一步實現(xiàn)效果。實現(xiàn)代碼如下：publicvoidinsertSortToShow(String[]src,intindex){ units=DataUtil.getUnitDataForBase(src); MyFactory.getContentPanel().setUnits(units); if(HanziToPinyin.getPingYin(src[index])pareTo(HanziToPinyin.getPingYin(src[index-1]))<0){ src[0]=src[index]; //數(shù)組拷貝及代碼跟隨 src[index]=src[index-1]; intj=index-2; for(;HanziToPinyin.getPingYin(src[0])pareTo(HanziToPinyin.getPingYin(src[j]))<0;j--){ //找出插入位置 } src[j+1]=src[0]; //src[0]插入到插入位置 } repaintUnit(500); }4.2折半插入排序?qū)⒆址當?shù)組封裝為Vector<Unit>，同時利用GUI在ContentPanel（中間JPanel）中繪制數(shù)據(jù)；將SortUtils.copyUnit()切入到排序代碼中，完成數(shù)組拷貝與賦值；initUnits(units,low,high)切入到排序代碼中完成折半查找過程的繪制。AccessoryPanel（右邊JPanel）中加入JList，通過JList.setSelectedIndices(int[]i)完成代碼跟隨。將MyFactory.getAccessoryPanel().setSelectIndexs(newint[]{});該方法切入到排序代碼完成排序算法每一步實現(xiàn)效果。實現(xiàn)代碼如下：publicvoidbinaryInsertionSortToShow(String[]src,intindex){ units=DataUtil.getUnitDataForBase(src);//獲取顯示數(shù)據(jù) MyFactory.getContentPanel().setUnits(units); //將src[i]暫存在src[0] src[0]=src[index]; //數(shù)組拷貝及代碼跟隨 intlow=1,high=index-1; //--代碼跟隨 MyFactory.getAccessoryPanel().setSelectIndexs(newint[]{2}); //在src[low...high]中折半查找 SortUtils.refreshUnit(units);//初始化Units initUnits(units,low,high); //延遲time后重繪 repaintUnit(1000); while(low<=high){ 找出插入位置 } MyFactory.getContentLayoutPanel().repaint(); //記錄后移 for(intj=index-1;j>=high+1;j--){記錄后移 } 將src[0]插入到指定位置 }將字符串數(shù)組封裝為Vector<Unit>，同時利用GUI在ContentPanel（中間JPanel）中繪制數(shù)據(jù)；將SortUtils.changeUnit()切入到排序代碼中，完成數(shù)組拷貝與賦值。AccessoryPanel（右邊JPanel）中加入JList，通過JList.setSelectedIndices(int[]i)完成代碼跟隨。將MyFactory.getAccessoryPanel().setSelectIndexs(newint[]{});該方法切入到排序代碼完成排序算法每一步實現(xiàn)效果。實現(xiàn)代碼如下：publicvoidselectSortToShow(String[]src,intindex)throwsSortPlayingException{ units=DataUtil.getUnitDataForBase(src);//獲取顯示數(shù)據(jù) MyFactory.getContentPanel().setUnits(units); //--代碼跟隨 MyFactory.getAccessoryPanel().setSelectIndexs(newint[]{1}); intj=selectMinKeyToShow(src,index); if(j!=index){ Stringtemp=src[index]; src[index]=src[j]; src[j]=temp; //--代碼跟隨 MyFactory.getAccessoryPanel().setSelectIndexs(newint[]{3,4,5}); changeUnit(units,index,j); } }將字符串數(shù)組封裝為Vector<Unit>，同時利用GUI在ContentPanel（中間JPanel）中繪制數(shù)據(jù)；將SortUtils.copyUnit()切入到排序代碼中，完成數(shù)組拷貝與賦值。AccessoryPanel（右邊JPanel）中加入JList，通過JList.setSelectedIndices(int[]i)完成代碼跟隨。將MyFactory.getAccessoryPanel().setSelectIndexs(newint[]{});該方法切入到排序代碼完成排序算法每一步實現(xiàn)效果。實現(xiàn)代碼如下：publicintpartitionToShow(String[]l,intlow,inthigh) { SortUtils.repaintUnit(500); //用字表的第一個記錄軸的記錄 l[0]=l[low]; //--代碼跟隨 MyFactory.getAccessoryPanel().setSelectIndexs(newint[]{1}); SortUtils.copyUnit(units,units.get(low),units.get(0));//顯示內(nèi)存處理 //軸記錄關(guān)鍵字 Stringpivotkey=l[low]; //--代碼跟隨 MyFactory.getAccessoryPanel().setSelectIndexs(newint[]{2}); //從表的兩端交替向中間掃描 while(low<high) { 從表的兩端交替向中間掃描 } 將l[0]插入到指定位置 returnlow; }將字符串數(shù)組封裝為Vector<Unit>，同時利用GUI在ContentPanel（中間JPanel）中繪制數(shù)據(jù)；將movingUnit()完成數(shù)組的移動與交換。AccessoryPanel（右邊JPanel）中加入JList，通過JList.setSelectedIndices(int[]i)完成代碼跟隨。將MyFactory.getAccessoryPanel().setSelect-Indexs(newint[]{});該方法切入到排序代碼完成排序算法每一步實現(xiàn)效果。實現(xiàn)代碼如下：privatevoidmergeToShow(String[]sr,ints,intm,intt) { String[]tmp=newString[t-s+1];//臨時數(shù)據(jù)存儲 Vector<Unit>tmpUnits=newVector<Unit>(t-s+1); intcurx=units.get(s).getPoint().x; inti=s,k=0,j=m+1; //--代碼跟隨 MyFactory.getAccessoryPanel().setSelectIndexs(newint[]{2}); for(;i<=m&&j<=t;k++) { 將sr[i...m] 和sr[j...t]歸并 }//forend if(i<=m)//將剩余的sr[i...m]復制到tmp中 { .將剩余的sr[i...m]復制到tmp中 }//ifend if(j<=t)//將剩余的sr[j...t]復制到tmp中 { 將剩余的sr[j...t]復制到tmp中 }//ifend System.arraycopy(tmp,0,sr,s,tmp.length); //--代碼跟隨 MyFactory.getAccessoryPanel().setSelectIndexs(newint[]{20});/r