數(shù)據(jù)結(jié)構(gòu)課件10

第十章內(nèi)部排序10.1概述10.2插入排序10.3交換排序10.4選擇排序10.5歸并排序10.6基數(shù)排序10.7各種內(nèi)部排序方法比較10.8例題解析1數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序10.1概述10.1.1什么是排序是依據(jù)記錄關(guān)鍵字的值的遞增(遞減)的關(guān)系將多個記錄的次序重新排列。定義：設(shè)有含n個記錄的文件{R1,R2,...,Rn}，對應(yīng)的關(guān)鍵字序列為{K1,K2,...,Kn}，求一個置換p1,p2,...,pn使文件按關(guān)鍵字有序{Rp1,Rp2,...,Rpn}，滿足Kp1Kp2...Kpn或Kp1Kp2...Kpn2數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序10.1.2排序的分類依據(jù)排序時文件記錄的存放位置：內(nèi)部排序：排序過程中將全部記錄放在內(nèi)存中處理。外部排序：排序過程中需在內(nèi)外存之間交換信息。依據(jù)排序前后相同關(guān)鍵字記錄的相對次序：穩(wěn)定排序：設(shè)文件中隨意兩個記錄的關(guān)鍵字值相同，即Ki=Kj(ij)，若排序之前記錄Ri領(lǐng)先于記錄Rj，排序后這種關(guān)系不變(對全部輸入實例而言)。不穩(wěn)定排序：只要有一個實例使排序算法不滿足穩(wěn)定性要求。3數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序依據(jù)文件的存儲結(jié)構(gòu)劃分排序的種類連續(xù)依次文件排序鏈表排序地址排序:待排記錄依次存儲，排序時只對幫助表(關(guān)鍵字+指針)的表目進行物理重排。依據(jù)排序中運用的主要方法插入排序交換排序選擇排序歸并排序基數(shù)排序依據(jù)排序算法所需的幫助空間就地排序：O(1)非就地排序：O(n)或與n有關(guān)4數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序10.1.3評價排序算法的主要標(biāo)準(zhǔn)

[時間開銷]考察算法的兩個基本操作的次數(shù)：比較關(guān)鍵字移動記錄算法時間還與輸入實例的初試狀態(tài)有關(guān)時，分狀況：最好最壞平均[空間開銷]所需的幫助空間探討約定：(1)連續(xù)依次文件(2)關(guān)鍵字非遞減TYPElist=ARRAY[0..maxn]OFRECORDkey:keytype;......END;varr:list5數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序10.2插入排序10.2.1干脆插入排序（增量法）[示例]{R(0)R(-4)R(8)R(1)R(-4)R(-6)}n=6i=1[0]-481-4-6i=2[-40]81-4-6i=3[-408]1-4-6i=4[-4018]-4-6i=5[-4-4018]-6i=6[-6-4-4018][算法思想]每次使有序區(qū)增加一個記錄穩(wěn)定排序6數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序[算法步驟]

