【導(dǎo)讀】大約公元前300年，在愛琴島上發(fā)現(xiàn)了若干個。表,給出了宗教中的人名.這些表按字母排列,約公元前200年,巴比倫人艾娜基比特-安奴。在許多圣經(jīng)贊美詩中,遵循一個嚴(yán)格的字母序。公元134-135年,某些希臘文稿包含一些分類賬的片斷,他列出了按頭兩個字母排序的納稅人的名字.對于今天排序技術(shù)起源的探索,是19世紀(jì)末發(fā)明的排序?？谄詹榈慕y(tǒng)計問題.1945年,馮.諾依曼編制了一個用。算機的第一個程序.來,那我就心滿意足了.將一組雜亂無序的數(shù)據(jù)按一定的規(guī)律順次排列。依據(jù)的字段稱之為關(guān)鍵字。大多數(shù)的排序方法數(shù)據(jù)是存儲在內(nèi)存中，并。如果在排序過程中，數(shù)據(jù)的主要部分存放在。之間的順序，則稱之為外部排序。為穩(wěn)定的，否則稱為不穩(wěn)定的。較快的運算速度。比較過程中，又防止下標(biāo)j出界，起到了監(jiān)視哨。重復(fù)以上過程，直到?jīng)]有記錄交換為止。每趟掃描開始前將其置1。少出現(xiàn)一次互換時，將其置0。

　　

