VC實(shí)現(xiàn)排序算法動(dòng)態(tài)演示系統(tǒng)

PAGEPAGE19摘要排序是計(jì)算機(jī)科學(xué)的一個(gè)重要領(lǐng)域，并廣泛應(yīng)用于計(jì)算機(jī)圖形、計(jì)算機(jī)輔助設(shè)計(jì)、機(jī)器人、模式識(shí)別及統(tǒng)計(jì)學(xué)等領(lǐng)域。本文選擇其中最基本也是最常用的一些算法進(jìn)行討論，介紹它們的基本思想和實(shí)現(xiàn)過(guò)程，分析各種排序算法的性能，并且采用VS2008作為開(kāi)發(fā)工具以windowsSDK為編程環(huán)境動(dòng)態(tài)地演示算法的排序過(guò)程。排序方法大致可分為插入排序、交換排序、選擇排序、歸并排序四大類，他們的性能分析參數(shù)則以時(shí)間復(fù)雜度、空間復(fù)雜度和穩(wěn)定性為主。其中屬于交換排序的快速排序方法在平均時(shí)間上最省，但在最壞情況下不如堆排序和歸并排序，堆排序和歸并排序在所需時(shí)間和所需空間上成互補(bǔ)情況；幾種時(shí)間復(fù)雜度為O(n2)的簡(jiǎn)單排序則是在穩(wěn)定性上占有優(yōu)勢(shì)而且實(shí)現(xiàn)方法簡(jiǎn)單，在序列基本有序和需排序?qū)ο蟊容^少的情況下，直接插入排序是最佳排序；總體上來(lái)講，沒(méi)有哪一種排序方法是絕對(duì)優(yōu)勢(shì)的，在不同情況下需要選擇合適的排序方法，如果需要還可以混合使用已達(dá)到效果最佳。排序算法的演示系統(tǒng)由C語(yǔ)言調(diào)用windowsAPI完成圖形編程，采用數(shù)據(jù)線的虛實(shí)線變換和操作線的移動(dòng)交互演示，以定時(shí)器為基數(shù)刷新圖像達(dá)到動(dòng)態(tài)演示的效果。軟件還可以輸出排序過(guò)程中的數(shù)據(jù)和排序后的數(shù)據(jù)，以及顯示當(dāng)前排序方法的性能參數(shù)等，最大化地做到人性化人機(jī)交互。軟件在教學(xué)或者排序方法學(xué)習(xí)方面都有很好的用途?！娟P(guān)鍵詞】插入排序交換排序選擇排序歸并排序時(shí)間復(fù)雜度空間復(fù)雜度windowsSDKABSTRACTSortingisanimportantareaofcomputerscience,andiswidelyusedincomputergraphics,computerassistdesign,robotics,patternrecognitionandstatisticsandotherfields.Thischoiceofwhichsomeofthemostbasicandmostcommonlyusedalgorithmsdiscussed,introducingtheirbasicideasandimplementationprocess,toanalyzetheperformanceofsortingalgorithms,andusingVS2008windowsSDKasadevelopmenttoolfortheprogrammingenvironmenttodynamicallydemonstratprocessofsortingalgorithms.

Sortingmethodcanbedividedintoinsertionsort,exchangesort,selectionsort,mergesortfourcategories,andtheirperformanceanalysisparametersZeyitimecomplexity,spacecomplexityandstabilityoriented.Whichissortofthequicksortmethodforexchangingtheaveragetimemostprovinces,butnotasgoodasintheworstcaseheapsortandmergesort,heapsortandmergesortintimeandspacerequiredascomplementarysituation;severaltimecomplexitydegreeisO(n2)sortingisasimpleadvantageinstabilityandtherealizationofthemethodissimple,orderlyandinthesequenceofbasicobjectstobesortedrelativelyfewcases,directinsertionsortisthebestsort;generallyspeaking,noWhichsortisanabsoluteadvantageindifferentsituationsneedtoselecttheappropriatesortingmethod,ifnecessarytoachievethebestresultshavebeenmixed.

ThedemonstrationsystemconsistsofsortingalgorithmcalledC-completegraphwindowsAPIprogramming,brokenandsolidlineswithdatalinesandoperatinglinestransformthemobileinteractivedemotothetimertorefreshtheimageasabasetoachievedynamicpresentationoftheresults.Softwarecanalsoexportthedatainthesortingprocessandthesorteddata,andshowthecurrentsortmethodperformanceparameters,maximizingtheuser-friendlyhuman-computerinteractiondo.Rankingmethodinteachingsoftware,orhaveaverygoodlearningpurposes.【Keywords】ExchangedSortSelectionSortInsertionSortMergeSortSpacecomplexityTimecomplexitywindowsSDK