01i-1ii+1nr[0..n]r[i](有序區(qū))(無序區(qū))循環(huán)(n-1)次，初值i=21)把第i個記錄用出保存在r[0]中，j=i-12)若r[0]<r[j]，則r[j]后移一位，j=j-1，轉(zhuǎn)2)；否則r[0]放在r[j+1]處，i=i+1，轉(zhuǎn)1)7數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序[哨兵/監(jiān)視哨的作用]簡化邊界條件的測試，提高算法時間效率。[性能分析]最好狀況(原始數(shù)據(jù)按正序即非遞減序排列)Cmin=n-1Mmin=2(n-1)最壞狀況(原始數(shù)據(jù)按逆序即非遞增序排列)Cmax=(n+2)(n-1)/2Mmax=(n+4)(n-1)/2隨機狀況Cavg=(Cmin+Cmax)/2n2/4Mavgn2/4時間困難度O(n2)幫助空間困難度O(1)8數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序[改進措施]折半插入排序O(n2)算法思想：將循環(huán)中每一次在區(qū)間[1,i-1]上為確定插入位置的依次查找操作改為折半查找操作。效果：削減關(guān)鍵字間的比較次數(shù)。2-路插入排序O(n2)算法思想：設(shè)置與r同樣大小的幫助空間d，將r[1]賦值給d[1]，將d看作循環(huán)向量。對于r[i](2in)，若r[i]d[1]，則插入d[1]之后的有序序列中，反之則插入d[1]之前的有序序列中。(避開r[1]關(guān)鍵字最小/最大)效果：削減記錄的移動次數(shù)。表插入排序O(n2)算法思想：接受靜態(tài)鏈表作為存儲結(jié)構(gòu)。若要利用折半查找，需將記錄按序重排。9數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序[算法要點]是穩(wěn)定排序更適合于原始記錄基本呈正序的狀況算法思想也適用于鏈?zhǔn)酱鎯Y(jié)構(gòu)10數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序10.2.2希爾排序(漸減/縮小增量排序)[算法思想的動身點]干脆插入排序在待排序列的關(guān)鍵字基本有序時，效率較高在待排序的記錄個數(shù)較少時，效率較高[算法思想]先選定一個記錄下標(biāo)的增量d，將整個記錄序列按增量d從第一個記錄起先劃分為若干組，對每組運用干脆插入排序的方法；然后減小增量d，不斷重復(fù)上述過程，如此下去，直到d=1(此時整個序列是一組)。11數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序[示例]<初態(tài)>4682524067314073d1=44667318240524073<第一趟結(jié)果>4631404067825273d2=24046526731407382<其次趟結(jié)果>4031464052736782d3=13140404652677382<第三趟結(jié)果>3140404652677382不穩(wěn)定排序4組2組1組12數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序[性能分析]時間困難度是n和d的函數(shù)試驗結(jié)果：當(dāng)n較大時，比較和移動次數(shù)約在n1.25到1.6n1.25。就地排序[算法要點]是不穩(wěn)定排序算法的時間性能優(yōu)于干脆插入排序如何選擇最佳d序列，目前尚未解決最終一個增量值必需為1避開增量序列中的值（尤其是相鄰的值）有公因子不宜在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實現(xiàn)13數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序10.3交換排序10.3.1起泡排序(冒泡排序)[算法思想]

將兩個相鄰記錄的關(guān)鍵字進行比較，若為逆序則交換兩者位置，小者往上浮，大者往下沉。[算法步驟]記錄1和2、2和3、……、(n-1)和n的關(guān)鍵字比較(交換)；記錄1和2、2和3、……、(n-2)和(n-1)的關(guān)鍵字比較(交換)；……直到某一趟不出現(xiàn)交換操作為止。14數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序[示例]<初態(tài)><第一趟><其次趟><第三趟><第四趟>0-4-4-6-6-40-6-4-48-6-4-4-4-6-4000-4111118888sortedFFFT穩(wěn)定排序15數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序[性能分析]最好狀況(原始數(shù)據(jù)按正序即非遞減序排列)Cmin=n-1Mmin=0最壞狀況(原始數(shù)據(jù)按逆序即非遞增序排列)Cmax=n(n-1)/2Mmax=3n(n-1)/2時間困難度O(n2)幫助空間困難度O(1)[算法的改進]每趟排序中，記錄最終一次發(fā)生交換的位置雙向交替掃描，下上，最輕升頂；上下，最重沉底[算法要點]是穩(wěn)定排序移動記錄次數(shù)較多，平均時間性能比干脆插入排序差也可用于鏈?zhǔn)酱鎯Y(jié)構(gòu)16數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序10.3.2快速排序(分劃交換排序/分治法)[分治算法原理]1)分解：將原問題分解為若干子問題2)求解：遞歸地解各子問題，若子問題的規(guī)模足夠小，則干脆求解3)組合：將各子問題的解組合成原問題的解[快速排序算法思想]指定樞軸/支點/基準(zhǔn)記錄r[p](通常為第一個記錄)，通過一趟排序?qū)⑵浞旁谡_的位置上，它把待排記錄分割為獨立的兩部分，使得左邊記錄的關(guān)鍵字r[p].key右邊記錄的關(guān)鍵字對左右兩部分記錄序列重復(fù)上述過程，依次類推，直到子序列中只剩下一個記錄或不含記錄為止。(可以用遞歸方法實現(xiàn))17數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序[示例]<初態(tài)>{(49)38659776132749}x=49ij273865977613()49ij2738()9776136549ij2738139776()6549ij273813()76976549ij<一趟結(jié)束>{273813}49{76976549}(i=j)18數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序[性能分析]最壞狀況(原始數(shù)據(jù)正/逆序排列)Cmax=n(n-1)/2MmaxCmaxO(n2)最好狀況：每次劃分的結(jié)果是基準(zhǔn)的左、右兩個無序子區(qū)間的長度大致相等CminO(nlog2n)MminCminO(nlog2n)平均時間性能Tavg(n)=knln(n)k：某個常數(shù)；n：待排序序列中記錄個數(shù)幫助空間困難度取決于遞歸深度最好狀況O(log2n)最壞狀況O(n)19數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序[算法要點]非穩(wěn)定排序反例[2，2，1]：{12}2

