【專題】常見幾種排序法比較

常見幾種排序方法復(fù)習(xí)冒泡法、選擇法、插入法、桶排序、索引排序比較方向：從右往左比較，先確定左側(cè)數(shù)組元素規(guī)則：從右往左先定左比較方向：從左往右比較，先確定數(shù)組元素a(i)規(guī)則：無論左右先定i總是拿a(i)右側(cè)數(shù)據(jù)來比較k=jFori＝1Ton－1Forj＝1Ton-iIfa(j)>a(j+1)Thentemp＝a(j+1)a(j+1)＝a(j)a(j)＝tempEndIfNextjNexti比較方向：從左往右比較，先確定右側(cè)數(shù)組元素規(guī)則：從左往右先定右冒泡法變式一：Fori＝nTo2step-1Forj＝1Toi-1Ifa(j)>a(j+1)Thentemp＝a(j+1)a(j+1)＝a(j)a(j)＝tempEndIfNextjNexti比較方向：從左往右比較，先確定右側(cè)數(shù)組元素規(guī)則：從左往右先定右冒泡法變式二：Fori＝nTo2step-1Forj＝nTon-i+2step-1Ifa(j)>a(j-1)Thentemp＝a(j-1)a(j-1)＝a(j)a(j)＝tempEndIfNextjNexti比較方向：從右往左比較，先確定左側(cè)數(shù)組元素規(guī)則：從右往左先定左冒泡法變式三：Fori＝1Ton—1k＝iForj＝nToi＋1

step-1

Ifa(j)＜a(k)Thenk＝j(luò)NextjIfk＜＞iThent＝a(i)：a(i)＝a(k)：a(k)＝tEndIfNexti比較方向：從右往左比較，先確定數(shù)組元素a(i)規(guī)則：無論左右先定i選擇法變式一：總是拿a(i)右側(cè)數(shù)據(jù)來比較Fori＝nTo2step-1k＝iForj＝

1Toi-1

Ifa(j)＜a(k)Thenk＝j(luò)NextjIfk＜＞iThent＝a(i)：a(i)＝a(k)：a(k)＝tEndIfNexti比較方向：從左往右比較，先確定數(shù)組元素a(i)規(guī)則：無論左右先定i選擇法變式二：總是拿a(i)左側(cè)數(shù)據(jù)來比較Fori＝nTo2step-1k＝iForj＝

i-1To1

step-1Ifa(j)＜a(k)Thenk＝j(luò)NextjIfk＜＞iThent＝a(i)：a(i)＝a(k)：a(k)＝tEndIfNexti比較方向：從右往左比較，先確定數(shù)組元素a(i)規(guī)則：無論左右先定i選擇法變式三：總是拿a(i)左側(cè)數(shù)據(jù)來比較核心問題：無論哪一種排序，每一輪(遍)排序，都是將最大或最小的放在數(shù)組剩余元素最左側(cè)或最右側(cè)，應(yīng)當(dāng)確保接下來每一輪(遍)比較是對所有剩余數(shù)組元素的比較，不能有遺漏。某VB程序段如下：Fori=1To3

Forj=i+1To6

Ifa(j)<a(j-1)Thent=a(j):a(j)=a(j-1):a(j-1)=tNextjNexti數(shù)組元素a(1)到a(6)的值依次為“99，100，30，21，43，19”，經(jīng)過該程序段“加工”后a(4)、a(5)、a(6)的值依次為__________________解析：此例并不是冒泡法排序，標(biāo)準(zhǔn)的冒泡法排序，從左往右比較，每次都應(yīng)當(dāng)是從最左邊固定元素往右（如FORi=1to……），右側(cè)參與比較的數(shù)據(jù)每一遍減少一個，反之，從右往左比較，每次都應(yīng)當(dāng)是從最右邊固定元素往左（如FORi=nto……），左側(cè)參與比較的數(shù)據(jù)每一遍減少一個此例當(dāng)i=1時，第一遍比較，99與100比較，不用交換，然后100與后面的每一個都交換，數(shù)組值變?yōu)椋?9，30，21，43，19，100，第二遍，99不再參加比較，30與21交換，43與19交換，變?yōu)椋?9，21，30，19，43，100，第三遍，99，21不再參加比較，30與19交換，變?yōu)椋?9，21，19，30，43，100，所以答案為：30，43，100插入法排序核心代碼（升序為例）Fori=2To10

tmp=a(i)j=i-1DoWhiletmp<a(j)a(j+1)=a(j)j=j-1Loopa(j+1)=tmpNexti插入排序變形(升序）升序為例fori=2ton

tmp=a(i)

j=1

dowhiletmp>=a(j)

j=j+1

ifj=ithenexitdo

loop

fork=itoj+1step-1

a(k)=a(k-1)

nextk

a(k)=tmpnexti桶排序的算法思想最快最簡單的排序：桶排序期末考試完了老師要將同學(xué)們的分?jǐn)?shù)按照從高到低排序。班上只有5個同學(xué)，這5個同學(xué)分別考了5分、3分、5分、2分和8分，考得真是慘不忍睹(滿分是10分)。接下來將分?jǐn)?shù)進行從大到小排序，排序后是85532。那么有沒有什么好方法編寫一段程序，讓計算機隨機讀入5個數(shù)然后將這5個數(shù)從大到小輸出。桶排序如下圖所示，桶排序的算法思想是這樣的：要對分?jǐn)?shù)進行排序，可以通過這樣的方法來實現(xiàn)，假設(shè)有11個桶，從0～10對桶進行編號。每出現(xiàn)一個數(shù)，就在對應(yīng)編號的桶中放一面小旗子，最后只要數(shù)數(shù)每個桶中有幾面小旗子就可以了。例如2號桶中有1面小旗子，表示2出現(xiàn)了一次；3號桶中有1面小旗子，表示3出現(xiàn)了一次；5號桶中有2面小旗子，表示5出現(xiàn)了兩次；8號桶中有1面小旗子，表示8出現(xiàn)了一次。桶排序

