【正文】 R[(k+1)d]} … {R[2], R[2+d], R[2+2d], … ,R[2+kd]} 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 取 d3=1 三趟分組： 13 4 48 38 27 49 55 65 97 76 三趟排序： 4 13 27 38 48 49 55 65 76 97 例 初始： 49 38 65 97 76 13 27 48 55 4 一趟排序： 13 27 48 55 4 49 38 65 97 76 二趟排序： 13 4 48 38 27 49 55 65 97 76 取 d1=5 一趟分組： 49 38 65 97 76 13 27 48 55 4 取 d2=3 二趟分組： 13 27 48 55 4 49 38 65 97 76 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 例 49 38 65 97 76 13 27 48 55 4 j i 49 13 3827 一趟排序： 13 27 48 55 4 49 38 65 97 76 j i j i 27 4 j i j i 55j i 38j i j i j i 二趟排序： 13 4 48 38 27 49 55 65 97 76 j i j i 6548 j i 97 55 j i 76 4 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 算法描述： void ShellInsert(SqList amp。 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 其中 d為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序減為 1。 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 三、希爾排序 (縮小增量法 ) 基本思想：對(duì)待排記錄系列，先作 “ 宏觀 ” 調(diào)整，再作 “ 微觀 ” 調(diào)整。 // 插入 } } // BInsertSort 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 ? 算法評(píng)價(jià) ? 時(shí)間復(fù)雜度： T(n)=O(n178。 j ) R[j+1] = R[j]。 // 插入點(diǎn)在高半?yún)^(qū) } for ( j=i1。 // 折半 if (R[0].key R[m].key)) high = m1。 high = i1。 ++i ) { R[0] = R[i]。 for ( i=2。) 若待排序記錄是隨機(jī)的，取平均值 關(guān)鍵字 “比較” 次數(shù)： 記錄 “移動(dòng)” 次數(shù)： 空間復(fù)雜度： 時(shí)間復(fù)雜度： S(n)=O(1) 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 因?yàn)?R[1..i1]是一個(gè)按關(guān)鍵字有序的有序序列，則可以 利用折半查找實(shí)現(xiàn) “ 在 R[1..i1]中查找 R[i]的插入位置 ” ，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判颉? // 插入到正確位置 } } // InsertSort 算法描述： 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 例 49 38 65 97 76 13 27 i=2 38 (38 49) 65 97 76 13 27 i=3 65 (38 49 65) 97 76 13 27 i=4 97 (38 49 65 97) 76 13 27 i=5 76 (38 49 65 76 97) 13 27 i=6 13 (13 38 49 65 76 97) 27 i=1 ( ) i=7 (13 38 49 65 76 97) 27 27 j j j j j j 97 76 6549 38 27 (13 27 38 49 65 76 97) 排序結(jié)果： 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 （ 1）“比較”序列中兩個(gè)關(guān)鍵字的大??； 時(shí)間分析： 實(shí)現(xiàn)排序的基本操作有兩個(gè)： （ 2）“移動(dòng)”記錄。 j ) R[j+1] = R[j]。 // 復(fù)制為監(jiān)視哨 for ( j=i1。 i=n。 if(R[i].keyR[i1].key){ 將 R[i]插入到 = R[1..i1]中 } 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 void InsertionSort ( Elem R[ ], int n) { // 對(duì)記錄序列 R[1..n]作直接插入排序。 i=2。 R[j+1] = R[j] 3. i = 2， 3， …, n, 實(shí)現(xiàn)整個(gè)序列的排序。 R[0].keyR[j].key。 // 從后往前找 return j+1。 R[0].keyR[j].key。 R[0] = R[i]。 排序過程： 整個(gè)排序過程為 i1趟插入，即先將序列中第 1個(gè)記錄看成是一個(gè)有序子序列，然后從第 2個(gè)記錄開始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序 。 1．查找 R[i]的插入位置 j+1； R[1..j] ≤ R[i] ＜ R[j+1..i1] 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 一、直接插入排序 二、折半插入排序 三、希爾排序 167。 167。 下面將對(duì)每一類的排序算法介紹一至兩個(gè)排序算法。 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 從記錄的無序子序列中 “ 選擇 ” 關(guān)鍵字最小 或最大的記錄 ，并將它 加入到有序子序列中 ，以此方法增加記錄的有序子序列的長(zhǎng)度 。 使有序區(qū)中記錄的數(shù)目增加一個(gè)或幾個(gè)的操作稱為 一趟排序 。 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 三、內(nèi)部排序的方法 有序序列區(qū) 無 序 序 列 區(qū) 內(nèi)部排序的過程是一個(gè)逐步擴(kuò)大記錄的有序序列長(zhǎng)度的過程 。 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 二、內(nèi)部排序和外部排序 在本章內(nèi)先討論內(nèi)部排序的各種方法，然后介紹外部排序的基本過程。 排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組 “ 無序 ” 的記錄序列調(diào)整為 “ 有序 ” 的記錄序列。 基數(shù)排序 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 167。 選擇排序 167。 插入排序 167。 王秀章 \ 物理系 數(shù)據(jù)結(jié)構(gòu) —— 排序 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 第十章 排序 167。 167。 交換排序 167。 歸并排序 167。 一、什么是排序？ 二、內(nèi)部排序和外部排序 三、內(nèi)部排序的方法 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 167。 一、什么是排序？ 例如：將下列關(guān)鍵字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 調(diào)整為 14, 23, 36, 49, 52, 58, 61 ,75, 80, 97 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 一般情況下， 假設(shè)含 n個(gè)記錄的序列為 { R1, R2, … ， Rn } 其相應(yīng)的關(guān)鍵字序列為 { K1, K2, … ， Kn } 這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在著這樣一個(gè)關(guān)系 Kp1≤Kp2≤…≤K pn 按此固有關(guān)系將式 (1)的記錄序列重新排列為 { Rp1, Rp2, … ， Rpn } 的操作稱作 排序 。 若 整個(gè)排序過程不需要訪問外存 便能完成，則稱此類排序問題 為內(nèi)部排序 ； 反之，若參加排序的記錄數(shù)量很大，整個(gè)序列的排序過程 不可能在內(nèi)存中完成 ，則稱此類排序問題 為外部排序 。在排序的過程中，參與排序的記錄序列中存在兩個(gè)區(qū)域：有序區(qū)和無序區(qū)。 有 序 序 列 區(qū) 無序序列區(qū) 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 將無序子序列中的 一個(gè)或幾個(gè)記錄 “ 插入 ” 到有序序列中，從而增加記錄的有序子序列的長(zhǎng)度； 逐步擴(kuò)大記錄有序序列長(zhǎng)度的方法大致有下列幾類： 通過 “ 交換 ” 無序序列中的記錄從而得到其中關(guān)鍵字最小 或 最大 的記錄，并將它 加入到有序子序列中 ，以此方法增加記錄的有序子序列的長(zhǎng)度 。 4. 歸并類 通過 “ 歸并 ” 兩個(gè)或兩個(gè)以上的記錄有序子序列，逐步增加記錄有序序列的長(zhǎng)度 。 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 有序序列 R[1..i1] 無序序列 R[i..n] R[i] 假設(shè)在排序過程中，記錄序列 R[1..n]的狀態(tài)為： 有序序列 R[1..i] 無序序列 R[i+1..n] 則 一趟直接插入排序的基本思想為： 將記錄 R[i]插入到有序子序列 R[1..i1]中，使記錄的有序序列從 R[1..i1]變?yōu)?R[1..i]。 插入排序 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 顯然，完成這個(gè) “ 插入 ” 需分三步進(jìn)行： 2．將 R[j+1..i1]中的記錄后移一個(gè)位置； 3．將 R[i]復(fù)制到 R[j+1]的位置上。 插入排序 湖北師范學(xué)院物理系 王秀章主講 2/14/2022 一、直接插入排序