【正文】 else r[e[t]].next=p。 基數(shù)排序算法續(xù) e[t]=p。 p=r[p].next。 } j=0。 while (f[j]==0) j++。 /*尋找第一個非空隊列 */ p=f[j]。 t=e[j]。 while (jrd) 基數(shù)排序算法續(xù) { j++。 if (f[j]!=0) { r[t].next=f[j]。 t=e[j]。 } /*進行收集 */ } r[t].next=0。 /*收尾 */ } } 圖 初始狀態(tài) ?現(xiàn)以圖 306， 028，009， 948， 505， 917， 721， 430， 390為例說明 radixsort函數(shù)的執(zhí)行過程。 028 p 306 009 948 505 917 721 430 3 9 0 0 第一趟分配后各隊列情況 f [ 0 ] r [ 0 ] 430 390 f [ 1 ] r [ 1 ] 721 f[2] r[2] N U L L f[3] r[3] N U L L f[4] r[4] N U L L f [ 5 ] r [ 5 ] 505 f [ 6 ] r [ 6 ] 306 f [ 7 ] r [ 7 ] 917 f [ 8 ] r [ 8 ] 028 948 f [ 9 ] 009 r [ 9 ] 第一趟收集后的情況 390 p 430 721 505 306 917 028 948 0 0 9 0 第三趟分配后各隊列情況 f [ 0 ] r [ 0 ] 009 028 f[2] r[2] N U L L f[1] r[1] N U L L f [ 3 ] r [ 3 ] 306 390 f [ 4 ] r [ 4 ] 430 f [ 5 ] r [ 5 ] 505 f[6] r[6] N U L L f[8] r[8] N U L L f [ 7 ] r [ 7 ] 721 f [ 9 ] r [ 9 ] 917 948 第三趟收集后的情況 028 p 009 306 390 430 505 721 917 948 0 基數(shù)排序分析 ?采用基數(shù)排序需進行 d趟關(guān)鍵字的分散和收集過程，每趟運算時間為 O(n+rd)，故總的時間復(fù)雜性為 O(d(n+rd))。若基數(shù) rd相同，對于關(guān)鍵字?jǐn)?shù)目較多但位數(shù)較少的情況，采用基數(shù)排序較為適用。 ?基數(shù)排序是穩(wěn)定的排序方法。 返回 例 ?已知序列{60,20,31,1,5,44,55,61,200,30,80,150,4,29},寫出采用快速排序算法排序的每一趟的結(jié)果。 例 ?解 : 快速排序各趟的結(jié)果如下 : [60 20 31 1 5 44 55 61 200 30 80 150 4 29] [29 20 31 1 5 44 55 4 30] 60 [80 150 200 61] [4 20 5 1] 29 [44 55 31 30] 60 [61] 80 [200 150] [1] 4 [5 20] 29 [30 31] 44 [55] 60 61 80 150 [200] 1 4 5 [20] 29 30 [31] 44 55 60 61 80 150 200 1 4 5 20 29 30 31 44 55 60 61 80 150 200 例 ?已知序列 {26,5,77,1,61,11,59,15,48,19}寫出采用歸并排序算法排序的每一趟的結(jié)果。 ?解 : 快速排序各趟的結(jié)果如下 : [26] [5] [77] [1] [61] [11] [59] [15] [48] [19] [5 26] [1 77] [11 61] [15 59] [19 48] [1 5 26 77 ] [11 15 59 61] [19 48] [1 5 11 15 26 59 61 77] [19 48] [1 5 11 15 19 26 48 59 61 77] 例 ?設(shè)計一個用單鏈表作存儲結(jié)構(gòu)的選擇排序算法。 ?解 :依題義單鏈表定義如下 : struct node { int key。 struct node *next。 }。 ?實現(xiàn)本題功能的函數(shù)如下 : void select(node *head) { node *p,*q,*min。 int temp。 p=head。 while(p!=NULL) { min=p。 q=pnext。 while(q!=NULL) { if(qkeyminkey) min=q。 } temp=pkey。 pkey=minkey。 minkey=temp。 p=pnext。 } } 返回 小 結(jié) ?排序 ?冒泡排序 ?直接選擇排序 ?簡單插入排序 ?堆排序 ?快速排序 ?歸并排序 ?基數(shù)排序 返回 習(xí)題與練習(xí) ?一、基本知識題 1. 解釋下列概念 (1) 排序 (2) 內(nèi)部排序 (3) 堆 (4) 穩(wěn)定排序 2. 回答下面問題 (1) 5000個無序的數(shù)據(jù)，希望用最快速度挑選出其中前 10個最大的元素，在快速排序、堆排序、歸并排序和基數(shù)排序中采用哪種方法最好？為什么？ (2) 大多數(shù)排序算法都有哪兩個基本操作？ 3. 已知序列 {17， 25， 55， 43， 3， 32， 78， 67，91}，請給出采用冒泡排序法對該序列作遞增排序時每一趟的結(jié)果。 4. 已知序列 {491， 77， 572， 16， 996， 101， 863，258， 689， 325}，請分別給出采用快速排序、堆排序和基數(shù)排序法對該序列作遞增排序時每一趟的結(jié)果。 5. 已知序列 {86， 94， 138， 62， 41， 54， 18， 32}，請給出采用插入排序法對該序列作遞增排序時，每一趟的結(jié)果。 6. 已知序列 {27， 35， 11， 9， 18， 30， 3， 23， 35，20}，請給出采用歸并排序法對該序列作遞增排序時的每一趟的結(jié)果。 ?二、算法設(shè)計題 1. 一個線性表中的元素為全部為正或者負整數(shù)，試設(shè)計一算法，在盡可能少的時間內(nèi)重排該表，將正、負整數(shù)分開，使線性表中所有負整數(shù)在正整數(shù)前面。 2. 設(shè)計一個用單鏈表作存儲結(jié)構(gòu)的直接插入排序算法。 3. 試設(shè)計一個算法實現(xiàn)雙向冒泡排序。（雙向冒泡排序就是在排序的過程中交替改變掃描方向。） 4. 設(shè)一個一維數(shù)組 A[n]中存儲了 n個互不相同的整數(shù)，且這些整數(shù)的值都在 0到 n1之間，即 A中存儲了從 0到 n1這 n個整數(shù)。試編寫一算法將 A排序，結(jié)果存放在數(shù)組 B[n]中，要求算法的時間復(fù)雜性為 O(n)。 返回