【正文】 內(nèi)的數(shù)據(jù)元素用直接插入法排序；小組的個(gè)數(shù)逐次縮小，當(dāng)完成了所有數(shù)據(jù)元素都在一個(gè)組內(nèi)的排序后排序過(guò)程結(jié)束。優(yōu)點(diǎn)：讓關(guān)鍵字值小的元素能很快前移，且序列若基本有序時(shí)，再用直接插入排序處理，時(shí)間效率會(huì)高很多。public static void shellSort(int[] a, int[] d, int numOfD){ int i, j, k, m, span。 int n = 。 m numOfD。 //取本次的增量值 for(k = 0。 k ++){ //共span個(gè)小組 for(i = k。 i = i + span){ temp = a[i+span]。 while(j 1 amp。 temp a[j]){ a[j + span] = a[j]。 } a[j + span] = temp。 時(shí)間效率：O(n(log2n)2) 空間效率：O（1）——因?yàn)閮H占用1個(gè)緩沖單元 算法的穩(wěn)定性：不穩(wěn)定 練習(xí)：1. 欲將序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的關(guān)鍵碼按字母升序重排，則初始d為4的希爾排序一趟的結(jié)果是？答： 原始序列： Q, H, C, Y, P, A, M, S, R, D, F, Xshell一趟后： P,A,C,S,Q,D,F,X,R,H,M,Y2. 以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫出執(zhí)行希爾排序（取d=5,3,1）算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)。常用的選擇排序算法： （1）直接選擇排序 （2）堆排序其基本思想 每經(jīng)過(guò)一趟比較就找出一個(gè)最小值，與待排序列最前面的位置互換即可。）優(yōu)缺點(diǎn)優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單缺點(diǎn)：每趟只能確定一個(gè)元素，表長(zhǎng)為n時(shí)需要n1趟例3：關(guān)鍵字序列T= （21，25，49，25*，16，08），請(qǐng)給出直接選擇排序的具體實(shí)現(xiàn)過(guò)程。 int temp。 for(i = 0。 i ++){ small = i。 j n。 //記住最小元素的下標(biāo) if(small != i){ //當(dāng)最小元素的下標(biāo)不為i時(shí)交換位置 temp = a[i]。 a[small] = temp。 空間效率：O（1）——沒(méi)有附加單元（僅用到1個(gè)temp)算法的穩(wěn)定性：不穩(wěn)定穩(wěn)定的直接選擇排序算法例：關(guān)鍵字序列T= （21，25，49，25*，16，08），請(qǐng)給出穩(wěn)定的直接選擇排序的具體實(shí)現(xiàn)過(guò)程。 int temp。 for(i = 0。 i++){ small = i。 j n。 //記住最小元素的下標(biāo) } if(small != i){ temp = a[small]。 j i。 a[i] = temp。 解釋：如果讓滿足以上條件的元素序列 （k０，k１，…，kn－１）順次排成一棵完全二叉樹，則此樹的特點(diǎn)是： 樹中所有結(jié)點(diǎn)的值均大于（或小于）其左右孩子，此樹的根結(jié)點(diǎn)（即堆頂）必最大（或最小）。終端結(jié)點(diǎn)（即葉子）沒(méi)有任何子女，無(wú)需單獨(dú)調(diào)整例：關(guān)鍵字序列T= (21，25，49，25*，16，08），請(qǐng)建最大堆。public static void createHeap(int[] a, int n, int h){ int i, j, flag。 i = h。 // j為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的下標(biāo) temp = a[i]。 while(j n amp。 flag != 1){ //尋找左右孩子結(jié)點(diǎn)中的較大者,j為其下標(biāo) if(j n 1 amp。 a[j] a[j + 1]) j++。 //標(biāo)記結(jié)束篩選條件 else{ //否則把a(bǔ)[j]上移 a[i] = a[j]。 j = 2 * i + 1。 } 利用上述createHeap（a,n,h）函數(shù)，初始化創(chuàng)建最大堆的過(guò)程就是從第一個(gè)非葉子結(jié)點(diǎn)a[i]開始，到根結(jié)點(diǎn)a[0]為止，循環(huán)調(diào)用createHeap（a,n,h）的過(guò)程。 for(int i = (n11) / 2。 i ) createHeap(a, n, i)。 再對(duì)前面的n1個(gè)對(duì)象，使用堆的調(diào)整算法，重新建立堆（調(diào)整根結(jié)點(diǎn)使之滿足最大堆的定義）。 再對(duì)調(diào)a[0]和a[n2]，然后對(duì)前n2個(gè)對(duì)象重新調(diào)整，…如此反復(fù)，最后得到全部排序好的對(duì)象序列。 int n = 。 //初始化創(chuàng)建最大堆 for(int i = n 1。 i ){ //當(dāng)前最大堆個(gè)數(shù)每次遞減1 //把堆頂a[0]元素和當(dāng)前最大堆的最后一個(gè)元素交換 temp = a[0]。 a[i] = temp。 //調(diào)整根結(jié)點(diǎn)滿足最大堆 }}堆排序算法分析：時(shí)間效率：O(nlog2n)。穩(wěn)定性： 不穩(wěn)定。A.{1,4,8,9,20,7,15,7*} B.{1,7,15,7*,4,8,20,9}C.{1,4,7,8,20,15,7*,9} 練習(xí)3：已知序列{503，87，512，61，908，170，897，275，653，462}，寫出采用堆排序?qū)υ撔蛄凶鞣沁f減排列時(shí)的排序過(guò)程。交換排序的主要算法有： 1) 冒泡排序 2) 快速排序 冒泡排序基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。例：關(guān)鍵字序列 T=(21，25，49，25*，16，08），請(qǐng)按從小到大的順序，寫出冒泡排序的具體實(shí)現(xiàn)過(guò)程。 int temp。 for(i = 1。amp。 i++){ flag = 0。 j ni。 temp = a[j]。 a[j+1] = temp。初態(tài)：31，15，9， 25，16， 28第1趟15，9，25，16， 28， 31第2趟9，15， 16， 25，28，31第3趟9，15， 16，25， 28，31基本思想：設(shè)數(shù)組a中存放了n個(gè)數(shù)據(jù)元素，low為數(shù)組的低端下標(biāo)，high為數(shù)組的高端下標(biāo)，從數(shù)組a中任取一個(gè)元素（通常取a[low]）做為標(biāo)準(zhǔn)元素，以該標(biāo)準(zhǔn)元素調(diào)整數(shù)組a中其他各個(gè)元素的位置，使排在標(biāo)準(zhǔn)元素前面的元素均小于標(biāo)準(zhǔn)元素，排在標(biāo)準(zhǔn)元素后面的均大于或等于標(biāo)準(zhǔn)元素。對(duì)這兩個(gè)子數(shù)組中的元素分別再進(jìn)行方法類同的遞歸快速排序。 例、關(guān)鍵字序列 T=(60，55，48，37，10，90，84，36），請(qǐng)按從小到大的順序，寫出快速排序的具體實(shí)現(xiàn)過(guò)程。 int temp。 j = high。 //取第一個(gè)元素為標(biāo)準(zhǔn)數(shù)據(jù)元素 while(i j){ //在數(shù)組的右端掃描 while(i j amp。 temp = a[j]) j。 i++。amp。 if(i j){ a[j] = a[i]。 } } a[i] = temp。 //對(duì)左端子集合遞歸 if(i high) quickSort(a, j+1, high)。練習(xí)：已知序列{503,87,512,61,908,170,897,275,653,462}，給出采用快速排序?qū)υ撔蛄凶鞣沁f減排序時(shí)每趟的結(jié)果。（ A ） (n) (nlog2n) C. O(log2n) (n2) {8,9,10,4,5,6,20,1,2}只能是（ C ）算法的兩趟排序后的結(jié)果。 A. 快速排序 {28,16,32,12,60,2,5,72}序列進(jìn)行快速排序，第一趟從小到大一次劃分結(jié)果為（B ） A.(2,5,12,16)26(60,32,72) B.(5,16,2,12)28(60,32,72) C.(2,16,12,5)28(60,32,72) D.(5,16,2,12)28(32,60,72) {18，16，14，12，10，8}進(jìn)行從小到大的排序，所需進(jìn)行的關(guān)鍵字比較總次數(shù)是（ B ）。A.{85，80，45，40，42，55} B.{85，80，55，40，42，45} C.{85，80，55，45，42，40} D.{85，55，80，42，45，40}第十章 文件　　文件是性質(zhì)相同的記錄的集合?！　∥募　　〔⒂袑?shí)時(shí)和批量處理兩種處理方式。存儲(chǔ)結(jié)構(gòu)是指文件在外存上的組織方式?；镜慕M織方式有：順序組織、索引組織、散列組織和鏈組織。常用的文件組織方式：順序文件、索引文件、散列文件和多關(guān)鍵字文件?！　z索功能的多寡和速度的快慢，是衡量文件操作質(zhì)量的重要標(biāo)志。主關(guān)鍵字有序稱順序有序文件，否則稱順序無(wú)序文件?！　№樞蛭募牟迦?、刪除和修改只能通過(guò)復(fù)制整個(gè)文件實(shí)現(xiàn)?！　∷饕琼樞蛭募械乃饕頌槌砻芩饕！　∪粲涗浐艽笫沟盟饕硪埠艽髸r(shí)，可對(duì)索引表再建立索引，稱為查找表?！　∷饕樞蛭募Ｓ玫挠袃煞N：　　 　　　　散列文件是利用散列存儲(chǔ)方式組織的文件，亦稱為直接存取文件。優(yōu)點(diǎn)是：文件隨機(jī)存放，記錄不需要排序；插入刪除方便；存取速度快；不需要索引區(qū)，節(jié)省存儲(chǔ)空間。缺點(diǎn)是：不能進(jìn)行順序存取，只能按關(guān)鍵字隨機(jī)存取，且詢問(wèn)方式限地簡(jiǎn)單詢問(wèn)，需要重新組織文件?！　〉古疟恚捍侮P(guān)鍵字索引表稱倒排表，主文件和倒排表構(gòu)成倒排文件