天津科技大學(xué)數(shù)據(jù)結(jié)構(gòu)排序(已修改)
2025-10-26 15:10 本頁面
【正文】 ? 第 十章 排序 概述 插入排序 交換排序 選擇排序 歸并排序 分配排序 外排序 排序是計(jì)算機(jī)中經(jīng)常遇到的操作。 第十章 排 序 概述 排序 計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作， 將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列 。 例如：將下列關(guān)鍵字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 調(diào)整為 14, 23, 36, 49, 52, 58, 61 ,75, 80, 97 一般，假設(shè)含 n個(gè)記錄的序列為 { R1, R2, … ， Rn } 其相應(yīng)的關(guān)鍵字序列為 { K1, K2, … ， Kn } 這些關(guān)鍵字相互間可以進(jìn)行比較，即它們之間存在一個(gè)關(guān)系 Kp1≤Kp2≤…≤Kp n 按此固有關(guān)系將原記錄序列重新排列為 { Rp1, Rp2, … ， Rpn } 的操作稱作 排序 。 排序算法的穩(wěn)定性 判斷標(biāo)準(zhǔn) ：關(guān)鍵字相同的數(shù)據(jù)對(duì)象在排序過程中是否保持前后次序不變。 如 2, 2*,1，排序后若為 1, 2*, 2 ，則該排序方法是不穩(wěn)定的。 內(nèi)部排序和外部排序 若 整個(gè)排序過程不需要訪問外存 便能完成，則稱此類排序問題為 內(nèi)部排序 ； 若 參加排序的記錄數(shù)量很大 ， 整個(gè)序列的排序過程不可能在內(nèi)存中完成 ，則稱此類排序問題為 外部排序 。 內(nèi)部排序的方法 內(nèi)部排序的過程是一個(gè) 逐步擴(kuò)大記錄的有序序列長度的過程 。在排序的過程中，參與排序的記錄序列中存在兩個(gè)區(qū)域： 有序區(qū)和無序區(qū) 。 有序序列區(qū) 無序序列區(qū) 使有序區(qū)中記錄的數(shù)目增加一個(gè)或幾個(gè)的操作稱為 一趟排序 。 逐步擴(kuò)大記錄有序序列長度的方法 大致有下列幾類： 插入類 將無序序列中的一個(gè)或幾個(gè)記錄“插入”到有序序列中； 交換類 通過“交換”無序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加到有序子序列中 。 選擇類 從記錄的無序子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中 。 歸并類 通過“歸并”兩個(gè)或兩個(gè)以上的記錄有序序列 。 其它方法 插入排序 假設(shè)在排序過程中，記錄序列 R[1..n]的狀態(tài)為： 有序序列 R[1..i1] R[i] 無序序列 R[i+1..n] 則一趟直接插入排序的 基本思想 ： 將記錄 R[i]插入到有序子序列 R[1..i1]中，使記錄的有序序列從 R[1..i1]變?yōu)?R[1..i]。 完成一趟“插入”需分三步進(jìn)行： 1．查找 R[i]的插入位置 j+1； 2．將 R[j+1..i1]中的記錄后移一個(gè)位置； 3．將 R[i]復(fù)制到 R[j+1]的位置上。 一、 直接插入排序 利用順序查找實(shí)現(xiàn)“在 R[1..i1]中查找 R[i]的插入位置”的插入排序。 直接插入排序算法的三個(gè)要點(diǎn)： 從 R[i1]起向前順序查找，監(jiān)視哨設(shè)置在 R[0]； R[0] = R[i]。 // 設(shè)置“哨兵” for (j=i1。 R[0].keyR[j].key。 j)。 // 從后往前找 //循環(huán)結(jié)束后，可得 R[i]的插入位置 j+1 2．在查找過程中找到的關(guān)鍵字大于 R[0].key的記錄需在查找的同時(shí)向后移動(dòng)； for (j=i1。 R[0].keyR[j].key。 j) R[j+1] = R[j]。 3． i = 2， 3， …, n, 實(shí)現(xiàn)整個(gè)序列的排序。 算法描述如下 : void InsertionSort ( Elem R[ ], int n) { // 對(duì)記錄序列 R[1..n]作直接插入排序。 for ( i=2。 i=n。 ++i ) { R[0] = R[i]。 // 復(fù)制為監(jiān)視哨 for ( j=i1。 R[0].key R[j].key。 j ) R[j+1] = R[j]。 // 記錄后移 R[j+1] = R[0]。 // 插入到正確位置 } } // InsertSort 排序的時(shí)間分析： 實(shí)現(xiàn)排序的基本操作有兩個(gè)： （ 1）“比較”序列中兩個(gè)關(guān)鍵字的大??； （ 2）“移動(dòng)”記錄。 對(duì)于直接插入排序： 最好的情況 (關(guān)鍵字在記錄序列中順序有序 )： “比較”的次數(shù)： 1*(n1)=n1 “移動(dòng)”的次數(shù)： 0 最壞的情況 (關(guān)鍵字在記錄序列中逆序有序 )： “比較”的次數(shù) “移動(dòng)”的次數(shù) 直接插入排序所需進(jìn)行關(guān)鍵字間的比較次數(shù)和記錄移動(dòng)的次數(shù)均為 n2/4，所以直接插入排序的時(shí)間復(fù)雜度為 O(n2)。 直接插入排序是一種穩(wěn)定的排序方法。 原因：關(guān)鍵字相同的兩個(gè)對(duì)象，在整個(gè)排序過程中，不會(huì)通過比較而相互交換。 二、折半插入排序 由于 R[1..i1]是一個(gè)按關(guān)鍵字有序的有序序列，則可 利用折半查找實(shí)現(xiàn)“在 R[1..i1]中查找 R[i]的插入位置” ，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判颉? 折半插入排序比直接插入排序明顯地減少了關(guān)鍵字間的“比較”次數(shù)，但記錄“移動(dòng)”的次數(shù)不變。 void BInsertionSort (Elem R[ ]， int n) { // 對(duì)記錄序列 R[1..n]作 折半插入排序 。 for ( i=2。 i=。 ++i ) { R[0] = R[i]。 // 將 R[i]暫存到 R[0] low = 1。 high = i1。 while (low=high){//在 R[low..high]中折半查找插入的位置 m = (low+high)/2。 // 折半 if (R[0].key R[m].key)) high=m1。 else low = m+1。 } for ( j=i1。 j=high+1。 j ) R[j+1] = R[j]。 // 記錄后移 R[high+1] = R[0]。 // 插入 } } // BInsertSort 三、表插入排序 為了減少在排序過程中進(jìn)行的“移動(dòng)”記錄的操作 ，改變記錄的存儲(chǔ)結(jié)構(gòu)，利用 靜態(tài)鏈表 進(jìn)行排序，并在排序完成后，一次性地調(diào)整各個(gè)記錄相互之間的位置，從而實(shí)現(xiàn)排序。 例如： 下標(biāo) 0 1 2 3 4 5 6 7 8 關(guān)鍵字 MAXINT 49 38 65 97 76 13 27 49* 初值 1 0 i=2 2 0 1 i=3 2 3 1 0 i=4 2 3 1 4 0 i=5 2 3 1 5 0 4 i=6 6 3 1 5 0 4 2 i=7 6 3 1 5 0 4 7 2 終值 6 8 1 5 0 4 7 2 3 void LInsertionSort (Elem SL[ ]， int n){ // 對(duì)記錄序列 SL[1..n]作 表插入排序 。 SL[0].key = MAXINT 。 SL[0].next = 1。 SL[1].next = 0。 for ( i=2。 i=n。 ++i ){//結(jié)點(diǎn) i插在結(jié)點(diǎn) j、 k之間 j=0。 k = SL[0].next。 //j頭結(jié)點(diǎn)， k a1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1