資源描述:
《基于vb的排序算法比較》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、基于VB的排序算法比較(陳先紅湖北省仙桃市沔城高級(jí)中學(xué))摘要:排序在程序設(shè)計(jì)中占有很重要的地位,排序算法的好壞,直接影響到程序的時(shí)間復(fù)雜度.本文通過(guò)VB設(shè)計(jì)出一個(gè)程序,用來(lái)直觀地比較各種排序的優(yōu)劣.關(guān)鍵詞:排序算法時(shí)間復(fù)雜度程序設(shè)計(jì)中圖類分號(hào):TP312文獻(xiàn)標(biāo)識(shí)碼:ATheComparisonofSortingAlgorithmsBasedonVBAbstract:Sortingisimportanttoprogramming.Thesortingalgorithmhasgreatinfluenceonthetimecomplex
2、ityoftheproblem.AprogrammingbasedonVBisdesignedandmanysortingalgorithmsarecomparedinthearticle.Keywords:sortingalgorithm;timecomplexity;programming1.引言排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作,它的功能是將一個(gè)數(shù)據(jù)元素(或記錄)的任意序列,重新排列成一個(gè)按關(guān)鍵字有序的序列.在計(jì)算機(jī)數(shù)據(jù)處理中,特別是在事務(wù)處理中,排序(Sorting)占了很大的比重,一般認(rèn)為有1/4的時(shí)間用在排序上,而對(duì)
3、安裝程序,多達(dá)50%的時(shí)間花費(fèi)在對(duì)表的排序上.計(jì)算機(jī)在處理過(guò)程中,有大量時(shí)間用于排序和查找工作上.因此,研究各種排序方法是計(jì)算機(jī)工作者的重要工作之一.2.各種算法思想2.1冒泡排序(BubbleSort):即首先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字進(jìn)行比較,若為逆序,則將兩個(gè)記錄交換之,然后比較第二個(gè)記錄和第三個(gè)記錄的關(guān)鍵字.依次類推,直至第n-1個(gè)記錄和第n個(gè)記錄的關(guān)鍵字進(jìn)行過(guò)比較為止.上述過(guò)程稱做第一趟起泡排序,其結(jié)果是使關(guān)鍵字最大的記錄被安置到最后一個(gè)記錄的位置上.然后進(jìn)行第二趟起泡排序,對(duì)前n-1個(gè)記錄進(jìn)行同樣操作,其
4、結(jié)果是使關(guān)鍵字次大的記錄被安置到第n-1個(gè)記錄的位置上.重復(fù)上述過(guò)程直到“在一趟排序過(guò)程中,沒有進(jìn)行過(guò)交換的記錄操作”.2.2簡(jiǎn)單選擇排序(SimpleSelectionSort):每一趟在n-i+1(i=1,2,…,n-1)個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄.一趟簡(jiǎn)單選擇簡(jiǎn)單排序的操作為:通過(guò)n-i次關(guān)鍵字間的比較,從n-i-1個(gè)記錄中選出關(guān)鍵字最小的記錄,并和第i(1=
5、將一個(gè)記錄插入到已經(jīng)排好序的有序表中,從而得到一個(gè)新的、記錄數(shù)增一得有序表.一般情況下其第i趟直接插入排序的操作為:在含有i-1個(gè)記錄的有序子序列r[1..i-1]中插入一個(gè)記錄r[i]后,變成含有i個(gè)記錄的有序子序列r[1..i];并且,和順序查找類似,為了在查找插入位置的過(guò)程中避免數(shù)組下標(biāo)出界,在r[0]處設(shè)置監(jiān)視哨.在自i-1起往前搜索的過(guò)程中,可以同時(shí)后移記錄;整個(gè)排序過(guò)程為進(jìn)行n-1趟插入,即:先將序列中第1個(gè)記錄看成是一個(gè)有序的子序列,然后從第2個(gè)記錄起逐個(gè)進(jìn)行插入,直至整個(gè)序列變成按關(guān)鍵字非遞減有序序列為止.2.4希
6、爾排序(Shell’sSort):希爾排序方法又稱為縮小增量排序.該方法的基本思想是:先將整個(gè)待排記錄序列分割成為若干個(gè)子序列分別進(jìn)行直接插入排序,待整個(gè)序列中的記錄“基本有序”時(shí),再對(duì)全體記錄進(jìn)行一次直接插入排序.至此,希爾排序結(jié)束,整個(gè)序列的記錄已經(jīng)按關(guān)鍵字非遞減有序排列.2.5快速排序(QuickSort):快速排序是冒泡排序的改進(jìn)算法.它的基本思想是,通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分,其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小,則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序,以達(dá)到整個(gè)序列有序.2.6堆排序(HeapSo
7、rt):堆排序分為兩個(gè)步驟:第一步,根據(jù)初始輸入數(shù)據(jù),利用堆的調(diào)整算法形成初始堆,第二步,通過(guò)一系列的對(duì)象交換和重新調(diào)整堆進(jìn)行排序.最大堆的第一個(gè)對(duì)象V[0]具有最大的關(guān)鍵碼,將V[0]與V[n]對(duì)調(diào),把具有最大關(guān)鍵碼的對(duì)象交換到最后,再對(duì)前面的n-1個(gè)對(duì)象,使用堆的調(diào)整算法,重新建立最大堆.結(jié)果具有次最大關(guān)鍵碼的對(duì)象又上浮到堆頂,即V[0]位置.再對(duì)調(diào)V[0]和V[n-1].如此反復(fù)執(zhí)行,最后得到全部排序好的對(duì)象序列.2.7歸并排序(MergingSort):“歸并”的含義是將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)兩個(gè)或兩個(gè)以上的有序
8、表組合成一個(gè)新的有序表.假設(shè)初始序列含有n個(gè)記錄,則可看成是n個(gè)有序的子序列,每個(gè)子序列的長(zhǎng)度為1,然后兩兩歸并,得到個(gè)長(zhǎng)為2或1的有序子序列,再兩兩歸并,......,如此重復(fù),直至得到一個(gè)長(zhǎng)度為n的有序序列為止,這種排序方法稱為2-路歸并排序.