在輸出時，如果是升序排序，只要按照桶的編號，從小到大對桶進行檢查，如果發(fā)現(xiàn)桶里面只要有1面以上的小旗子(非空)就輸出桶的編號，如果有2面小旗子就連續(xù)輸出兩次，依次類推┈┈，這樣就快速地實現(xiàn)了升序排列。而如果是在排序時去除重復(fù)的數(shù)據(jù)，則更加簡單了。一般來說，桶的算法思想主要有以下三種功能：1.桶計數(shù)功能、2.桶排序功能、3.驗證數(shù)據(jù)是否存在。桶排序桶排序 桶排序的算法思想是：如圖a所示，有10個桶，編號為1～10。每出現(xiàn)一個數(shù)，就在對應(yīng)編號的桶中的放一面小旗子，最后只要看每個桶中有幾面小旗子就可以了。例如2號桶中有1面小旗子，表示2出現(xiàn)了一次；3號桶中有1面小旗子，表示3出現(xiàn)了一次；5號桶中有2面小旗子，表示5出現(xiàn)了兩次；8號桶中有1面小旗子，表示8出現(xiàn)了一次。最后只要按桶的編號順序逐次輸出非空的桶編號即可實現(xiàn)排序功能。桶排序桶排序小明利用桶排序的算法思想實現(xiàn)對5個[1，10]隨機整數(shù)的排序過程。實現(xiàn)上述功能的VB程序如圖b所示，請在劃線處填入合適的代碼。Dima(1To5)AsInteger

′數(shù)組a用于存放數(shù)字Dimb(1To10)AsInteger

′數(shù)組b相當(dāng)于桶PrivateSubForm_Load()

′生成5個[1，10]隨機整數(shù)

List1.Clear

Randomize

Fori＝1To5桶排序b(a(i))＝b(a(i))＋1桶排序b(i)Str(i)桶排序解析：本題考查VB基本程序閱讀及運算能力。①該程序使用了桶排序的算法思想，數(shù)組b相當(dāng)于桶，用于記錄數(shù)組a的小旗子的數(shù)量，也就是說數(shù)組a的值是數(shù)組b的下標(biāo)，數(shù)組b的值是數(shù)組a的值出現(xiàn)的次數(shù)，因此答案是b(a(i))＝b(a(i))＋1。請?zhí)貏e注意，該題涉及數(shù)組嵌套，即數(shù)組a的值是數(shù)組b的下標(biāo)。②如果小旗子的數(shù)量多于1面，則需要輸出多次，因此內(nèi)循環(huán)是控制輸出次數(shù)的，其終值由b(i)決定，當(dāng)b(i)＝0時，相當(dāng)于不輸出。③排序后輸出數(shù)據(jù)，只需要輸出桶的編號i并將其轉(zhuǎn)換為字符類型即可。索引排序索引排序是指不改變原始數(shù)組a()數(shù)據(jù)的前提下，引用新的數(shù)組b()用于記錄a()數(shù)組元素在所有元素中的排名（即索引），簡單說就是通過排序交換數(shù)組b()元素的值，比如升序排列，b(1)就要記錄下a()數(shù)組中值最小的元素的下標(biāo)，b(2)就要記錄下a()數(shù)組中值第二小的元素的下標(biāo)，依此類推。下標(biāo)原始原始下標(biāo)排序排序后i=1b(1)=1a(1)=9a(b(1))=9i=1b(1)=4a(b(1))=3a(4)=3i=2b(2)=2a(2)=6a(b(2))=6i=2b(2)=5a(b(2))=4a(5)=4i=3b(3)=3a(3)=8a(b(3))=8i=3b(3)=2a(b(3))=6a(2)=6i=4b(4)=4a(4)=3a(b(4))=3i=4b(4)=3a(b(4))=8a(3)=8i=5b(5)=5a(5)=4a(b(5))=4i=5b(5)=1a(b(5))=9a(1)=9索引排序之結(jié)合選擇法排序Dima(1To5)AsInteger，b(1To5)AsIntegera(1)=9:a(2)=6:a(3)=8:a(4)=3:a(5)=4Fori=1To5'初始化b(i)=iNextiFori=1To4k=iForj=i+1To5Ifa(b(k))>a(b(j))Thenk=jNextjIfk<>iThent=b(k):b(k)=b(i):b(i)=tNextiFori=1To5List1.AddItemStr(a(b(i)))Nexti索引排序之結(jié)合冒泡法排序Dima(1To5)AsInteger，b(1To5)AsIntegera(1)=9:a(2)