目錄7289前言 4TOC\o"1-3"\h\u7289第一章排序算法的研究現(xiàn)狀 53864第二章排序算法的實(shí)現(xiàn)方法及性能分析 7696第一節(jié)插入排序 713709一、直接插入排序 725441二、希爾排序 930882第二節(jié)交換排序 1118324一、冒泡排序 1111723二、快速排序 1217517第三節(jié)選擇排序 147525一、直接選擇排序 154568二、堆排序 1529857第四節(jié)歸并排序 184429一、兩路歸并算法 187137二、歸并排序 192895第五節(jié)各種排序算法的比較討論 2115544第三章排序算法的動(dòng)態(tài)演示 2325044第一節(jié)編程環(huán)境及語(yǔ)言 2323854一、編程環(huán)境的選擇 239988二、編程語(yǔ)言和工具 2325089第二節(jié)動(dòng)態(tài)演示程序界面實(shí)現(xiàn) 2417147一、界面及功能介紹 246125二、主界面的創(chuàng)建 2626723第三節(jié)排序算法動(dòng)態(tài)演示實(shí)現(xiàn) 299291一、實(shí)現(xiàn)動(dòng)態(tài)演示的方法 2922313二、實(shí)現(xiàn)動(dòng)態(tài)演示步驟 2932640三、具體排序算法實(shí)現(xiàn)的過(guò)程 309628四、本章結(jié)束語(yǔ) 3228693結(jié)論 3319377致謝 3429558參考文獻(xiàn) 3518760附錄 3610656一、英文原文： 3618332二、英文翻譯： 3717225三、源程序：(部分) 38第一章緒論第一節(jié)課題研究背景排序是計(jì)算機(jī)科學(xué)中最重要的研究問(wèn)題之一,它在計(jì)算機(jī)圖形、計(jì)算機(jī)輔助設(shè)計(jì)、機(jī)器人、模式識(shí)別及統(tǒng)計(jì)學(xué)等領(lǐng)域具有廣泛的應(yīng)用。由于它固有的理論上的重要性,2000年它被列為對(duì)科學(xué)和工程計(jì)算的研究與實(shí)踐影響最大的10大問(wèn)題之一。排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。作為排序依據(jù)的數(shù)據(jù)項(xiàng)稱為“排序碼”，也即數(shù)據(jù)元素的關(guān)鍵碼。為了便于查找，通常希望計(jì)算機(jī)中的數(shù)據(jù)表是按關(guān)鍵碼有序排列的。若關(guān)鍵碼是主關(guān)鍵碼，則對(duì)于任意待排序序列，經(jīng)排序后得到的結(jié)果是唯一，這是因?yàn)榫哂邢嗤P(guān)鍵碼得數(shù)據(jù)元素，這些元素在排序結(jié)束中，它們之間的位置關(guān)系與排序前不能保持一致。排序算法是在整個(gè)計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語(yǔ)。排序算法是計(jì)算機(jī)程序設(shè)計(jì)、數(shù)據(jù)庫(kù)、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。在日常生活中經(jīng)常需要對(duì)所收集到的各種數(shù)據(jù)信息進(jìn)行處理，這些數(shù)據(jù)處理中經(jīng)常用到的核心運(yùn)算就是排序。例如圖書(shū)管理員將書(shū)籍按照編號(hào)排序放置在書(shū)架上，方便讀者查找；打開(kāi)計(jì)算機(jī)的資源管理器，可以選擇按名稱、大小、類型等來(lái)排列圖標(biāo)。排序已被廣泛應(yīng)用在幾乎所有的領(lǐng)域。在當(dāng)今的計(jì)算機(jī)系統(tǒng)中，花費(fèi)在排序上的時(shí)間占CPU運(yùn)行時(shí)間的很大比重。有資料表明，在一些商用計(jì)算機(jī)上，用在排序上的CPU時(shí)間達(dá)到20%至60%。所以高效的排序算法是當(dāng)今所需，而對(duì)現(xiàn)有的常用排序算法的性能分析和對(duì)比也有一定的作用。若對(duì)任意的數(shù)據(jù)元素序列使用某個(gè)排序方法，對(duì)它按關(guān)鍵碼進(jìn)行排序：若相同關(guān)鍵碼元素間的位置關(guān)系，排序前與排序后保持一致，稱為排序方法是穩(wěn)定的；而不能保持一致的排序方法則稱為不穩(wěn)定的。隨著計(jì)算機(jī)技術(shù)的日益發(fā)展，其應(yīng)用早已不局限于簡(jiǎn)單的數(shù)值運(yùn)算。而涉及到問(wèn)題的分析、數(shù)據(jù)結(jié)構(gòu)框架的設(shè)計(jì)以及插入、刪除、排序、查找等復(fù)雜的非數(shù)值處理和操作。排序算法的學(xué)習(xí)就是為以后利用計(jì)算機(jī)資源高效地開(kāi)發(fā)非數(shù)值理的計(jì)算機(jī)程序打下堅(jiān)實(shí)的理論、方法和技術(shù)基礎(chǔ)。資料表明，在當(dāng)今的計(jì)算機(jī)系統(tǒng)中，有50％以上的CPU時(shí)間是用在排序數(shù)據(jù)上的。目前人們已經(jīng)提出了許多不同的排序算法，本文選擇其中最基本也是最常用的一些算法進(jìn)行討論，介紹它們的基本思想和實(shí)現(xiàn)過(guò)程，分析各種算法的時(shí)間與空間復(fù)雜度，以清晰描述排序演示系統(tǒng)。作為計(jì)算機(jī)科學(xué)中一項(xiàng)復(fù)雜而重要的技術(shù)，排序一直是計(jì)算機(jī)領(lǐng)域內(nèi)人們感興趣的課題，尋找速度快、附加存儲(chǔ)空間開(kāi)銷小的高效排序算法也一直是人們追尋的目標(biāo)。本文討論整數(shù)數(shù)組元素的排序，分析幾種常見(jiàn)排序算法并進(jìn)行比較。排序是程序設(shè)計(jì)中非常重要的內(nèi)容，每一種程序設(shè)計(jì)語(yǔ)言中都涉及到排序，它的功能是將一組無(wú)序的數(shù)據(jù)序列變成有序的數(shù)據(jù)序列，結(jié)果一般只有兩種情況：數(shù)據(jù)從大到小排列或者從小到大排列。排序的算法有很多種，常用的有三種，即冒泡排序、選擇排序和插入排序。要判斷排序算法的優(yōu)劣，一般有兩個(gè)標(biāo)準(zhǔn)：一是算法執(zhí)行所需的時(shí)間，又稱時(shí)間復(fù)雜度；二是算法所需的存儲(chǔ)空間，又稱空間復(fù)雜度。排序算法的優(yōu)劣將直接影響到程序的性能。隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，排序（Sorting）仍將成為計(jì)算機(jī)科學(xué)的一個(gè)重要組成部分。早期計(jì)算機(jī)多用于進(jìn)行簡(jiǎn)單的數(shù)值計(jì)算，輸入和輸出的數(shù)據(jù)量不大，數(shù)據(jù)元素之間的關(guān)系較為簡(jiǎn)單，數(shù)據(jù)處理時(shí)間較長(zhǎng)，但是自從第一臺(tái)計(jì)算機(jī)誕生，隨著操作系統(tǒng)從簡(jiǎn)單到復(fù)雜，從低級(jí)到高級(jí)的發(fā)展，排序速度也越來(lái)越快，當(dāng)處理大批量數(shù)據(jù)，特別是成千上萬(wàn)的數(shù)據(jù)時(shí)，時(shí)間也挺長(zhǎng)，但是效率已相當(dāng)高了。操作系統(tǒng)大概經(jīng)歷了以下幾個(gè)階段：一、手工操作階段；二、早期批量處理階段；三、管理程序階段；四、多道程序設(shè)計(jì)與多道批處理系統(tǒng)。有了這許多硬件和軟件的支持，排序算法的實(shí)現(xiàn)就有了強(qiáng)大的支撐力，從而為我們的計(jì)算機(jī)科學(xué)注入了活力。計(jì)算機(jī)已經(jīng)深入到人類社會(huì)的各個(gè)領(lǐng)域，其應(yīng)用已經(jīng)不再局限于科學(xué)計(jì)算，而更多用于控制，管理及數(shù)據(jù)處理等非數(shù)值計(jì)算的處理工作。另外，計(jì)算機(jī)加工處理的對(duì)象由純粹的數(shù)值發(fā)展到字符，表格和圖象等各種具有一定結(jié)構(gòu)的數(shù)據(jù)，這就必須分析待處理對(duì)象的特性以及各處理對(duì)象之間存在的關(guān)系，而排序是其中必不可少的一份子。所以展望計(jì)算機(jī)世界，數(shù)據(jù)結(jié)構(gòu)是它的支持框架，而作為數(shù)據(jù)結(jié)構(gòu)中排序一大塊，其作用是非同小可的。課題研究目的和意義排序分為兩類：內(nèi)部排序和外部排序。內(nèi)部排序：是指待排序列完全存放在內(nèi)存中所進(jìn)行的排序過(guò)程，適合不太大的元素序列。外部排序：是指排序過(guò)程中還需訪問(wèn)外存儲(chǔ)器，足夠大的元素序列，因不能完全放入內(nèi)存，只能使用外部排序。當(dāng)然，本文則以內(nèi)部排序?yàn)橹攸c(diǎn)討論。排序算法在日常生活中特別是計(jì)算機(jī)上有舉足輕重的作用，如果沒(méi)有好的排序算法，那么電腦會(huì)花費(fèi)大量的時(shí)間在數(shù)據(jù)的查找上。本課題的研究則圍繞幾種基本的排序算法以及對(duì)其的動(dòng)態(tài)演示為重心。在對(duì)排序算法的闡述中，對(duì)時(shí)下常用的排序算法從理論到實(shí)現(xiàn)進(jìn)行了詳細(xì)講解。特別在實(shí)現(xiàn)過(guò)程中，采用C語(yǔ)言以函數(shù)的形式完成每一個(gè)排序方法的代碼，方便移植。在第二章的最后還對(duì)每種排序方法的性能進(jìn)行了分析以及對(duì)比，這樣能讓讀者更深入的了解排序算法之間的關(guān)系以及在選擇排序算法的過(guò)程中有一個(gè)明確的目標(biāo)。本課題關(guān)于排序算法研究目的在于，本文收集并整理了時(shí)下常用的基本的排序方法，且對(duì)每種排序算法從講解到代碼的實(shí)現(xiàn)都很清晰，在讀者對(duì)排序算法的學(xué)習(xí)或者教學(xué)過(guò)程中能啟一定的參考作用。排序算法的動(dòng)態(tài)演示程序則前所未有的用到了windowsSDK編程，這個(gè)十年前流行的技術(shù)現(xiàn)在早被MFC的光芒照耀，而前者本身在編程過(guò)程中就是對(duì)windows操作系統(tǒng)的學(xué)習(xí)以及對(duì)windows軟件的底層運(yùn)行機(jī)制的了解。論文的第三章也對(duì)整個(gè)編程過(guò)程進(jìn)行了講解，雖然重點(diǎn)在排序算法動(dòng)態(tài)演示這塊，但也對(duì)整個(gè)軟件的運(yùn)行過(guò)程進(jìn)行了講解，且運(yùn)用了很多常用的控件，代碼有很強(qiáng)的移植效果，從最后的演示結(jié)果來(lái)看，能讓讀者對(duì)排序算法有深入的認(rèn)識(shí)。總而言之，本文對(duì)基本排序方法做了詳細(xì)的總結(jié)，有很好的參考價(jià)值；演示程序則開(kāi)先河的用了比較底層的圖形編程，不但在運(yùn)行速度上有所提高且演示效果明顯易懂，對(duì)排序算法的教學(xué)和學(xué)習(xí)啟很好的輔助作用。課題的主要工作和技術(shù)難點(diǎn)課題圍繞排序算法展開(kāi)，在理解每種算法后，則把主要工作集中在對(duì)各種排序算法的整理和代碼實(shí)現(xiàn)以及動(dòng)態(tài)演示程序的編寫(xiě)。在本文所講述的排序算法中，都是基本的算法，所以資料比較豐富，學(xué)習(xí)過(guò)程中難點(diǎn)并不多。在選擇題目以后，我一直把重點(diǎn)放在動(dòng)態(tài)演示程序這一塊，因?yàn)槲疫m應(yīng)不了MFC的編程機(jī)制，且我一直想學(xué)習(xí)win32編程并能通過(guò)這些對(duì)windows操作系統(tǒng)本身有所了解。我的參考資料則是經(jīng)典的windows程序設(shè)計(jì)第五版，一本一千多頁(yè)的書(shū)，我也是看了一大半慘對(duì)這種編程方法有初步了解其中包括對(duì)windows系統(tǒng)的了解，當(dāng)然這個(gè)過(guò)程是枯燥乏味的。在看到第一個(gè)windows程序時(shí)是一頭霧水，特別是里面的各種句柄真是讓人暈頭轉(zhuǎn)向；還有CreateWindow里面的各種風(fēng)格和擴(kuò)展風(fēng)格，加上控件的風(fēng)格那可是多如牛毛；在windows系統(tǒng)上運(yùn)行的軟件，一開(kāi)始需要注冊(cè)窗口類，之后是創(chuàng)建窗口，刷新客戶區(qū)，然后執(zhí)行整個(gè)軟件運(yùn)行的最重要操作，消息處理函數(shù)。這個(gè)函數(shù)是一個(gè)回調(diào)函數(shù)，剛開(kāi)始對(duì)回調(diào)函數(shù)的理解也是讓人很痛苦的，但后來(lái)理解到回調(diào)函數(shù)就是不但軟件要用且windows本身也要用到的一個(gè)函數(shù)，就是它實(shí)現(xiàn)了windows系統(tǒng)與在該系統(tǒng)上運(yùn)行的軟件之間的通信，簡(jiǎn)而言之，就是軟件你要處理什么消息，自己去拿，系統(tǒng)都已經(jīng)準(zhǔn)備好了，剩下的你不需要的消息則由系統(tǒng)自己消化。一個(gè)十年前流行的技術(shù)本身資料很少，特別是最新的windows技術(shù)，所以很多地方都是很困難的。本課題幾乎所以技術(shù)難點(diǎn)都集中在與編程這一塊，包括排序算法的實(shí)現(xiàn)和軟件的編寫(xiě)，而后者更顯得沉重。后者范圍太廣且很多地方涉及到操作系統(tǒng)本身。一些知識(shí)之前根本沒(méi)有接觸過(guò)，都是遇到問(wèn)題解決問(wèn)題，可能這也是畢業(yè)設(shè)計(jì)的宗旨吧。