{}就平均時間而言，快速排序是目前被認(rèn)為最好的一種內(nèi)部排序方法。樞軸記錄的合理選擇可改善性能。例如，三者取中隨機產(chǎn)生難于在單向鏈表結(jié)構(gòu)上實現(xiàn)20數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序10.4選擇排序10.4.1簡潔選擇排序(干脆選擇排序)[算法步驟]第1趟：從n個記錄中選關(guān)鍵字最小的記錄，與第1個記錄交換；第2趟：從剩余的n-1個記錄中選關(guān)鍵字最小的記錄，與第2個記錄交換；……第i趟：從剩余的n-i+1個記錄中選關(guān)鍵字最小的記錄，與第i個記錄交換；……直到第n-1趟執(zhí)行完為止。21數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序[示例]（n=8）<初態(tài)>4938659776491327<第1趟>13

38659776494927<第2趟>1327659776494938<第3趟>1327389776494965<第4趟>1327384976974965<第5趟>1327384949977665<第6趟>1327384949657697<第7趟>1327384949657697（每趟排序使有序區(qū)增加一個記錄）不穩(wěn)定排序22數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序[性能分析]總的比較次數(shù)與記錄排列的初始狀態(tài)無關(guān)C=(n-1)+(n-2)+...+2+1=n(n-1)/2移動次數(shù)初始記錄逆序時：Mmax=3(n-1)初始記錄正序時：Mmin=0平均時間困難度O(n2)幫助空間困難度O(1)[算法要點]是不穩(wěn)定排序當(dāng)一個記錄占用的空間較多時，此方法比干脆插入排序快可用于鏈?zhǔn)酱鎯Y(jié)構(gòu)23數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序10.4.2樹形選擇排序(錦標(biāo)賽排序)[算法思想]錦標(biāo)賽名次產(chǎn)生過程。較簡潔選擇排序削減“比較”次數(shù)。[示例]2323403823404638233840[時間困難度]每次都走樹的一條分支，O(nlog2n)。[缺陷]幫助空間較多；需與“最大值”進行多余的比較233838383846383838

464040

4646

穩(wěn)定排序24數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序10.4.3堆排序[特點]較干脆選擇排序削減重復(fù)比較；較樹形選擇排序削減幫助存儲空間(僅需一個)[堆的概念](二叉)堆的定義：n個關(guān)鍵字的序列（k1,k2,...,kn）當(dāng)且僅當(dāng)滿足下列條件之一：(1)KiK2i且KiK2i+1小根堆(2)KiK2i且KiK2i+1大根堆則稱該序列為一個堆。[堆的存儲結(jié)構(gòu)]對應(yīng)于完全二叉樹的依次存儲

