基于vb的排序算法比較

1、基于VB的排序算法比較（陳先紅湖北省仙桃市沔城高級中學）摘要：摘要：排序在程序設(shè)計中占有很重要的地位排序算法的好壞直接影響到程序的時間復(fù)雜度.本文通過VB設(shè)計出一個程序用來直觀地比較各種排序的優(yōu)劣.關(guān)鍵詞：關(guān)鍵詞：排序算法時間復(fù)雜度程序設(shè)計中圖類分號:TP312文獻標識碼:ATheComparisonofStingAlgithmsBasedonVBAbstract:Abstract:Stingisimptanttoprogramming

2、.Thestingalgithmhasgreatinfluenceonthetimecomplexityoftheproblem.AprogrammingbasedonVBisdesignedmanystingalgithmsarecomparedinthearticle.KeyKeywds:wds:stingalgithmtimecomplexityprogramming1.1.引言引言排序是計算機程序設(shè)計中的一種重要操作它的功能是將

3、一個數(shù)據(jù)元素（或記錄）的任意序列重新排列成一個按關(guān)鍵字有序的序列.在計算機數(shù)據(jù)處理中特別是在事務(wù)處理中排序(Sting)占了很大的比重一般認為有14的時間用在排序上而對安裝程序多達50%的時間花費在對表的排序上.計算機在處理過程中有大量時間用于排序和查找工作上.因此研究各種排序方法是計算機工作者的重要工作之一.2.2.各種算法思想各種算法思想2.12.1冒泡排序冒泡排序(Bubble(BubbleSt)St):即首先將第一個記錄的關(guān)鍵字

4、和第二個記錄的關(guān)鍵字進行比較若為逆序則將兩個記錄交換之然后比較第二個記錄和第三個記錄的關(guān)鍵字.依次類推直至第n1個記錄和第n個記錄的關(guān)鍵字進行過比較為止.上述過程稱做第一趟起泡排序其結(jié)果是使關(guān)鍵字最大的記錄被安置到最后一個記錄的位置上.然后進行第二趟起泡排序?qū)η皀1個記錄進行同樣操作其結(jié)果是使關(guān)鍵字次大的記錄被安置到第n1個記錄的位置上.重復(fù)上述過程直到“在一趟排序過程中沒有進行過交換的記錄操作”.2.22.2簡單選擇排序簡單選擇排序(

5、Simple(SimpleionionSt)St)：每一趟在ni1(i=12…n1)個記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個記錄.一趟簡單選擇簡單排序的操作為：通過ni次關(guān)鍵字間的比較從ni1個記錄中選出關(guān)鍵字最小的記錄并和第i（1=i=n）個記錄交換之.2.32.3直接插入排序直接插入排序(Straight(StraightionionSt):St):直接插入排序是一種最簡單的排序方法它的基本操作是將一個記錄插入到已經(jīng)排好序的

6、有序表中從而得到一個新的、記錄數(shù)增一得有序表.一般情況下其第i趟直接插入排序的操作為：在含有i1個記錄的有序子序列r[1..i1]中插入一個記錄r[i]后變成含有i個記錄的有序子序列r[1..i]；并且和順序查找類似為了在查找插入位置的過程中避免數(shù)組下標出界在r[0]處設(shè)置監(jiān)視哨.在自i1起往前搜索的過程中可以同時后移記錄；整個排序過程為進行n1趟插入即：先將序列中第1個記錄看成是一個有序的子序列然后從第2個記錄起逐個進行插入直至整個序

7、列變成按關(guān)鍵字非遞減有序序列為止.2.42.4希爾排序希爾排序(Shell’s(Shell’sSt)St):希爾排序方法又稱為縮小增量排序.該方法的基本思想是：先將整個待排記錄序列分割成為若干個子序列分別進行直接插入排序待整個序列中的記錄“基本有序”時再對全體記錄進行一次直接插入排序.至此希爾排序結(jié)束整個交換次數(shù)2618982411360269866表（一）100個數(shù)升序排列所得到的數(shù)據(jù)記錄方法性能冒泡排序簡單選擇排序直接插入排序希爾排

8、序快速排序堆排序歸并排序耗時（ms）612834314318681780610712循環(huán)次數(shù)6103350125074115972335530111217150275730交換次數(shù)60981204980596732152990119650024912表（二）5000個數(shù)升序排列所得到的數(shù)據(jù)記錄由上述兩個表可知在n較小各種內(nèi)部排序相差不大.若n較大排序方法的優(yōu)越性表現(xiàn)比較突出由表（二）可以發(fā)現(xiàn)：時間復(fù)雜度為O()的排序方法：快速排序、堆2

9、lognn排序或歸并排序耗費時間較少.其它排序耗費的時間都較長.鑒于對各種算法的分析可以發(fā)現(xiàn)：當待排序的關(guān)鍵字是隨機分布時快速排序的平均時間最短；堆排序雖不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況但它需要建堆的過程.這兩種排序都是不穩(wěn)定的.歸并排序是穩(wěn)定的排序算法但它有一定數(shù)量的數(shù)據(jù)移動所以把它與插入排序組合先獲得一定長度的序列然后再合并在效率上將有所提高.5.5.總結(jié)總結(jié)內(nèi)部排序的方法很多，但就其全面的性能而言，很難找到一種被認為是最好的方法

10、，每一種方法都有各自的優(yōu)缺點，適合不同的環(huán)境和要求下使用，如待排序列的初始狀態(tài)、記錄數(shù)目n、記錄的大小(規(guī)模)、關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)、對穩(wěn)定性的要求、語言工具的條件、存儲結(jié)構(gòu)、時間和輔助空間復(fù)雜度等.參考文獻[1].嚴蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學出版社，1997[2].陳惟斌張軍《VB開發(fā)指南》[M].北京：清華大學出版社，2001[3].樊吉亮.排序算法的比較與選擇研究[J].青海師范大學20081：81822