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

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