基于vb的排序算法比較

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

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

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

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

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

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

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

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

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

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