數(shù)據(jù)結(jié)構(gòu)電子科技-第七章排序

第七章排排序：待排序記錄存放在內(nèi)外部排序：排序過程中需對外存進(jìn) 的排排序：直 排序、折 排序 排交換排序：冒泡排序、快速選擇排序：簡單選擇排序、堆排歸并排序：2-路歸并排基數(shù)排簡單的排序方法先進(jìn)的排序方法基數(shù)排序排序：將一組數(shù)據(jù)元素序列重新排列使得數(shù)據(jù)元素序列按某個(gè)數(shù)據(jù)項(xiàng)（關(guān)鍵字排序依據(jù)：是依據(jù)數(shù)據(jù)元素的關(guān)鍵字（關(guān)鍵字值不重復(fù)這無論采用何種排序方法，排出的結(jié)果都是唯一的；假設(shè)含n個(gè)記錄的序列為R1,R2Rn其相應(yīng)的關(guān)鍵字序列為K1K2，Kn即在它們之間存在著這樣一個(gè)關(guān)系：{Rp1,Rp2,…，Rpn 排直 排 (49) 38 65 97 76 13 i=7

排序結(jié)果 時(shí)間復(fù)若待排序記錄按關(guān)鍵字從小到大排列(正序關(guān)鍵字比較次數(shù)： 1i2

n記錄移動次數(shù)

nni2

22(n若待排序記錄按關(guān)鍵字從大到小排列(逆序nn關(guān)鍵字比較次數(shù)：ii

(n2)(n2nn記錄移動次數(shù)i

(n

2

若待排序記錄是隨機(jī)的，取平均關(guān)鍵字比較次數(shù) n4記錄移動次數(shù) n4

空間復(fù)雜度折 排排序過程：用折半查找方法確 68585mj85smj85s85js85時(shí)間復(fù)雜度空間復(fù)雜度2- 排指針：first和final(當(dāng)前最小和最大值位置） r[ｉ]．key與d[1．key若r[ｉ]．key＜d[1]．key:則將r[ｉ] 若r[ｉ]．key≥d[1]．key:則將r[ｉ] 例如first ．．．d[1] 2依據(jù)：⑴若待排序文件"基本有序"，即文件中具有特性：r[i].key＜Max{r[j].key} 和排序操作；直至di=144例初始： 44取一趟分組 一趟排序 取二趟分組 二趟排序 取三趟分組 三趟排序 T 4

一趟排序：13

二趟排 子序列的構(gòu)成不是簡單的“逐段分割”，而是將相隔某量的記錄組成一個(gè)子排序可提高排序速度分組后n值減小，n2更小，而T(n)=O(n2),所以T(n)上看是減小關(guān)鍵字較小的記錄跳躍式前移，在進(jìn)行最后一趟增量為 排序時(shí)，序列已基本有增量序列取無除1最后一個(gè)增量值必須為快速（交換）排將第一個(gè)記錄的關(guān)鍵字與第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序r[1kr[2k，則交換；然后比較第二個(gè)記錄與第三個(gè)記錄；依次類推，直至第-個(gè)記錄和第個(gè)記錄比較為止——第一趟冒泡排序，結(jié)果關(guān)鍵字最大的記錄被安置在最后一個(gè)記錄上對前n-1個(gè)記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字次大的錄被安置在第n-1個(gè)記錄重復(fù)上述過程，直到“在一趟排序過程中沒有進(jìn)行過交錄的操作”為例

76

第第第第四五六七趟趟趟趟冒泡排序的改冒泡排序的結(jié)束條件最后一趟沒有進(jìn)行“交換記錄”12 12 3

forfor(j=1;j<i;j++)if(R[j+1].key<R[j].key)void emR[],intn)i=while(i>1)lastExchangeIndexlastExchangeIndex=if(R[j].key>{Swap(R[j],lastExchangeIndexj;/*記下進(jìn)行交換的記錄位置}for(j=1;j<i;ilastExchangeIndex;/*本趟最后一次交換的位置}}時(shí)間復(fù)最好情況（正序比較次數(shù)：n-移動次數(shù)情況（逆序比較次

(ni)

1(n2

n移動次n

(ni)

3(n2

空間復(fù)雜度初始時(shí)令首先從j所指位置向前搜索第一個(gè)關(guān)鍵字小于x的記錄，并rp交再從i所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于x的記錄和rp交重復(fù)上述兩步，直至i==j為再分別對兩個(gè)子序列進(jìn)行快速排序，直到每個(gè)子序列只一個(gè)記錄為例初始關(guān)鍵字

27

13

完成一趟排序：( 分別進(jìn)行快速排序：( 快速排序結(jié)束 時(shí)間復(fù)最好情況（每次總是選到中間值作劃分元情況（每次總是選到最小或最大元素作劃分元T(n)=O(空間復(fù)雜度：需?？臻g以實(shí)現(xiàn)遞情況一般情況

r[sk.尾記錄r[t]k和中間記錄rst)/2k三者的中間值為劃分記錄。494938快速排序結(jié)果為384949 性 選擇排首先通過-個(gè)記錄中找出關(guān)鍵字最小的記錄，將它與第一個(gè)記錄交換再通過-次比較，從剩余的-個(gè)記錄中找出關(guān)鍵字次小的記錄，將它與第二個(gè)記錄交換重復(fù)上述操作，共進(jìn)行n-1趟排序后，排序結(jié) 例

初始：[

27

一趟： [

38 二趟： 38三趟： 65四趟： 65五趟： 76六趟： [97排序結(jié)束： 時(shí)間復(fù)記錄移動次最好情況 情況：3(n-比較次(ni)

1(n2

空間復(fù)雜度 樹形選擇排序例子45,50,23,78,90,15,37,49,63,85,19,

⑴以初始關(guān)鍵字序列，建立完全二叉樹（從葉結(jié)點(diǎn)開⑶在余下元素中，形成新的根（將剛得到名次的葉結(jié)點(diǎn)的成績置為，再從此葉結(jié)點(diǎn)開始，沿著到根⑷重復(fù)⑵,⑶，直到n個(gè)元素輸出，得到一個(gè)有序序樹形選擇排序性能分選擇第二名時(shí)，將剛選出的第一名置為lo2。(n-1)log2n+n-1

9例（96，83，27，38，11，9）9可將堆序列看成完全二叉樹，則堆元素（完全二叉樹的根）必為序列n個(gè)元素的最小值或最大如何由一個(gè)無序序列建成一個(gè)堆如何在輸出堆頂 后，調(diào)整剩余元素，使之成為一個(gè)的堆方法：輸出堆頂元后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并與其中堆，稱這個(gè)從堆頂至葉子的調(diào)整過程為“篩選”

輸出：13 輸出：13輸出：13輸出：1327輸出：輸出：1327輸出：132738輸出：132738輸出：13273849輸出：13273849輸出：1327384950 輸出輸出：1327384950輸出：132738495065輸輸出：13273849506576算法描方法：從無序序列的第個(gè)元素（即此無序序列對應(yīng)的完全二叉樹的最后一個(gè)非終端結(jié)點(diǎn)）起，至第一個(gè)元素止，進(jìn)行反復(fù)篩選8個(gè)元素的無序序列算法描時(shí)間復(fù)雜度k的堆，“篩選”所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多為2(k-n個(gè)關(guān)鍵字，建成深度為h(=log2n+1)n-12(log2(n-1)+log2(n-2)+…+log22)<空間復(fù)雜度堆排序與樹形選擇排序的區(qū)結(jié)點(diǎn) 堆排序?qū)⒍秧斣睾投训漠?dāng)前最末元素交換, 10.4歸并排2-設(shè)初始序列含有n個(gè)記錄，則可看成n個(gè)有序的子序列子序列長度為兩兩合并，得到n/2個(gè)長度為2或1的有序子再兩兩合并，……如此重復(fù)，直至得到一個(gè)長度為n的有序列為 初始關(guān)鍵字： 一趟歸并后： 二趟歸并后： 三趟歸并后： 算法描時(shí)間復(fù)雜度：每一趟歸并的時(shí)間復(fù)雜度為O(n)，總共需歸并log2n趟，因而，總的時(shí)間復(fù)雜度為O(nlog2n)空間復(fù)雜度：2-路歸并排序過程中，需要一個(gè)與表等長的存 [615][2345][9 45] 9 9 10.5基數(shù)排例對52 牌按以下次序排序兩個(gè)關(guān)鍵字：花色（<<<面值并且“花色”地位高于“面值最 優(yōu)先法（M)：先對最 關(guān)鍵字k（如花色）排序，將序列分成若干子序列，每個(gè)子序列有相同的k值；然后讓每個(gè)子序列對次關(guān)鍵字k（如面值）排序，又分成若干更小的子序列；依次重復(fù)，直至就每個(gè)子序列對最低位關(guān)鍵字k排序；最后將所有子序列依次連接在一起成為一個(gè)有序列 MSD與LSD不同特按MSD排序，必須將序列逐層分割成若干子序列，然對各子序列分別排按D排序，不必分成子序列，對每個(gè)關(guān)鍵字都是整個(gè)序列參加排序；并且可不通過關(guān)鍵字比較，而通過若干次分配與收集實(shí)現(xiàn)排序進(jìn)行排序 鏈?zhǔn)交鶖?shù)排序：用鏈表 結(jié)構(gòu)的基數(shù)排設(shè)置10個(gè)隊(duì)列，f[i]和e[i]分別為第i個(gè)隊(duì)列的頭指針和尾指第一趟分配對最低位關(guān)鍵字（個(gè)位）進(jìn)行，改變記錄的指針值，將鏈表中記錄分配至鍵字的個(gè)位相同第一趟收集是改變所有非空隊(duì)列的隊(duì)尾記錄的指針域，令其指向下一個(gè)非空隊(duì)列的隊(duì)頭記錄，重新將鏈表重復(fù)上述兩步，進(jìn)行第二趟、第三趟分配和收集，分別位、百位進(jìn)行，最后得到一個(gè)有序例初始狀態(tài) 配 配一趟收集一趟收集 二趟收集二趟收集 三趟收集算法描時(shí)間復(fù)雜度分配其中：n——記錄d——關(guān)鍵字rd——關(guān)鍵字取值范空間復(fù)雜度：S(n)=2rd個(gè)隊(duì)列指針+n個(gè)指針域空123456789123456789f[0] e[0]== == ==f[3] ===67=67======

==67==67====1928436719258一趟收集 00

e[0]=

=e[7]=== = 二趟收集78165二趟收集78165

=====289 =====289e[2]= = e[5]= = =三趟收集

e[9