【正文】 （雙向冒泡排序就是在排序的過程中交替改變掃描方向。 p=pnext。 int temp。 ?基數(shù)排序是穩(wěn)定的排序方法。 t=e[j]。 /* 隊(duì)列指示器置初值 */ while (i!=0) /*進(jìn)行分配 */ { t=r[p].key[i]。 i++) r[i].next=i+1。 數(shù)據(jù)類型 ?設(shè)基數(shù)排序中記錄的數(shù)據(jù)類型如下： struct element { int key[d]。 ?設(shè)一組關(guān)鍵字的個(gè)數(shù)為 n（即卡片的張數(shù)），每個(gè)關(guān)鍵字的位數(shù)為 d，每位數(shù)可能有 rd種取值，則這種排序方法需進(jìn)行 d趟“分散”，每趟檢查 n張卡片的某一位數(shù)，并按此位數(shù)值的不同，將卡片分別放到 rd個(gè)卡片盒中。 merge (r2, r1, s, k, t)。 /*余的部分 copy到 while (j=t) /*r2[]中 r2[k++]=r[j++]。 /*并成一個(gè)有序序列 r2[s… t] i=s。 /*元素交換 } } 堆排序算法分析 ?其運(yùn)行時(shí)間主要消耗在建初始堆和進(jìn)行反復(fù)的篩選上。 ?例： 堆排序算法 void heapsort (r[], n) { int i。amp。 ?設(shè)某堆的結(jié)點(diǎn)數(shù)共有 n個(gè)，順序?qū)⑺鼈兇嫒胍痪S數(shù)組 r[] 中。當(dāng)時(shí)他就發(fā)現(xiàn)了以上的問題，他在文章中建議用兩種方法改進(jìn)：產(chǎn)生一個(gè)隨機(jī)數(shù)，或選擇一個(gè)小樣本中值。 r[i]=x。 if (ij) /*已找到了滿足 { r[i]=r[j]。 ?圖 過程。 快速排序 ?快速排序是由冒泡排序改進(jìn)而得到的，又稱為分區(qū)交換排序，是目前內(nèi)部排序中速度較快的方法。 while((k0) amp。 ?基本思想：把整個(gè)文件分成若干個(gè)較小的子文件，對(duì)每個(gè)子文件進(jìn)行直接插入排序；在文件的記錄達(dá)到基本有序時(shí)，再對(duì)整個(gè)文件進(jìn)行一次直接插入排序。 j++) if (r[ j]. key r[ k]. key) k=j。第 i 趟掃描只需將該位置的元素與第 i個(gè)元素交換即可。 r[j] ? r[j+1]。 j++) if (r[j+1].key r[j].key) r[j] ? r[j+1]。 性能分析 R[0]的使用： ?把 R[I]放在 R[0]中， R[I]的位置用來向后移動(dòng)記錄 ?比較過程中，又防止下標(biāo) j 出界，起到了監(jiān)視哨的作用。 for( i=2。 ?大多數(shù)的排序方法數(shù)據(jù)是存儲(chǔ)在內(nèi)存中，并在內(nèi)存中加以處理的，這種排序方法叫 內(nèi)部排序。數(shù)據(jù)結(jié)構(gòu) 第 九 章 排序 第九章 排序 ?知 識(shí) 點(diǎn) 排序的基本概念 三種簡(jiǎn)單的排序方法：冒泡排序、直接選擇排序、簡(jiǎn)單插入排序 堆排序 快速排序 歸并排序 基數(shù)排序 ?難 點(diǎn) 堆排序 快速排序 歸并排序 基數(shù)排序 ?要 求 熟練掌握以下內(nèi)容： 熟悉各種內(nèi)部排序方法的基本思想和特點(diǎn) 各種排序方法的優(yōu)缺點(diǎn)、時(shí)、空性能和適用場(chǎng)合 熟悉并掌握三種簡(jiǎn)單排序算法、快速排序算法和堆排序算法 了解以下內(nèi)容： 二路歸并排序算法 基數(shù)排序算法 排序的歷史 ?大約公元前 300年，在愛琴島上發(fā)現(xiàn)了若干個(gè)表 , 給出了宗教中的人名 .這些表按字母排列 ,但只按頭一個(gè)字母排列 .(單個(gè)字母的字符排序 ) ?約公元前 200年 , 巴比倫人艾娜基比特 安奴(InakibitAnu),用陶土做的 ,含有 500個(gè)以上高精度的六十進(jìn)制數(shù)及其倒數(shù)表 ,并把它排列成詞典順序 .(數(shù)字排序 ) ?在許多圣經(jīng)贊美詩中 ,遵循一個(gè)嚴(yán)格的字母序列 ,頭一個(gè)詩句以 a開始 ,第二個(gè)詩句以 b開始 ,…… 有助于記憶 .(單個(gè)字母的字符排序 ) ? 公元 134135年 ,某些希臘文稿包含一些分類賬的片斷 ,他列出了按頭兩個(gè)字母排序的納稅人的名字 . ? …… ? 對(duì)于今天排序技術(shù)起源的探索 ,是 19世紀(jì)末發(fā)明的排序機(jī)器 .1880年 ,美國(guó)人口普查 ,數(shù)據(jù)處理成為令人頭痛的問題 — 無法在當(dāng)年完成 . 赫爾曼 .霍勒里斯 (Herman Hollerith),一位人口統(tǒng)計(jì)局的 20歲的職員 ,發(fā)明了一臺(tái)巧妙的制表機(jī) ,用 100臺(tái)這樣的制表機(jī) ,成功的完成了人口普查的統(tǒng)計(jì)問題 . ? …… 計(jì)算機(jī)的誕生和發(fā)展促進(jìn)了排序技術(shù)的發(fā)展 ? 1945年 ,馮 .諾依曼 (Von Neuman)編制了一個(gè)用于內(nèi)部合并排序的程序 這也是存儲(chǔ)程序計(jì)算機(jī)的第一個(gè)程序 . ?…… 如果我能把過去幾年內(nèi)所產(chǎn)生的大量的關(guān)于排序的材料的要旨都加以排序 ,編排出次序來 ,那我就心滿意足了 . ( 1955) 排序的概念 ?將一組雜亂無序的數(shù)據(jù)按一定的規(guī)律順次排列起來叫做 排序 (sort)。 ?如果在排序過程中，數(shù)據(jù)的主要部分存放在外存儲(chǔ)器中（如軟盤、硬盤、磁帶），借助內(nèi)存進(jìn)行內(nèi)、外存數(shù)據(jù)交換，逐步排列記錄之間的順序，則稱之為 外部排序。 i=n。 ?可以看出 ， 該算法是穩(wěn)定的 。 } } 修正后的冒泡排序算法 void bubblesort(r[ ], n) { int i, j, flag。 } if (flag==1) return。這樣掃描 n1次，處理元素的個(gè)數(shù)從 n逐次減 1。 if ( i!=k) r[i] ? r[k]。 ?例： 9 13 8 2 5 13 7 1 4 11 希爾排序算法 Void shellsort (r[], n, dk[], t) /*dk[]增量數(shù)組 /*t:增量數(shù)組的元素?cái)?shù) { for (i=1。amp。 ?基本思想：在待排序的 n個(gè)數(shù)據(jù)中任取一個(gè)數(shù)據(jù)（通常取第一個(gè)數(shù)據(jù)），把該數(shù)據(jù)和文件中的所有記錄比較，所有比該數(shù)據(jù)小的放置在前一部分，所有比它大的放置在后一部分，即該數(shù)據(jù)排在這兩部分的中間。 ?圖中括號(hào)中的數(shù)據(jù)表示正進(jìn)行比較的兩個(gè)數(shù)據(jù)，左面一個(gè)的下標(biāo)為 i，右面一個(gè)的下標(biāo)為j。 /*r[j].keyx的 r[j] i++。 return(i)。 1969年，辛格爾頓就遵循了這一建議，采用R[1].key, R[n].key, R[n/2].key的中間值，故稱作“三者取中”法。根據(jù)順序表示二叉樹的特點(diǎn)，除下標(biāo)為 1的結(jié)點(diǎn) (根結(jié)點(diǎn) )沒有父結(jié)點(diǎn)以外，其余下標(biāo)為 j 的結(jié)點(diǎn)（ 2≤j≤n）都有父結(jié)點(diǎn)，父結(jié)點(diǎn)的下標(biāo)為 i= 。 r[j].keyr[j+1].key)) j++。 for (i=n/2。對(duì) n個(gè)元素，樹的深度 k=?log2n? +1，篩選算法中關(guān)鍵字的比較次數(shù)最多為 2（ k1），共調(diào)用了 n1次，所以總的比較次數(shù)小于 2n（ ?log2n?）次；在建初始堆時(shí)，因?yàn)榈?h（ 1≤h≤k1）層最多有 2h1個(gè)元素，而每一個(gè)元素的最大調(diào)整次數(shù)為 kh，故總的調(diào)整次數(shù)不大于 4n。 j=m+1。 } ?上面