排序算法的實(shí)現(xiàn)方法及性能分析第一節(jié)插入排序插入排序的基本思想是：每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的記錄集中，使記錄依然有序，直到所有待排序記錄全部插入完成。一、直接插入排序1.直接插入排序思想假設(shè)待排序數(shù)據(jù)存放在數(shù)組A[1..n]中（A[0]可用做監(jiān)視哨），則A[1]可看作是一個(gè)有序序列，讓i從2開(kāi)始，依次將A[i]插入到有序序列A[1..i-1]中，A[n]插入完畢則整個(gè)過(guò)程結(jié)束，A[1..n]成為有序序列。排序過(guò)程示例（用“（）”表示有序序列）待排序數(shù)據(jù)：（25）548542119727315（n=10）i=2： （2554）8542119727315i=3： （82554）542119727315i=4： （8255454）2119727315i=5： （821255454）19727315i=6： （1821255454）9727315i=7： （182125545497）27315i=8： （1282125545497）7315i=9： （128212554547397）15i=10： （12815212554547397）排序結(jié)束3．算法實(shí)現(xiàn)可在數(shù)組中增加元素A[0]作為關(guān)鍵值（待插入的數(shù)據(jù)）存儲(chǔ)器和循環(huán)控制開(kāi)關(guān)。第i趟排序，即A[i]的插入過(guò)程為：①保存A[i]→A[0]②從后往前遍歷，條件不符則數(shù)據(jù)后移③如果A[j]<=A[0]（即待排序的A[i]），則A[0]→A[j+1]，完成插入；否則，將A[j]后移一個(gè)位置：A[j]→A[j+1]；；繼續(xù)執(zhí)行③對(duì)于上面的數(shù)據(jù)實(shí)例，i從2依次變化到10的過(guò)程中，j值分別為{1，0，3，1，0，6，1，7，3}4．程序代碼voidInsertSort(intA[],intn)//對(duì)數(shù)組A做直接插入排序{inti,j;for(i=2;i<n;i++)//A[0]用于待插數(shù)據(jù)存儲(chǔ)，從第二個(gè)開(kāi)始if(A[i]<A[i-1])//"<",需將A[i]插入有序子表 { A[0]=A[i];//復(fù)制到緩存充當(dāng)哨兵 A[i]=A[i-1];//已經(jīng)確定小于則用前值覆蓋 for(j=i-2;A[0]<A[j];j--) A[j+1]=A[j];//接著前面，記錄后移 A[j+1]=A[0];//插入到正確位置 }}5．算法分析（1）穩(wěn)定性：穩(wěn)定（2）時(shí)間復(fù)雜度：①原始數(shù)據(jù)正序，總比較次數(shù)：②原始數(shù)據(jù)逆序，總比較次數(shù)：③原始數(shù)據(jù)無(wú)序，第i趟平均比較次數(shù)=，總次數(shù)為：④可見(jiàn)，原始數(shù)據(jù)越趨向正序，比較次數(shù)和移動(dòng)次數(shù)越少。（3）空間復(fù)雜度：僅需一個(gè)單元A[0]二、希爾排序希爾排序(Shell'sSort)又稱“縮小增量排序”(DiminishingIncrementSort)，它也是一種屬于插入排序類的方法，但在時(shí)間效率上較前述排序方法有較大的改進(jìn)。1．基本思想任取一個(gè)小于n的整數(shù)S1作為增量，把所有元素分成S1個(gè)組。所有間距為S1的元素放在同一個(gè)組中。第一組：{A[1]，A[S1+1]，A[2*S1+1]，……}第二組：{A[2]，A[S1+2]，A[2*S1+2]，……}第三組：{A[3]，A[S1+3]，A[2*S1+3]，……}……第s1組：{A[S1]，A[2*S1]，A[3*S1]，……}先在各組內(nèi)進(jìn)行直接插人排序；然后，取第二個(gè)增量S2（<S1）重復(fù)上述的分組和排序，直至所取的增量St=1（St<St-1<St-2<…<S2<S1），即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹?。增量序列可以有各種取法，但需要注意：應(yīng)使增量序列中的值沒(méi)有除1之外的公因子，并且最后一個(gè)增量必須等于1。排序過(guò)程示例設(shè)有10個(gè)待排序的記錄，關(guān)鍵字分別為12,89,57,32,96,37,54,5,79,57，增量序列是5,3,2,1，希爾排序的過(guò)程如下表序號(hào)12345678910原始數(shù)據(jù)1289573296375457957S1=5組別①②③④⑤①②③④⑤排序結(jié)果1254532573789577996S2=3組別①②③①②③①②③①排序結(jié)果1254532573789577996S2=2組別①②①②①②①②①②排序結(jié)果5321237575479578996S4=1組別①①①①①①①①①①排序結(jié)果5123237545757798996表2_1_1其中相同組別內(nèi)部執(zhí)行直接插入排序，比如當(dāng)S1=5時(shí)，同為①組的是12和37，同為②的是89和54……，這樣的有五組分別在其內(nèi)部進(jìn)行直接插入排序，這里的第二組就變成了54和89，當(dāng)所以的執(zhí)行完，改變?cè)隽坷^續(xù)執(zhí)行，直到增量等于1。所以越到后面整個(gè)序列越是有序，當(dāng)然在基本有序的情況下，直接插入排序就會(huì)顯得更簡(jiǎn)單。3．算法實(shí)現(xiàn)由于在分組內(nèi)部使用的是直接插入排序，因此排序過(guò)程只要在直接插入排序的算法上對(duì)其步長(zhǎng)進(jìn)行修改就可以了，這里寫(xiě)了兩個(gè)函數(shù)，一個(gè)調(diào)用一個(gè)實(shí)現(xiàn)了希爾排序，程序易于理解。4．程序代碼voidShellPass(intA[],ints,intn)//對(duì)數(shù)組A進(jìn)行一次希爾排序，增量為s{inti,j; for(i=s+1;i<n;i++) { A[0]=A[i];//設(shè)置監(jiān)視哨兵 j=i-s; while(j>0&&A[0]<A[j])//前插條件滿足 {A[j+s]=A[j];j=j-s;}//記錄后移 A[j+s]=A[0];//插入正確位置 }}voidShellSort(intA[],intS[],intn,intt)//其中S為增量序列,n為數(shù)組長(zhǎng)度{//按增量序列S[0…t-1],對(duì)順序表L進(jìn)行希爾排序inti;for(i=0;i<t;i++)ShellPass(A,S[i],n);}5．算法分析（1）穩(wěn)定性：不穩(wěn)定（2）時(shí)間復(fù)雜度：①希爾排序的分析是一個(gè)復(fù)雜的問(wèn)題，因?yàn)樗臅r(shí)間是所取“增量”序列的函數(shù)，這涉及一些數(shù)學(xué)上尚未解決的難題。因此，到目前為止尚未有人求得一種最好的增量序列，但大量的研究已得出一些局部的結(jié)論。如有人指出，當(dāng)增量序列未時(shí)，希爾排序的時(shí)間復(fù)雜度為，其中t為排序趟數(shù)，。還有人在大量的實(shí)驗(yàn)基礎(chǔ)上推出：當(dāng)n在某個(gè)特定范圍內(nèi)，希爾排序所需要的比較和移動(dòng)次數(shù)約為，當(dāng)時(shí)，可減少到。②在直接插入排序中，數(shù)據(jù)越趨向于有序，比較和移動(dòng)次數(shù)越少，希爾排序的目的則是增加這種有序趨勢(shì)。雖然看起來(lái)重復(fù)次數(shù)較多，需要多次選擇增量，但開(kāi)始時(shí)，增量較大，分組較多，但由于各組的數(shù)據(jù)個(gè)數(shù)少，則比較次數(shù)累計(jì)值也小，當(dāng)增量趨向1時(shí)，組內(nèi)數(shù)據(jù)增多，而所有數(shù)據(jù)已經(jīng)基本接近有序狀態(tài)，因此，希爾排序的時(shí)間性能優(yōu)于直接插入排序?？臻g復(fù)雜度：僅需一個(gè)單元A[0]第二節(jié)交換排序交換排序的基本思想是：兩兩比較待排序的數(shù)據(jù)，發(fā)現(xiàn)兩個(gè)數(shù)據(jù)的次序相反則進(jìn)行交換，直到?jīng)]有反序的數(shù)據(jù)為止。一、冒泡排序1．冒泡排序的思想最多進(jìn)行n-1趟排序，每趟排序時(shí)，從底部向上掃描，一旦發(fā)現(xiàn)兩個(gè)相鄰的元素不符合規(guī)則（如果由小到大排序，規(guī)則就是前者大于后者，由大到小則反之），則交換。我們發(fā)現(xiàn)，第一趟排序后，最小值在A[1]，第二趟排序后，較小值在A[2]，第n-1趟排序完成后，所有元素完全按順序排列。排序過(guò)程示例（由小到大，從底部冒泡）待排序數(shù)據(jù)：5333195336382201939第一趟排序：3533319531963822039第二趟排序：3195333195320638239第三趟排序：3191953332053396382第四趟排序：3191920533339536382第五趟排序：3191920335339536382第六趟排序：3191920333953536382第七趟排序：沒(méi)有反序數(shù)據(jù)，排序結(jié)束。3．程序代碼voidBubbleSort(intA[],intn){//冒泡排序，從后往前遍歷inti,j,flag=1;intTemp;//中間變量for(i=n;i>0&&flag==1;i--)//當(dāng)flag=0時(shí)表示沒(méi)有反序數(shù)列跳出循環(huán)，排序完畢{flag=0;//標(biāo)志位 for(j=n-1;j>n-i;j--) if(A[j]<A[j-1])//不滿足規(guī)則就交換 {flag=1;Temp=A[j]; A[j]=A[j-1];A[j-1]=Temp; }}}4．算法分析（1）穩(wěn)定性：穩(wěn)定（2）時(shí)間復(fù)雜度：①原始數(shù)據(jù)正序，需一趟排序，比較次數(shù)②原始數(shù)據(jù)反序，需n-1趟排序，比較次數(shù)③一般情況下，雖然不一定需要n-1趟排序，但由于每次數(shù)據(jù)位置的改變需要3次移動(dòng)操作，因此，總時(shí)間復(fù)雜度高于直接插入排序。（3）空間復(fù)雜度：僅需一個(gè)中間變量Temp二、快速排序1．快速排序的思想在A[1..n]中任取一個(gè)數(shù)據(jù)元素作為比較的“基準(zhǔn)”（不妨記為X），將數(shù)據(jù)區(qū)劃分為左右兩個(gè)部分：A[1..i-1]和A[i+1..n]，且A[1..i-1]≤X≤A[i+1..n](1≤i≤n)，當(dāng)A[1..i-1]和A[i+1..n]非空時(shí)，分別對(duì)它們進(jìn)行上述的劃分過(guò)程，直至所有數(shù)據(jù)元素均已排序?yàn)橹埂?．算法實(shí)現(xiàn)可以使用遞歸函數(shù)實(shí)現(xiàn)這一算法。假定待排序序列的下標(biāo)范圍為low~high。借用兩個(gè)整型變量i、j作為指針，約定初值分別為low、high。排序過(guò)程：①選定基準(zhǔn)X（不妨用A[low]）②j向前掃描，直到A[j]<X，交換A[i]與A[j]，i+1。保證了A[low..i-1]≤X③i向后掃描，直到A[i]>X，交換A[i]與A[j]，j-1。保證了X≤A[j..high]④繼續(xù)執(zhí)行②、③，直到i=j。這時(shí)，X恰好在A[i]位置上。⑤對(duì)序列A[low..i-1]及A[i+1..high]按照上述規(guī)律繼續(xù)劃分，直到序列為空。仔細(xì)分析算法，我們發(fā)現(xiàn)，在排序中，我們總是用基準(zhǔn)X與另一數(shù)據(jù)交換，因此，一趟排序結(jié)束后，X就能確切定位其最終位置。3．排序過(guò)程示例待排序數(shù)據(jù)：6767145229990548771X=67ij掃描jij交換5467145229990678771掃描iij交換5467145229967908771j=i，結(jié)束ij第一趟排序后：54671452299[67]908771第二趟排序后：9291452[54]67[67]7187[90]第三趟排序后：[9]291452[54676771]87[90]第四趟排序后：[9]14[29]52[546767718790]第五趟排序后：[9142952546767718790]4．程序代碼intPartition(intA[],intlow,inthigh){A[0]=A[low];//A[0]做哨兵，以它為界左右分開(kāi)while(low<high){while(low<high&&A[high]>=A[0])//從數(shù)組的兩端交替向中間掃描high--;A[low]=A[high];//將小于哨兵的數(shù)字移動(dòng)到低端while(low<high&&A[low]<=A[0])low++;A[high]=A[low];//將大于哨兵的數(shù)字移動(dòng)到高端}A[low]=A[0];//放置哨兵位returnlow;//返回其位置}voidQuickSort(intA[],intlow,inthigh){intcenter;//保存哨兵位置if(low<high){center=Partition(A,low,high);//將A[lowhigh]一分為二 QuickSort(A,low,center-1);//對(duì)低子表遞歸排序QuickSort(A,center+1,high);//對(duì)高子表遞歸排序}}5．算法分析（1）穩(wěn)定性：不穩(wěn)定（2）時(shí)間復(fù)雜度：每趟排序所需的比較次數(shù)為待排序區(qū)間的長(zhǎng)度-1，排序趟數(shù)越多，占用時(shí)間越多。①最壞情況：每次劃分選取的基準(zhǔn)恰好都是當(dāng)前序列中的最小(或最大)值，劃分的結(jié)果A[low..i-1]為空區(qū)間或A[i+1..high]是空區(qū)間，且非空區(qū)間長(zhǎng)度達(dá)到最大值。這種情況下，必須進(jìn)行n-1趟快速排序，第i次趟去見(jiàn)長(zhǎng)度為n-i+1，總的比較次數(shù)達(dá)到最大值：②最好情況：每次劃分所取的基準(zhǔn)都是當(dāng)前序列中的“中值”，劃分后的兩個(gè)新區(qū)間長(zhǎng)度大致相等。共需趟快速排序，總的關(guān)鍵字比較次數(shù)：。③基準(zhǔn)的選擇決定了算法性能。經(jīng)常采用選取low和high之間一個(gè)隨機(jī)位置作為基準(zhǔn)的方式改善性能。（3）空間復(fù)雜度：快速排序在系統(tǒng)內(nèi)部需要一個(gè)棧來(lái)實(shí)現(xiàn)遞歸，最壞情況下為，最佳情況下為，其中A[0]不記。第三節(jié)選擇排序選擇排序的基本思想是：每一趟從待排序的數(shù)據(jù)中選出最小元素，順序放在已排好序的數(shù)據(jù)最后，直到全部數(shù)據(jù)排序完畢。一、直接選擇排序1．過(guò)程模擬表2_3_1待排序數(shù)據(jù)92286284621656873366第一趟排序16286284629256873366第二趟排序16286284629256873366第三趟排序16283384629256876266第四趟排序16283356629284876266第五趟排序16283356629284876266第六趟排序16283356626284879266第七趟排序16283356626266879284第八趟排序16283356626266849287第九趟排序162833566262668487922．程序代碼voidSelectSort(intA[],intn)//簡(jiǎn)單選擇排序{inti,j;for(i=1;i<n;i++)//從前往后掃描 for(j=i+1;j<n;j++) if(A[i]>A[j])//小到大 { A[0]=A[i];//第i個(gè)記錄和第j個(gè)記錄交換 A[i]=A[j]; A[j]=A[0]; }}3．算法分析（1）穩(wěn)定性：不穩(wěn)定（2）時(shí)間復(fù)雜度：（3）空間復(fù)雜度：僅需一個(gè)中間單元A[0]二、堆排序1．堆排序思想堆排序是一種樹(shù)形選擇排序，在排序過(guò)程中，將A[1..n]看成是完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹(shù)中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來(lái)選擇最小的元素。堆的定義n個(gè)元素的序列K1，K2，K3，…Kn稱為堆，當(dāng)且僅當(dāng)該序列滿足特性：Ki≤K2i，Ki≤K2i+1（1≤i≤n/2）堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹(shù)：樹(shù)中任一非葉子結(jié)點(diǎn)的關(guān)鍵字均大于等于其孩子結(jié)點(diǎn)的關(guān)鍵字。例如序列{1,35,14,60,61,45,15,81}就是一個(gè)堆，它對(duì)應(yīng)的完全二叉樹(shù)如下圖1所示。這種堆中根結(jié)點(diǎn)（稱為堆頂）的關(guān)鍵字最小，我們把它稱為小根堆。反之，若完全二叉樹(shù)中任一非葉子結(jié)點(diǎn)的關(guān)鍵字均大于等于其孩子的關(guān)鍵字，則稱之為大根堆。圖2_3_1最小堆圖2_3_2最大堆堆排序過(guò)程（以最大堆為例）（1）調(diào)整堆假定待排序數(shù)組A為{20，12，35，15，10，80，30，17，2，1}（n=10），初始完全樹(shù)狀態(tài)為：圖2_3_3圖2_3_4結(jié)點(diǎn)（20）、（35）、(12)等，值小于其孩子結(jié)點(diǎn)，因此，該樹(shù)不屬最大堆。為了將該樹(shù)轉(zhuǎn)化為最大堆，從后往前查找，自第一個(gè)具有孩子的結(jié)點(diǎn)開(kāi)始，根據(jù)完全二叉樹(shù)性質(zhì)，這個(gè)元素在數(shù)組中的位置為i=[n/2]，如果以這個(gè)結(jié)點(diǎn)為根的子樹(shù)已是最大堆，則此時(shí)不需調(diào)整，否則必須調(diào)整子樹(shù)使之成為堆。隨后，繼續(xù)檢查以i-1、i-2等結(jié)點(diǎn)為根的子樹(shù)，直到檢查到整個(gè)二叉樹(shù)的根結(jié)點(diǎn)（i=1），并將其調(diào)整為堆為止。調(diào)整方法：由于A[i]的左、右子樹(shù)均已是堆，因此A[2i]和A[2i+1]分別是各自子樹(shù)中關(guān)鍵字最大的結(jié)點(diǎn)。若A[i]不小于A[2i]和A[2i+1]，則A[i]沒(méi)有違反堆性質(zhì)，那么以A[i]為根的子樹(shù)已是堆，無(wú)須調(diào)整；否則必須將A[i]和A[2i]與A[2i+1]中較大者（不妨設(shè)為A[j]）進(jìn)行交換。交換后又可能使結(jié)點(diǎn)A[j]違反堆性質(zhì)，同樣由于該結(jié)點(diǎn)的兩棵子樹(shù)仍然是堆，故可重復(fù)上述的調(diào)整過(guò)程，直到當(dāng)前被調(diào)整的結(jié)點(diǎn)已滿足堆性質(zhì)，或者該結(jié)點(diǎn)已是葉子結(jié)點(diǎn)為止。以上圖為例，經(jīng)過(guò)調(diào)整后，最大堆為：{80，17，35，12，10，20，30，15，2，1}。如圖4_4所示。此堆作為排序的初始無(wú)序區(qū)。（2）選擇、交換、調(diào)整①將建成的最大堆作為初始無(wú)序區(qū)。②將堆頂元素（根）A[1]和A[n]交換，由此得到新的無(wú)序區(qū)A[1..n-1]和有序區(qū)A[n]，且滿足A[1..n-1]≤A[n]③將A[1..n-1]調(diào)整為堆。④再次將A[1]和無(wú)序區(qū)最后一個(gè)數(shù)據(jù)A[n-1]交換，由此得到新的無(wú)序區(qū)A[1..n-2]和有序區(qū)A[n-1..n]，且仍滿足關(guān)系A(chǔ)[1..n-2]≤A[n-1..n]，同樣要將A[1..n-2]調(diào)整為堆。直到無(wú)序區(qū)只有一個(gè)元素A[1]為止。說(shuō)明：如果需要生成降序序列，則利用最小堆進(jìn)行操作。4．程序代碼voidmaxheapify(intA[],inti,intheapsize){intlargest,left,right,Temp;left=Left(i);right=Right(i);if(left<=heapsize&&A[left]>A[i])largest=left;elselargest=i;if(right<=heapsize&&A[right]>A[largest])largest=right;if(largest!=i){ Temp=A[i]; A[i]=A[largest]; A[largest]=Temp;maxheapify(A,largest,heapsize);}return;}voidHeapSort(intA[],intheapsize){inti,Temp;for(i=heapsize/2;i>=1;i--)/*buildmax-heap*/maxheapify(A,i,heapsize);for(i=heapsize;i>=2;i--)/*deletemax*/{Temp=A[1]; A[1]=A[i]; A[i]=Temp;heapsize--;maxheapify(A,1,heapsize);}}5．算法分析（1）穩(wěn)定性：不穩(wěn)定。假定數(shù)據(jù)序列為{1，1}，已是大堆，經(jīng)過(guò)排序后，結(jié)果為{1，1}。（2）時(shí)間復(fù)雜度：堆排序的時(shí)間，主要由建立初始堆和反復(fù)調(diào)整堆這兩部分的時(shí)間開(kāi)銷構(gòu)成，它們均是通過(guò)調(diào)用maxheapify函數(shù)實(shí)現(xiàn)的。堆排序的最壞時(shí)間復(fù)雜度為。堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。（3）空間復(fù)雜度：第四節(jié)歸并排序歸并排序是利用"歸并"技術(shù)來(lái)進(jìn)行排序。歸并是指將若干個(gè)已排序的子文件合并成一個(gè)有序的文件。一、兩路歸并算法1、算法基本思路假設(shè)初始序列含有n個(gè)記錄，則可看成是n個(gè)有序的子序列，沒(méi)個(gè)子序列的長(zhǎng)度為1，然后兩兩歸并，得到[n/2]個(gè)長(zhǎng)度為2或1的有序子序列；再兩兩歸并，……，如此重復(fù)，直到得到一個(gè)長(zhǎng)度為n的有序序列為止。設(shè)有兩個(gè)有序（升序）序列存儲(chǔ)在同一數(shù)組中相鄰的位置上，不妨設(shè)為sr[left...mid]，sr[mid+1...right]，將它們歸并為一個(gè)有序數(shù)列，并存儲(chǔ)在sr[left...right]。2．程序代碼voidMerge(int*sr,int*di,intleft,intmid,intright){//將有序的sr[left...mid]和sr[mid+1...right]歸并為有序的di[left...right]inti=left,j=mid+1,k=left;while(i<=mid&&j<=right)//將sr中記錄由小到大的并入di{if(sr[i]<sr[j])di[k++]=sr[i++];elsedi[k++]=sr[j++];}if(i>mid)//將剩余的sr[j...right]復(fù)制到diwhile(j<=right)di[k++]=sr[j++];elseif(j>right)//將剩余的sr[i...mid]復(fù)制到diwhile(i<=mid)di[k++]=sr[i++];}二、歸并排序歸并排序有兩種實(shí)現(xiàn)方法：遞歸法和非遞歸方法。1．非遞歸法（1）基本思想自底向上的基本思想是：第1趟歸并排序時(shí)，將數(shù)列A[1..n]看作是n個(gè)長(zhǎng)度為1的有序序列，將這些序列兩兩歸并，若n為偶數(shù)，則得到[n/2]個(gè)長(zhǎng)度為2的有序序列；若n為奇數(shù)，則最后一個(gè)子序列不參與歸并。第2趟歸并則是將第1趟歸并所得到的有序序列兩兩歸并。如此反復(fù)，直到最后得到一個(gè)長(zhǎng)度為n的有序文件為止。上述的每次歸并操作，均是將兩個(gè)有序序列合并成一個(gè)有序序列，故稱其為“二路歸并排序”。類似地有k(k>2)路歸并排序。（2）程序代碼//歸并排序之非遞歸voidMergeSort(intA[],intB[],intn){ intstep=1;//決定趟數(shù) while(step<n) { MergePass(A,B,step,count);//#1 step=2*step; MergePass(B,A,step,count);//作用：和#1輪替執(zhí)行，保證源數(shù)據(jù)是被部分歸并過(guò)的； step=2*step;//作用：在歸并完成后再調(diào)用一次，把最終歸并結(jié)果copy到A數(shù)組中 }//其實(shí)是調(diào)用了MergePass里最后的for循環(huán)。}//歸并排序非遞歸之一趟歸并voidMergePass(intC[],intD[],intstep,intlen){//決定每一趟需要幾次歸并 inti=0; while(i<=len-2*step)//一組一組地進(jìn)行歸并（這兩組是） { Merge(C,D,i,i+step-1,i+2*step-1); i+=2*step; } if(i+step<len)//如果剩余元素夠一組再進(jìn)行一次歸并 Merge(C,D,i,i+step-1,len-1); else for(intj=i;j<=len-1;j++)//作用：如果元素不夠一組那么直接把剩余元素copy到//目標(biāo)指針?biāo)赶虻目臻g D[j]=C[j];//作用：一切元素都?xì)w并完成之后，把最終歸并//結(jié)果copy到A數(shù)組中。}2．遞歸法采用遞歸法進(jìn)行自頂向下的算法設(shè)計(jì)，形式更為簡(jiǎn)潔。（1）分治法的三個(gè)步驟設(shè)歸并排序的當(dāng)前區(qū)間是sr[l..h]，分治法的三個(gè)步驟是：分解：將當(dāng)前區(qū)間一分為二，即求分裂點(diǎn)m=(l+h)/2；求解：遞歸地對(duì)兩個(gè)子區(qū)間sr[l..m]和sr[m+1..h]進(jìn)行歸并排序；組合：將已排序的兩個(gè)子區(qū)間sr[l..m]和sr[m+1..h]歸并為一個(gè)有序的區(qū)間sr[l..h]。遞歸的終結(jié)條件：子區(qū)間長(zhǎng)度為1（一個(gè)數(shù)據(jù)組成的區(qū)間必然有序）。（2）程序代碼voidMSort(intsr[],di[],ints,intt){//將sr[s...t]歸并到di[s...t]intm;if(s==t)di[s]=sr[s]; else { m=(s+t)/2;//將sr[s..t]平分為sr[s..m]和sr[m+1..t] MSort(sr,di,s,m);//遞歸的將sr[s..m]歸并為有序的di[s..m] MSort(sr,di,m+1,t);//遞歸的將sr[m+1..t]歸并為有序的di[m+1..t] Merge(sr,di,s,m,t);//將sr[s..m]和sr[m+1..t]歸并為di[s..t] }}3．算法分析（1）穩(wěn)定性歸并排序是一種穩(wěn)定的排序。（2）存儲(chǔ)結(jié)構(gòu)要求用順序存儲(chǔ)結(jié)構(gòu)。也易于在鏈表上實(shí)現(xiàn)。（3）時(shí)間復(fù)雜度長(zhǎng)度為n的數(shù)列，需進(jìn)行趟二路歸并，每趟歸并的時(shí)間為，故其時(shí)間復(fù)雜度無(wú)論是在最好情況下還是在最壞情況下均是。（4）空間復(fù)雜度需要一個(gè)輔助數(shù)組來(lái)暫存兩有序序列歸并的結(jié)果，故其輔助空間復(fù)雜度為。第五節(jié)各種排序算法的比較討論一、各種算法比較表2_5_1方法平均時(shí)間最壞所需時(shí)間空間復(fù)雜度穩(wěn)定性直接插入排序穩(wěn)定希爾排序不穩(wěn)定簡(jiǎn)單選擇排序不穩(wěn)定堆排序不穩(wěn)定冒泡排序穩(wěn)定快速排序不穩(wěn)定歸并排序穩(wěn)定主要內(nèi)部排序算法的性能表從平均時(shí)間性能而言，快速排序最好，其所需時(shí)間最省，但快速排序在最壞情況下的時(shí)間性能不如堆排序和歸并排序。而后兩者相比較的結(jié)果是，在n較大是，歸并排序所需要時(shí)間較堆排序省，但它所需的輔助存儲(chǔ)量最多。在時(shí)間復(fù)雜度為的排序算法（直接插入排序、簡(jiǎn)單選擇排序、冒泡排序），其中直接插入排序最為簡(jiǎn)單，當(dāng)序列中的記錄“基本有序”或者n值較小時(shí)，它是最佳的排序方法，因此常將它和其他的排序方法，如快速排序、歸并排序等結(jié)合在一起使用。從方法的穩(wěn)定性來(lái)比較，所有時(shí)間復(fù)雜度為的排序方法都是穩(wěn)定的，然而快速排序、堆排序和希爾排序等時(shí)間性能較好的排序方法都是不穩(wěn)定的。一般來(lái)說(shuō)，排序過(guò)程中的“比較”是在“相鄰的兩個(gè)記錄關(guān)鍵字”間進(jìn)行的排序方法是穩(wěn)定的。值得提出的是，穩(wěn)定性是由方法本身決定的，對(duì)不穩(wěn)定的排序方法而言，不管其描述形式如何，總能舉出一個(gè)說(shuō)明不穩(wěn)定的實(shí)例來(lái)。反之，對(duì)穩(wěn)定的排序方法，總能找到一種引起不穩(wěn)定的描述形式。由于大多數(shù)情況下排序是按記錄的主關(guān)鍵字進(jìn)行的，則所用的排序方法是否穩(wěn)定無(wú)關(guān)緊要。若排序按記錄的次關(guān)鍵字進(jìn)行，則應(yīng)根據(jù)問(wèn)題所需慎重選擇排序方法及其描述算法。二、選取排序算法的主要因素◆待排序的記錄數(shù)目n；◆每個(gè)記錄的大??；◆關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)；◆是否要求排序的穩(wěn)定性；◆語(yǔ)言工具的特性；◆存儲(chǔ)結(jié)構(gòu)的初始條件和要求；◆時(shí)間復(fù)雜度、空間復(fù)雜度和開(kāi)發(fā)工作的復(fù)雜程度的平衡點(diǎn)等。綜上所述，在本章討論的所用排序方法中，沒(méi)有那一種排序算法是絕對(duì)最優(yōu)的。有的適用于n較大的情況，有的適合于n較小的情況，有的………因此，在實(shí)用時(shí)需要根據(jù)不同情況適當(dāng)選用，甚至可將多種方法結(jié)合起來(lái)使用。第三章排序算法的動(dòng)態(tài)演示第一節(jié)編程環(huán)境及語(yǔ)言一、編程環(huán)境的選擇現(xiàn)在比較流行的有MicrosoftVisualStudio2008和MicrosoftVisualC++6.0，前者界面很人性化，對(duì)工程和代碼的管理做得很好，有強(qiáng)大智能提示功能和接近完美的MSDN幫助文件，后者對(duì)代碼的兼容性很高，幾乎前十幾年的windowsC/C++代碼都是用它編寫(xiě)的，所以在程序的參考和編譯來(lái)看，它無(wú)可挑剔，但是那些粗糙的界面也很是讓人枯燥。本程序編譯環(huán)境是MicrosoftVisualStudio2008，在所以VS系列中是最穩(wěn)定，應(yīng)用最廣的一個(gè)版本。二、編程語(yǔ)言和工具M(jìn)FCObject:MFC(MicrosoftFoundationClasses)，是一個(gè)微軟公司提供的類庫(kù)（classlibraries），以C++類的形式封裝了Windows的API，并且包含一個(gè)應(yīng)用程序框架，以減少應(yīng)用程序開(kāi)發(fā)人員的工作量。其中包含的類包含大量Windows句柄封裝類和很多Windows的內(nèi)建控件和組件的封裝類。MFC是微軟封裝了的API。windows作為一個(gè)提供功能強(qiáng)大的應(yīng)用程序接口編程的操作系統(tǒng)，的確方便了許多程序員，傳統(tǒng)的win32開(kāi)發(fā)（直接使用windows的接口函數(shù)API）對(duì)于程序員來(lái)說(shuō)非常的困難，因?yàn)?，API函數(shù)實(shí)在太多了，而且名稱很亂，從零構(gòu)架一個(gè)窗口動(dòng)輒就是上百行的代碼。MFC是面向?qū)ο蟪绦蛟O(shè)計(jì)與Applicationframework的完美結(jié)合，他將傳統(tǒng)的API進(jìn)行了分類封裝，并且為你創(chuàng)建了程序的一般框架。確定，對(duì)于初學(xué)者很難理解它的后臺(tái)運(yùn)行機(jī)制。windowsAPIObject:視覺(jué)操作系統(tǒng)應(yīng)用程序接口（windowsAPI），有非正式的簡(jiǎn)稱為WinAPI，是微軟對(duì)于windows操作系統(tǒng)中可用的核心應(yīng)用程序編程接口的稱法。它被設(shè)計(jì)為各種語(yǔ)言的程序調(diào)用，也是應(yīng)用軟與windows系統(tǒng)的最直接交互方式。WindowsAPI為程序員提供大量的構(gòu)建不同windows的底層結(jié)構(gòu)，這有助于為windows程序員開(kāi)發(fā)應(yīng)用程序提供大量的靈活性和功能。但是，它同樣是windows應(yīng)用程序要負(fù)責(zé)處理大量底層且又是是繁瑣的與圖形用戶界面（GUI）相關(guān)的操作。雖然題目是要求用MFC編寫(xiě)，但我還是選擇了windowsAPI編程，應(yīng)為我覺(jué)得前者有很多東西我很難理解，還有自己對(duì)C++沒(méi)有深刻的認(rèn)識(shí)，對(duì)類封裝這一新接觸概念很難接受，對(duì)MFC后臺(tái)的運(yùn)行機(jī)制并不明白。而winAPi則不同，全部采用C語(yǔ)言對(duì)windowsAPI進(jìn)行調(diào)用，從WinMain進(jìn)入主函數(shù)，到CALLBACKWndProc回調(diào)到消息處理函數(shù)，整個(gè)過(guò)程思路很清晰，只是在圖形編程上有些繁瑣而已，對(duì)消息的接收和處理反復(fù)操作，就連改變一個(gè)字體都要通過(guò)消息發(fā)送，但經(jīng)過(guò)幾個(gè)月的學(xué)習(xí)，已經(jīng)能熟練的建立圖形界面和操作消息了。以下就是我的演示程序的編寫(xiě)過(guò)程及細(xì)節(jié)。第二節(jié)動(dòng)態(tài)演示程序界面實(shí)現(xiàn)一、界面及功能介紹1、主界面：圖3_2_1模塊說(shuō)明主程序用groupbox控件把程序分為若干個(gè)模塊：演示區(qū)、操作區(qū)、排序方法、調(diào)速、風(fēng)格、顏色和數(shù)據(jù)查看。這樣做的好處是讓界面看上去清晰整潔。（1）演示區(qū)這是整個(gè)程序最重要的模塊。當(dāng)未進(jìn)入演示階段時(shí)，演示區(qū)TextOut打印出演示規(guī)則及相關(guān)說(shuō)明，如圖2_2_1所示；進(jìn)入演示畫(huà)面時(shí)如圖2_2_2，（直接插入排序）紅色的線條是操作線，其他是數(shù)據(jù)線，當(dāng)遇到需要移動(dòng)的數(shù)據(jù)線，其會(huì)改變?yōu)樘摼€，然后移動(dòng)到適當(dāng)?shù)奈恢?，整個(gè)演示就是這樣的尋找排序過(guò)程；當(dāng)排序完成如圖2_2_3，界面會(huì)顯示整個(gè)過(guò)程的比較次數(shù)和移動(dòng)次數(shù)。圖3_2_2圖3_2_3（2）操作區(qū)第一個(gè)按鍵點(diǎn)擊后程序會(huì)運(yùn)行隨機(jī)產(chǎn)生數(shù)組randpoint[143]，并用背景刷刷掉演示區(qū)，然后繪制數(shù)據(jù)線條和操作線條。這里要注意的是，每次需要觀看演示程序的時(shí)候，第一步一定得先創(chuàng)建數(shù)據(jù)，因?yàn)檫@個(gè)消息函數(shù)里面涉及到一些圖像以及函數(shù)的初始化工作；之后可以點(diǎn)擊開(kāi)始，當(dāng)然途中也可以暫停和繼續(xù)。（3）排序方法該模塊包括內(nèi)容有排序方法的選擇，這里用到了列表框，還有就是對(duì)該排序方法的一些性能說(shuō)明，其中有穩(wěn)定性、時(shí)間復(fù)雜度、空間復(fù)雜度。當(dāng)用戶選擇了一種新的排序方法時(shí)，在觀看演示之前一定要?jiǎng)?chuàng)建數(shù)據(jù)，這里再次說(shuō)明。（4）調(diào)速、風(fēng)格和顏色區(qū)調(diào)速左慢右快，具體是通過(guò)slider控件產(chǎn)生1~1000的整數(shù)，然后對(duì)定時(shí)器進(jìn)行設(shè)置；風(fēng)格就是可以選擇數(shù)據(jù)線或者數(shù)據(jù)點(diǎn)，當(dāng)然是二選一，還有就是可以去除操作線（這里存在一定的bug）；顏色區(qū)就不用多說(shuō)了，可以改變背景顏色和數(shù)據(jù)線顏色，操作線顏色就沒(méi)有提供修改方案，這些都是畫(huà)刷的一些選擇操作，程序并沒(méi)有把過(guò)多精力放在上面。（5）數(shù)據(jù)查看這個(gè)區(qū)域比較重要，當(dāng)點(diǎn)擊按鍵是程序會(huì)產(chǎn)生一個(gè)與之對(duì)應(yīng)的對(duì)話框，里面會(huì)把操作數(shù)據(jù)全部TextOut。用戶可以在創(chuàng)建數(shù)據(jù)后查看原始數(shù)據(jù)，還可以在排序過(guò)程中查看部分已排序的數(shù)據(jù)，這些只需要點(diǎn)擊“過(guò)程數(shù)據(jù)”按鍵就ok，如圖3_2_4所示。如果想查看已經(jīng)排序成功的數(shù)據(jù)，那么點(diǎn)擊“排序數(shù)據(jù)”按鍵就會(huì)彈出列好從小到大的數(shù)據(jù)，如圖3_2_5所示。這里要說(shuō)明的是，隨機(jī)產(chǎn)生的數(shù)范圍是0~280，至于為什么，這個(gè)是根據(jù)演示區(qū)的高度像素點(diǎn)決定的，還有就是演示用的隨機(jī)數(shù)組，和完成排序數(shù)據(jù)的數(shù)組是分開(kāi)的，所以才能實(shí)現(xiàn)二者的獨(dú)立性，并不互相干擾，但是為了數(shù)據(jù)的統(tǒng)一，數(shù)據(jù)還是不要隨便創(chuàng)建。圖3_2_4圖3_2_5二、主界面的創(chuàng)建在程序入口主函數(shù)WinMain里面定義了結(jié)構(gòu)體wndclass，然后注冊(cè)窗口類，也就是對(duì)結(jié)構(gòu)體內(nèi)部元素的填充，參數(shù)差不多都選擇默認(rèn)，只是圖標(biāo)MAKEINTRESOURCE了我自己添加到資源的一個(gè)圖標(biāo)（自動(dòng)化四班班徽）；如果窗口注冊(cè)成功，那么就開(kāi)始CreatWindow，這里我創(chuàng)建了一個(gè)寬600像素點(diǎn)，高470像素點(diǎn)的窗口，風(fēng)格默認(rèn)。差不多主界面就創(chuàng)建完成，后面ShowWindow和UpdateWindow顯示窗口并刷新客戶區(qū)，然后就是進(jìn)入消息循環(huán)直到窗口關(guān)閉。這里不得不提幾個(gè)比較重要的變量：hInst=hInstance，窗口實(shí)例句柄，這里傳給全局變量hInst，方便以后的操作；hwnd，就是創(chuàng)建主窗口返回的主窗口句柄，這個(gè)很重要，很多依賴主窗口所創(chuàng)建的控件都要用到這個(gè)句柄，包括對(duì)主窗口客戶區(qū)的操作也必須hdc=GetDC(hwnd)來(lái)獲得客戶區(qū)句柄。各個(gè)模塊的具體實(shí)現(xiàn)1、所有控件清單7個(gè)groupbox控件：負(fù)責(zé)對(duì)每個(gè)模塊區(qū)分畫(huà)界限，是軟件界面一目了然；5個(gè)button控件：就是按鍵，三個(gè)負(fù)責(zé)操作，另外兩個(gè)調(diào)用兩個(gè)對(duì)話框；3個(gè)combobox控件：列表框控件，一個(gè)是算法的選擇，后兩個(gè)分別是對(duì)背景和數(shù)據(jù)線顏色的設(shè)置；2個(gè)radiobutton控件和1個(gè)checkbox控件：用于風(fēng)格操作，radiobutton只能二選一，checkbox可選可不選；1個(gè)slider控件：滑塊控件，用于速度調(diào)節(jié)的；8個(gè)static控件：5個(gè)靜態(tài)字體用于具體說(shuō)明，另外3個(gè)是算法性能參數(shù)，根據(jù)算法不同會(huì)有相應(yīng)的值。1個(gè)灰色框：包圍演示區(qū)，有界限美觀作用；2個(gè)dialog對(duì)話框：一個(gè)是過(guò)程數(shù)據(jù)，一個(gè)是排序后數(shù)據(jù)。2、控件的創(chuàng)建這里由一個(gè)button控件為例：hpushbutton=CreateWindow(TEXT("button"),TEXT("創(chuàng)建數(shù)據(jù)"),WS_CHILD|WS_VISIBLE|BS_PUSHBUTTON,32,377,56,32,hwnd,(HMENU)IDM_BUILD_DATA,hInst,NULL);容易看出還是由CreatWindow（……）函數(shù)完成，其中第一個(gè)參數(shù)和第三個(gè)參數(shù)的BS_PUSHBUTTON決定了它的控件類型；第二個(gè)參數(shù)是控件名字，風(fēng)格則表示創(chuàng)建的是控件而且visible就是可視的；后面的數(shù)字，前兩個(gè)表示開(kāi)始的x、y坐標(biāo)，后者表示寬高；再后來(lái)是主窗口句柄，IDM_BUILD_DATA是控件ID，在消息處理函數(shù)的WM_COMMAND消息下由wParam參數(shù)的低字節(jié)傳遞；最后是實(shí)例句柄和擴(kuò)展，就不多說(shuō)。函數(shù)返回hpushbutton控件的當(dāng)前句柄，用于對(duì)控件的設(shè)置等，由SendMessage函數(shù)完成。關(guān)于控件字體的修改，因?yàn)橄到y(tǒng)默認(rèn)的字體實(shí)在難看，所以就自己創(chuàng)建了一個(gè)字體類，定義屬性為宋體，12號(hào)，SendMessage(hgroupbox,WM_SETFONT,(WPARAM)hfont,TRUE)來(lái)實(shí)現(xiàn)修改字體，其中hfont就是創(chuàng)建的字體類。其他控件大體都是這樣創(chuàng)建的，根據(jù)控件的不同或者需求不同，可以有不同的風(fēng)格和創(chuàng)建方式，以及后來(lái)微軟提供的CreatWindowEx函數(shù)更能增加控件的美觀性，當(dāng)然也可以手動(dòng)繪制控件等，在這里就不多討論。重要地說(shuō)一點(diǎn)是，關(guān)于滑塊控件的使用，它是控件里面最特別的一個(gè)，其它的控件ID都由WM_COMMAND消息下傳遞，而滑塊控件是單獨(dú)的消息，根據(jù)橫向或者縱向有WM_HSCROLL和WM_VSCROLL消息。3、關(guān)于dialog對(duì)話框的創(chuàng)建首先是在資源視圖里面創(chuàng)建一個(gè)newdialog，然后設(shè)置其ID，其消息的傳回跟上面的其他普通控件一樣。差不多創(chuàng)建就完成，之后要做的就是連接，和其自身內(nèi)部的消息處理，對(duì)話框其實(shí)就想一個(gè)對(duì)立的窗口一樣，它有自己的消息體，所以需要想主窗口那樣建立一個(gè)消息回調(diào)函數(shù)，然后在主消息循環(huán)里面添加如下代碼：DialogBox(hInst,MAKEINTRESOURCE(IDD_DIALOG2),hwnd,AboutDlgProc);其中最后一個(gè)參數(shù)就是他自己的消息回調(diào)函數(shù),比如一個(gè)簡(jiǎn)單的回調(diào)函數(shù)如下：BOOLCALLBACKAboutDlgProc(HWNDhDlg,UINTmessage,WPARAMwParam,LPARAMlParam){ switch(message) { caseWM_INITDIALOG: returnTRUE; caseWM_COMMAND: switch(LOWORD(wParam)) { caseIDOK: EndDialog(hDlg,0); break; } break; } returnFALSE;}WM_INITDIALOG接受對(duì)話框的初始化，有點(diǎn)像主消息函數(shù)里面的WM_CREATE，WM_COMMAND消息的wParam參數(shù)的地位字是默認(rèn)按鈕的ID。本例中該ID是IDOK，就是OK鍵。點(diǎn)擊EndDialog(hDlg,0)接受對(duì)話框。第三節(jié)排序算法動(dòng)態(tài)演示實(shí)現(xiàn)一、實(shí)現(xiàn)動(dòng)態(tài)演示的方法就像動(dòng)畫(huà)一樣，一定時(shí)間更換一張圖片，就實(shí)現(xiàn)了動(dòng)畫(huà)的連續(xù)性，那就是動(dòng)態(tài)的。所以對(duì)于簡(jiǎn)單的圖形動(dòng)態(tài)編程，可以以定時(shí)器為核心，因?yàn)槎〞r(shí)器每到一個(gè)規(guī)定時(shí)間就會(huì)產(chǎn)生WM_TIMER消息。在接收到這一消息時(shí)，我們要做的就是，擦除以前的圖形，畫(huà)出新的圖形，這樣反復(fù)操作就實(shí)現(xiàn)了動(dòng)態(tài)演示。在進(jìn)入定時(shí)器之前，必須對(duì)圖形進(jìn)行初始化，做好一切準(zhǔn)備工作，因?yàn)橐坏┏绦蜷_(kāi)始接收WM_TIMER消息，它就只會(huì)做兩件事情，一是擦圖像，二是畫(huà)圖像，直到排序完成。這里需要說(shuō)明的是，整個(gè)演示程序只代表性的選擇了三個(gè)排序算法：簡(jiǎn)單選擇排序、直接插入排序和冒泡排序。因?yàn)樯弦徽乱呀?jīng)對(duì)常用的排序算法有了深刻的講解，所以并沒(méi)有全部都實(shí)現(xiàn)了動(dòng)態(tài)演示。二、實(shí)現(xiàn)動(dòng)態(tài)演示步驟1.準(zhǔn)備當(dāng)用戶點(diǎn)擊“創(chuàng)建數(shù)據(jù)”按鈕，程序要做的就是：（1）把演示區(qū)用背景刷刷成背景色（2）RandomData(randpoint,143)產(chǎn)生隨機(jī)數(shù)組（3）一個(gè)for循環(huán)把隨機(jī)數(shù)組對(duì)應(yīng)的值繪制成線，由下往上繪制（4）選擇排序算法初始化：這里的iIndex值就是combobox列表框控件產(chǎn)生的switch(iIndex)//排序方法選擇 { case0:BubbleInit(hdc);//冒泡 break; case1:InsertInit(hdc);//直接插入 break; case2: SelectInit(hdc);//選擇排序 break; }2.開(kāi)始當(dāng)消息接收到WM_COMMAND消息里的IDM_PLAY（“開(kāi)始”按鈕的ID）時(shí)，執(zhí)行代碼：SetTimer(hwnd,1,speed,NULL)就是建立一個(gè)定時(shí)器，定時(shí)時(shí)間是speed，這個(gè)參數(shù)由slider速度控件產(chǎn)生。當(dāng)定時(shí)器一設(shè)置后，系統(tǒng)就會(huì)產(chǎn)生WM_TIMER消息，之后要做的就是去接收這個(gè)消息，反復(fù)在里面改變圖像。3.運(yùn)行caseWM_TIMER: switch(iIndex) { case0:BubbleSort(hdc);//冒泡排序 break; case1:InsertSort(hdc);//直接插入 break; case2: SelectSort(hdc);//簡(jiǎn)單選擇排序 break; }return0;表面看很簡(jiǎn)單，其實(shí)這是整個(gè)程序的精髓，只不過(guò)用函數(shù)封裝了顯得簡(jiǎn)單。當(dāng)排序完成，這里還有關(guān)閉KillTimer定時(shí)器，還有告訴用戶這個(gè)排序一共比較多少次，移動(dòng)了多少次。三、具體排序算法實(shí)現(xiàn)的過(guò)程以下將以直接插入排序和簡(jiǎn)單選擇排序?yàn)槔又v解具體排序算法的實(shí)現(xiàn)：1.直接插入排序算法第二章已經(jīng)詳細(xì)的講了直接插入排序算法的實(shí)現(xiàn)過(guò)程，簡(jiǎn)而言之就是，待排序數(shù)據(jù)挨個(gè)從后向前和前面已排序數(shù)據(jù)比較，如果滿足比較條件則插入，后面的依次后移。這樣反反復(fù)復(fù)直到完成。程序的最開(kāi)始構(gòu)建了兩個(gè)POINT點(diǎn)數(shù)組ptlast[4]和ptnow[4]用于操作線（紅色）的更新和保存，因?yàn)椴僮骶€由一條折線組成，所以需要4個(gè)點(diǎn)，然后用Polyline函數(shù)完成繪制。直接插入排序里面的操作線是這樣布置的，始端指向和待排序數(shù)據(jù)長(zhǎng)度一樣的克隆線條，如果數(shù)據(jù)不是待排序數(shù)據(jù)則指向上一次的待排序數(shù)據(jù)；末端指向需要處理的數(shù)據(jù)，當(dāng)然這個(gè)數(shù)據(jù)不一定是待排序數(shù)據(jù)，如果是則會(huì)馬上被繪制為虛線，不是的話則不變。進(jìn)入InsertSort函數(shù)后，第一件事就是擦除上次的操作線，然后會(huì)進(jìn)入一個(gè)大的if語(yǔ)句，這里是因?yàn)槲以O(shè)置了一個(gè)標(biāo)志位sign，它的作用把定時(shí)器再次分為兩次操作，其賦值為01變換。當(dāng)sign=1時(shí)，操作線指向下一數(shù)據(jù)，如果滿足待排序條件，這里條件就是其值小于前面數(shù)據(jù)值，滿足條件情況下，就將其畫(huà)成虛線，表示即將對(duì)其進(jìn)行插入操作。然后更新ptnow[4]，調(diào)整操作線，具體如圖3_3_1所示。當(dāng)sign=0時(shí)，就是排序的關(guān)鍵了，如果數(shù)據(jù)滿足待排序原則，那么用一變量?jī)?chǔ)存當(dāng)前值，之后從后往前遍歷，遇到比關(guān)鍵字大的數(shù)據(jù)就后移，一直反復(fù)操作，直到找到合適位置，停止移動(dòng)，把關(guān)鍵字插入到該位置，繼續(xù)讓其成虛線狀，這能讓用戶直觀的觀察到具體的插入位置，如下圖的圖3.3.1。圖3.3.1圖3.3.2程序跳出if語(yǔ)句后，會(huì)對(duì)sign進(jìn)行切換操作，還有操作線數(shù)據(jù)點(diǎn)的保存，以便下次進(jìn)入時(shí)擦除它。這樣一次操作就算完成，通過(guò)countx++，實(shí)現(xiàn)向后連續(xù)操作，通過(guò)它耶可以判斷是否排序完成。2.簡(jiǎn)單選擇排序與直接插入排序所不同的是，操作線會(huì)跟隨正在做比較的兩根數(shù)據(jù)線，如果遍歷到的數(shù)據(jù)線需要交換就會(huì)被畫(huà)為虛線。為排序前數(shù)據(jù)如圖3_3_3所示，很容易看出所有數(shù)據(jù)里面間夾著小數(shù)據(jù)量，好像縫隙一樣。隨著排序的進(jìn)行這樣的情況會(huì)越來(lái)越少，如圖3_3_4，因?yàn)樾?shù)據(jù)都被一個(gè)一個(gè)交換到前面去了，后面的數(shù)據(jù)參差愈是小，這就是選擇排序的原理，一次一次地尋找最小的數(shù)據(jù)交換到前面。圖3.3.3圖3.3.4四、本章結(jié)束語(yǔ)由實(shí)際效果來(lái)看，采用數(shù)據(jù)線和操作線的動(dòng)態(tài)演示是可行的，能直觀的演示整個(gè)排序過(guò)程，而且程序還提供了過(guò)程數(shù)據(jù)和排序后的數(shù)據(jù)參考，圖像和數(shù)字結(jié)合的觀察效果還是很好的，在排序算法教學(xué)或者理解上能有很大的幫助。結(jié)論目標(biāo)在現(xiàn)代信息技術(shù)的高速發(fā)展,實(shí)際工程應(yīng)用基本都面臨著大量的無(wú)序信息。若沒(méi)有排序算法，大量的時(shí)間將花費(fèi)在數(shù)據(jù)查找過(guò)程。因此，高效的排序算法在工程應(yīng)用中具有重要的意義。本課題在對(duì)數(shù)據(jù)結(jié)構(gòu)和算法分析理論的了解的基礎(chǔ)上，通過(guò)學(xué)習(xí)多種排序算法（選擇