(i=1,2,...,n/2)96832738119堆頂大根堆示例9683273811925數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序[堆排序基本思想]將初始文件R[1..n]建成一個大根堆；第1趟：將關(guān)鍵字最大的記錄(堆頂)R[1]與無序區(qū)的最終一個記錄R[n]交換；再將新的無序區(qū)R[1..n-1]調(diào)整為堆；第2趟：將R[1]與R[n-1]交換；再將新的無序區(qū)R[1..n-2]調(diào)整為堆；......第i趟：將R[1]與R[n-i+1]交換；再將新的無序區(qū)R[1..n-i]調(diào)整為堆；......直到執(zhí)行完第(n-1)趟為止?！璕[1]26數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序[算法步驟]將剩余元素調(diào)整為一個新堆

1)將堆頂元素作為當(dāng)前結(jié)點位置；2)若當(dāng)前結(jié)點無左子結(jié)點，結(jié)束調(diào)整；否則，比較當(dāng)前結(jié)點與其左右孩子的關(guān)鍵字值3)若前者后者，則結(jié)束調(diào)整；否則，前者與后者中關(guān)鍵字值較大的結(jié)點交換位置，前者交換后的位置作為當(dāng)前結(jié)點位置，轉(zhuǎn)2)

678080807567757675篩選法497665494976654949676549堆堆27數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序?qū)⒊跏加涗浶蛄蠷[1..n]建成大根堆方法：依次把以i=n/2，n/2-1，n/2-2，......，1為根的子樹調(diào)整為堆，則完成了整個建堆的過程。[算法分析]最壞狀況O(nlog2n)建初始堆時，比較次數(shù)4n反復(fù)調(diào)整堆時，比較次數(shù)<2nlog2n試驗表明：平均性能接近于最壞性能O(nlog2n)幫助空間困難度：O(1)[算法要點]不穩(wěn)定排序初始建堆所需比較次數(shù)較多，因此記錄數(shù)較少時不宜接受在最壞狀況下時間性能優(yōu)于快速排序28數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序10.5歸并排序(合并排序)[歸并的概念]指將兩個或兩個以上的同序序列歸并成一個序列的操作。10.5.1兩路歸并排序[算法思想]第1趟：將待排序列R[1..n]看作n個長度為1的有序子序列，兩兩歸并，得到n/2個長度為2的有序子序列(或最終一個子序列長度為1)；第2趟：將上述n/2個有序子序列兩兩歸并；......直到合并成一個序列為止。29數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序[示例]

(n=7)<初態(tài)>(49)(38)(65)(97)(76)(49)(13)<第1趟>(3849)(6597)(4976)(13)<第2趟>(38496597)(134976)<第3趟>(13384949657697)[性能分析]任何狀況時間困難度O(nlog2n)幫助空間困難度O(n)[算法要點]是穩(wěn)定排序若接受單鏈表作為存儲結(jié)構(gòu)，可實現(xiàn)就地排序很少用于內(nèi)部排序穩(wěn)定排序30數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序10.5.2自然兩路歸并排序[特點]以游程(自然的有序段)作為子序列進行歸并，可以比干脆兩路歸并更有效。[示例]5038751261908170897275653426154512503512612758979081706535124261548787154426503512512653908897275170616187154170275426503512512653897908不穩(wěn)定排序31數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序10.6基數(shù)排序(支配排序)[特點]通過“支配”和“收集”過程來實現(xiàn)排序，時間困難度可以突破基于關(guān)鍵字比較一類方法的下界O(nlgn)，達到O(n)。[方法]借助多關(guān)鍵字排序的思想對單關(guān)鍵字排序[多關(guān)鍵字排序示例]撲克牌排序(點數(shù)+花色)花色：<<<點數(shù)：2<3<…<Q<K<A最高位優(yōu)先法：按花色分成4堆；（MSD法）對每一堆：按面值分堆；從小到大排序；按花色從小到大排序32數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序最低位優(yōu)先法：按點數(shù)大小分成13堆；（LSD法）按點數(shù)從小到大收集起來；再按花色分成四堆；按花色從小到大收集起來[基數(shù)排序算法思想]借鑒LSD法設(shè)參與排序的序列為K={K1,K2,...,Kn}，其中Ki是d位rd進制的數(shù)，rd稱為基數(shù)；d由全部元素中最長的一個元素的位數(shù)計量，Ki=Ki1Ki2...Kid從低位到高位依次對Kj(j=d,d-1,...,1)依據(jù)基數(shù)支配，再按基數(shù)遞增序收集，則可得有序序列。33數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序[例]

