【正文】 5,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í)的排序過程。排序好的序列為：61，87，170，275，462，503，512，653，897，908 交換排序交換排序的基本思想是：利用交換數(shù)據(jù)元素的位置進(jìn)行排序的方法。交換排序的主要算法有： 1) 冒泡排序 2) 快速排序 冒泡排序基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。優(yōu)點(diǎn)：每趟結(jié)束時(shí)，不僅能擠出一個(gè)最大值到最后面位置，還能同時(shí)部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結(jié)束排序。例：關(guān)鍵字序列 T=(21，25，49，25*，16，08），請按從小到大的順序，寫出冒泡排序的具體實(shí)現(xiàn)過程。初態(tài)：21，25，49， 25*，16， 08第1趟21，25，25*，16， 08 ， 49第2趟21，25， 16， 08 ，25*，49第3趟21，16， 08 ，25， 25*，49第4趟16，08 ，21， 25， 25*，49第5趟08，16， 21， 25， 25*，49冒泡排序算法public static void bubbleSort(int[] a){ int i, j, flag=1。 int temp。 int n = 。 for(i = 1。 i n amp。amp。 flag == 1。 i++){ flag = 0。 for(j = 0。 j ni。 j++){ if(a[j] a[j+1]){ flag = 1。 temp = a[j]。 a[j] = a[j+1]。 a[j+1] = temp。 } } }}冒泡排序的算法分析時(shí)間效率：O（n2) —因?yàn)橐紤]最壞情況（數(shù)據(jù)元素全部逆序），當(dāng)然最好情況是數(shù)據(jù)元素已全部排好序，此時(shí)循環(huán)n1次，時(shí)間復(fù)雜度為O（n) 空間效率：O（1） —只在交換時(shí)用到一個(gè)緩沖單元 穩(wěn) 定 性： 穩(wěn)定 —25和25*在排序前后的次序未改變練習(xí)：關(guān)鍵字序列 T=(31，15，9，25，16，28），請按從小到大的順序，寫出冒泡排序的具體實(shí)現(xiàn)過程。初態(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)元素。這樣一次排序過程結(jié)束后，一方面將標(biāo)準(zhǔn)元素放在了未來排好序的數(shù)組中該標(biāo)準(zhǔn)元素應(yīng)位于的位置上，另一方面將數(shù)組中的元素以標(biāo)準(zhǔn)元素為中心分成了兩個(gè)子數(shù)組，位于標(biāo)準(zhǔn)元素左邊子數(shù)組中的元素均小于標(biāo)準(zhǔn)元素，位于標(biāo)準(zhǔn)元素右邊子數(shù)組中的元素均大于等于或標(biāo)準(zhǔn)元素。對這兩個(gè)子數(shù)組中的元素分別再進(jìn)行方法類同的遞歸快速排序。算法的遞歸出口條件是low≥high。 例、關(guān)鍵字序列 T=(60，55，48，37，10，90，84，36），請按從小到大的順序，寫出快速排序的具體實(shí)現(xiàn)過程。 快速排序算法各次快速排序過程 快速排序算法public static void quickSort(int[] a, int low, int high){ int i, j。 int temp。 i = low。 j = high。 temp = a[low]。 //取第一個(gè)元素為標(biāo)準(zhǔn)數(shù)據(jù)元素 while(i j){ //在數(shù)組的右端掃描 while(i j amp。amp。 temp = a[j]) j。 if(i j){ a[i] = a[j]。 i++。 } //在數(shù)組的左端掃描 while(i j amp。amp。 a[i] temp) i++。 if(i j){ a[j] = a[i]。 j。 } } a[i] = temp。 if(low i) quickSort(a, low, i1)。 //對左端子集合遞歸 if(i high) quickSort(a, j+1, high)。 //對右端子集合遞歸}快速排序算法分析：時(shí)間效率：一般情況下時(shí)間復(fù)雜度為O(nlog2n)，最壞情況是數(shù)據(jù)元素已全部正序或反序有序，此時(shí)每次標(biāo)準(zhǔn)元素都把當(dāng)前數(shù)組分成一個(gè)大小比當(dāng)前數(shù)組小1的子數(shù)組，此時(shí)時(shí)間復(fù)雜度為O(n2) 空間效率：O（log2n）—因?yàn)檫f歸要用棧 穩(wěn) 定 性： 不 穩(wěn) 定 —因?yàn)橛刑S式交換。練習(xí)：已知序列{503,87,512,61,908,170,897,275,653,462}，給出采用快速排序?qū)υ撔蛄凶鞣沁f減排序時(shí)每趟的結(jié)果。第一趟：【462 87 275 61 170】 503 【 897 908 653 512】第二趟：【170 87 275 61 】 462 503 【512 653】 897 【908】第三趟：【61 87】 170 【275】 462 503 512 【653】 897 908第四趟：61 【 87】 170 275 462 503 512 653 897 908最后排序結(jié)果：61 87 170 275 462 503 512 653 897 908，選擇排序是不穩(wěn)定的。，所需時(shí)間確定于初始記錄的排列情況，在初始記錄無序的情況下最好。（ A ） (n) (nlog2n) C. O(log2n) (n2) {8,9,10,4,5,6,20,1,2}只能是（ C ）算法的兩趟排序后的結(jié)果。 ，元素比較次數(shù)最少的是（C ） ,32,40,90,80,46,21,69 ,40,21,46,69,94,90,80 ,32,46,40,80,69,90,94 ,69,80,46,21,32,94,40 7. .以下排序算法中，（B ）不能保證每趟排序至少能將一個(gè)元素放到其最終位置上。 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 ）。 10. 一組記錄的關(guān)鍵字為{45，80，55，40，42，85}，則利用堆排序的方法建立的初始堆為（ 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ù)據(jù)項(xiàng)是文件可使用的最小單位，數(shù)據(jù)項(xiàng)有時(shí)稱字段或者屬性。　　文件　邏輯結(jié)構(gòu)是一種線性結(jié)構(gòu)。　　操作有：檢索和維護(hù)。并有實(shí)時(shí)和批量處理兩種處理方式。　　文件　存儲結(jié)構(gòu)是指文件在外存上的組織方式?！　』镜慕M織方式有：順序組織、索引組織、散列組織和鏈組織?！　〕Ｓ玫奈募M織方式：順序文件、索引文件、散列文件和多關(guān)鍵字文件?！　≡u價(jià)一個(gè)文件組織的效率，是執(zhí)行文件操作所花費(fèi)的時(shí)間和文件組織所需的存儲空間。　　檢索功能的多寡和速度的快慢，是衡量文件操作質(zhì)量的重要標(biāo)志。　　順序文件是指按記錄進(jìn)入文件的先后順序存放、其邏輯順序和物理順序一致的文件。主關(guān)鍵字有序稱順序有序文件，否則稱順序無序文件?！　∫磺写鎯υ陧樞虼鎯ζ鳎ㄈ绱艓В┥系奈募贾荒茼樞蛭募荒馨错樞虿檎曳ù嫒?。　　順序文件的插入、刪除和修改只能通過復(fù)制整個(gè)文件實(shí)現(xiàn)?！　∷饕募慕M織方式：通常是在主文件之外建立一張索引表指明邏輯記錄和物理記錄之間一一對應(yīng)的關(guān)系，它和主文件一起構(gòu)成索引文件?！　∷饕琼樞蛭募械乃饕頌槌砻芩饕Ｋ饕樞蛭募械乃饕頌橄∈杷饕?。　　若記錄很大使得索引表也很大時(shí)，可對索引表再建立索引，稱為查找表。是一種靜態(tài)索引?！　∷饕樞蛭募Ｓ玫挠袃煞N：　　ISAM索引順序存取方法：是專為磁盤存取文件設(shè)計(jì)的，采用靜態(tài)索引結(jié)構(gòu)。 　　VSAM虛擬存儲存取方法：采用B+樹作為動(dòng)態(tài)索引結(jié)構(gòu)，由索引集、順序集、數(shù)據(jù)集組成?！　∩⒘形募抢蒙⒘写鎯Ψ绞浇M織的文件，亦稱為直接存取文件。　　散列文件　　優(yōu)點(diǎn)是：文件隨機(jī)存放，記錄不需要排序；插入刪除方便；存取速度快；不需要索引區(qū)，節(jié)省存儲空間?！∪秉c(diǎn)是：不能進(jìn)行順序存取，只能按關(guān)鍵字隨機(jī)存取，且詢問方式限地簡單詢問，需要重新組織文件?！　《嘀乇砦募簩π枰樵兊拇侮P(guān)鍵字建立相應(yīng)的索引，對相同次關(guān)鍵字的記錄建一個(gè)鏈表并將鏈表頭指針、長度、次關(guān)鍵字作為索引表的索引項(xiàng)?！　〉古疟恚捍侮P(guān)鍵字索引表稱倒排表，主文件和倒排表構(gòu)成倒排文件。