(1)K={362107248385007505147368

0008}rd=10,d=4(2)K={ZhangWangLiZhao}rd=27,d=534數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序[基數(shù)排序示例]

{4772414675363815}第1趟：支配[0][1][2][3][4][5][6][7][8][9]2413635477815467收集{2418136355477467}第2趟：支配[0][1][2][3][4][5][6][7][8][9]5241363477815467收集{5524136346747781}第3趟：支配[0][1][2][3][4][5][6][7][8][9]5241363467547781收集{5581241363467477}rd=10d=3穩(wěn)定排序35數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序[鏈?zhǔn)交鶖?shù)排序的性能分析]每一趟：支配O(n)收集O(rd)d趟總計：O(d(n+rd))O(n)通常d,rd均為常數(shù)幫助空間n個指針域空間隊頭指針數(shù)組f[1..rd]和隊尾指針數(shù)組e[1..rd]幫助空間困難度：O(rd+n)36數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序10.7各種內(nèi)部排序方法的比較排序方法最好時間平均時間最壞時間幫助空間穩(wěn)定性干脆插入O(n)O(n2)O(n2)O(1)希爾O(n1.3)O(1)冒泡O(n)O(n2)O(n2)O(1)快速O(nlog2n)O(nlog2n)O(n2)O(log2n)簡潔選擇O(n2)O(n2)O(n2)O(1)堆O(nlog2n)O(nlog2n)O(nlog2n)O(1)歸并O(nlog2n)O(nlog2n)O(nlog2n)O(n)基數(shù)O(d(rd+n))O(d(rd+n))O(d(rd+n))O(rd+n)37數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序按平均時間排序方法分為四類O(n2)、O(nlgn)、O(n1+)、O(n)快速排序是目前基于比較的內(nèi)部排序中最好的方法關(guān)鍵字隨機分布時，快速排序的平均時間最短，堆排序次之，但后者所需的幫助空間少當(dāng)n較小時如(n<50)，可接受干脆插入或簡潔選擇排序，前者是穩(wěn)定排序，但后者通常記錄移動次數(shù)少于前者當(dāng)n較大時，應(yīng)接受時間困難度為O(nlgn)的排序方法(主要為快速排序和堆排序)或者基數(shù)排序的方法，但后者對關(guān)鍵字的結(jié)構(gòu)有確定要求當(dāng)n較大時，為避開依次存儲時大量移動記錄的時間開銷，可考慮用鏈表作為存儲結(jié)構(gòu)（如插入排序、歸并排序、基數(shù)排序）38數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序快速排序和堆排序難于在鏈表上實現(xiàn)，可以接受地址排序的方法，之后再按幫助表的次序重排各記錄文件初態(tài)基本按正序排列時，應(yīng)選用干脆插入、冒泡或隨機的快速排序選擇排序方法應(yīng)綜合考慮各種因素39數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序10.8例題解析選擇題1.(北郵2001)若要求盡可能快地對序列進行穩(wěn)定的排序，則應(yīng)選（快速排序/歸并排序/冒泡排序）2.排序是依據(jù)（）的大小重新支配各元素的依次。A.數(shù)組B.關(guān)鍵字C.元素D.結(jié)點3.排序是依據(jù)關(guān)鍵字的大小重新支配各（）的依次。A.文件B.關(guān)鍵字C.數(shù)據(jù)元素D.數(shù)據(jù)項4.不穩(wěn)定排序是指在排序中，關(guān)鍵字相等的不同記錄間的前后相對位置（）。A.保持不變B.確定相反C.不定5.用冒泡排序的方法對n個數(shù)據(jù)進行排序，第一趟共比較（）元素。A.1B.2C.n-1D.n40數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序6.假如只想得到1000個元素組成的序列中第5個最小元素之前的部分排序的序列，用（）方法最快。A.冒泡排序4趟B.快速排序每次僅對第一個子序列劃分，直至子序列長度小于等于4；長度不足4，則再對其后的子序列劃分出補足的長度即可。（平均對數(shù)據(jù)操作2n次）C.希爾排序全部排序D.堆排序先建小根堆，3次堆調(diào)整，O(n+klog2n)7.已知待排序的n個元素分為n/k個組，每個組包含k個元素，且組間元素有序，若接受基于比較的排序，其時間的下界為（）。A.O(klog2k)B.O(klog2n)C.O(nlog2k)D.O(nlog2n)n/k*klog2k41數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序8.堆排序方法要求被排序的數(shù)據(jù)（）存儲。A.必需是依次B.必需是鏈表C.依次或鏈表D.二叉樹9.在全部的排序方法中，關(guān)鍵字比較次數(shù)與記錄的初始排列次序無關(guān)的是（）。A.希爾排序B.冒泡排序C.選擇排序D.插入排序10.在待排序列基本有序時，效率最高的排序方法是（）。A.快速排序B.選擇排序C.插入排序D.歸并排序11.用某種排序方法對序列(25,84,21,47,15,27,68,35,20)進行排序時，元素序列變更狀況如下,則所接受的排序方法是（）。(1)25,84,21,47,15,27,68,35,20(2)20,15,21,25,47,27,68,35,84(3)15,20,21,25,35,27,47,68,84(4)15,20,21,25,27,35,47,68,84A.選擇排序B.希爾排序C.歸并排序D.快速排序42數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序填空題1.(北郵2001)若不考慮基數(shù)排序，則在排序過程中，主要進行的兩種基本操作是關(guān)鍵字的（比較）和記錄的（移動）。2.歸并排序要求參與歸并的各組數(shù)據(jù)各自（有序）。3.當(dāng)數(shù)據(jù)已經(jīng)有序時，不再進行排序的方法是（冒泡排序）。4.在對一組記錄(54,38,96,23,15,72,60,45,83)進行干脆插入排序時，當(dāng)把第7個記錄60插入到有序表時，為找尋插入位置需比較（3）次。5.對n個元素的序列冒泡排序時，最少的比較次數(shù)是（n-1）次。6.快速排序的最大遞歸深度是（n），最小遞歸深度是（log2n+1）。43數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序7.在利用快速排序方法對一組記錄(54,38,96,23,15,72,60,45,83)排序時，遞歸調(diào)用中運用的棧能達到的最大深度為（3），共需遞歸調(diào)用（4）次，其中其次次遞歸調(diào)用是對（{23，38，15}）一組記錄快速排序。[分析]{543896231572604583}{45381523}54{72609683}{233815}45{}{60}72{9683}{15}23{38}{83}96{}44數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序推斷題1.(北郵2002)歸并排序在任何狀況下都比全部簡潔排序速度快。2.快速排序的速度在全部排序中最快，而且所需附加空間也最少。3.在文件“局部有序”或文件長度較小的狀況下，最佳的內(nèi)部排序方法是干脆插入排序。4.序列{100,90,80,60,85,75,20,25,10,70,65,50}是堆。45數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序求解題1.(北郵2001)簡答在多關(guān)鍵字排序時，LSD和MSD兩種方法的特點是什么？[解答]LSD即低關(guān)鍵字優(yōu)先算法，是從最低位的關(guān)鍵字起先，每次都按相應(yīng)的關(guān)鍵字位上的大小不同將全部記錄進行支配和收集，直至最高位的關(guān)鍵字為止；MSD即高關(guān)鍵字優(yōu)先算法，需將待排序列按高關(guān)鍵字大小不同進行支配形成若干較小的子序列，再在各子序列中按次高關(guān)鍵字大小不同進行支配形成一些更小的子序列，……，直至按最低位的關(guān)鍵字支配，最終一次性地將全部記錄收集起來。46數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序2.以關(guān)鍵碼序列(503,087,512,061,908,170,897,275,653,426)為例，手工執(zhí)行以下排序算法，寫出每一趟排序結(jié)束時的關(guān)鍵碼狀態(tài)：(1)干脆插入排序(2)希爾排序(d[1]=5,d[2]=3,d[3]=1)(3)快速排序(4)堆排序(5)歸并排序(6)基數(shù)排序47數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序(1)干脆插入排序503087512061908170897275653426i=2(087503)512061908170897275653426i=3(087503512)061908170897275653426i=4(061087503512)908170897275653426i=5(061087503512908)170897275653426i=6(061087170503512908)897275653426i=7(061087170503512897908)275653426i=8(061087170275503512897908)653426i=9(061087170275503512653897908)426i=10(061087170275426503512653897908)48數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序(2)希爾排序503087512061908170897275653426d=5170087275061426503897512653908d=3061087275170426503897512653908d=106108717027542650351265389790849數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序(3)快速排序503087512061908170897275653426

426087275061170503897908653512170087275061426512653897908061087170275512653

06108706108717027542650351265389790850數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序(4)堆排序503087512061908170897275653426

503908087512653897061908170897503426170512275653426275061087897653653512503512503426170087275426170087275061908061897908初態(tài)：建大根堆輸出908篩選087后輸出897篩選061后……51數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序(5)歸并排序[503][087][512][061][908][170][897][275][653][426]

[087503][061512][170908][275897][426653][061087503512][170275897908][426653][061087170275503512897908][426653]

[061087170275426503512653897908]52數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序(6)基數(shù)排序503087512061908170897275653426第一趟：[0][1][2][3][4][5][6][7][8][9]170061512503275426087908653897170061512503653275426087897908其次趟：[0][1][2][3][4][5][6][7][8][9]50351242665306117008789790827550390851242665306117027508789753數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序第三趟：[0][1][2][3][4][5][6][7][8][9]06117027542650365389790808751206108717027542650351265389790854數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序3.試為下列排序選擇合適的算法，并簡述理由。(1)記錄數(shù)n=50，每個記錄的信息量很大，關(guān)鍵字分布隨機；(2)記錄數(shù)n=50，關(guān)鍵字基本正序，要求穩(wěn)定排序；(3)記錄數(shù)n=5000，要求平均狀況速度最快；(4)記錄數(shù)n=5000，要求最壞狀況最快且穩(wěn)定；(5)記錄數(shù)n=5000，存儲結(jié)構(gòu)是單鏈表，關(guān)鍵字為整型，最長四位。[提示](1)簡潔選擇排序(2)干脆插入或冒泡排序(3)快速排序(4)二路歸并排序(5)基數(shù)排序55數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序4.(1)若在記錄數(shù)很大且記錄本身信息量很大時接受快速排序，有何提高排序效率的措施？(2)假設(shè)有500個關(guān)鍵字均為小于1000的正整數(shù)的記錄序列，試設(shè)計一種排序方法以盡可能少的比較次數(shù)和移動次數(shù)實現(xiàn)排序。[提示](1)地址排序(2)利用哈希表方法56數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序5.對于序列{57,40,38,11,13,34,48,75,25,6,19,9,7}，若要取出{6,7,9,11}4個最小元素，利用快速排序，其執(zhí)行的比較次數(shù)是多少？利用堆排序的方法，其執(zhí)行的比較次數(shù)又是多少？[提示]用快速排序需比較36次；堆排序比較次數(shù)：建堆20次得到6調(diào)整5次得到7調(diào)整4次得到9調(diào)整5次得到11共計34次比較。57數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序6.對50個整數(shù)進行快速排序，關(guān)鍵字間比較次數(shù)最多是多少？最少是多少？給出推導(dǎo)過程。[提示]最壞在關(guān)鍵字有序的狀況下：49+48+……+1=1225（次）最小比較次數(shù)：2222222311111111155651112245025……判定樹49次47次0次43次19次35次49+47+43+35+19=19358數(shù)據(jù)結(jié)構(gòu)---第十章內(nèi)部排序7.設(shè)有n個值不同的元素存于依次結(jié)構(gòu)中，問能否用比2n-3次少的比較次數(shù)找出該序列的最大值和最小值？若能，應(yīng)如何實現(xiàn)，最壞狀況如何？[解]