【文章內(nèi)容簡介】 序 ； 反之，若參加排序的記錄數(shù)量很大， 整個序列的排序過程 不可能在內(nèi)存中 完成 ，則稱此類排序問題 為 外部排序 。 四川大學計算機學院，主講教師：游洪躍 三、內(nèi)部排序的方法 內(nèi)部排序的過程是一個 逐步擴大 記錄的 有序序列長度 的過程。 經(jīng)過一趟排序 有序序列區(qū) 無 序 序 列 區(qū) 有序序列區(qū) 無 序 序 列 區(qū) 四川大學計算機學院，主講教師：游洪躍 基于不同的“ 擴大 ” 有序序列長度的 方法，內(nèi)部排序方法 大致可分下列幾種類型： 插入類 交換類 選擇類 歸并類 其它方法 四川大學計算機學院，主講教師：游洪躍 1. 插入類 將無序子序列中的 一個或幾個記錄 “ 插入 ” 到有序序列中，從而增加記錄的有序子序列的長度。 四川大學計算機學院，主講教師：游洪躍 2. 交換類 通過 “交換” 無序序列中的記錄從而得到其中 關(guān)鍵字最小 或 最大的記錄，并將它 加入到有序子序列中 ， 以此方法增加記錄的有序子序列的長度。 四川大學計算機學院，主講教師：游洪躍 3. 選擇類 從記錄的無序子序列中 “選擇”關(guān)鍵字最小或最大 的記錄，并將它加入到有序子序列 中，以此方法增加記錄的有序子序列的長度。 四川大學計算機學院，主講教師：游洪躍 4. 歸并類 通過 “歸并” 兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度。 5. 其它方法 四川大學計算機學院，主講教師：游洪躍 插 入 排 序 四川大學計算機學院，主講教師：游洪躍 有序序列 elem[1..i1] elem[i] 無序序列 elem[i..n] 一趟直接插入排序的基本思想： 有序序列 elem[1..i] 無序序列 elem[i+1..n] 四川大學計算機學院，主講教師：游洪躍 實現(xiàn)“一趟插入排序”可分三步進行： 3． 將 elem[i] 插入 (復制 )到 elem[j+1]的位置上。 2． 將 elem[j+1..i1]中的所有 記錄 均 后移 一個位置； 1． 在 elem[1..i1]中 查找 elem[i]的插入位置， elem[1..j] ? elem[i] elem[j+1..i1] ； 四川大學計算機學院，主講教師：游洪躍 直接插入排序 （基于順序查找） 不同的具體實現(xiàn)方法導致不同的算法描述 希爾排序 （基于逐趟縮小增量） 四川大學計算機學院，主講教師：游洪躍 一、直接插入排序 利用 “順序查找” 實現(xiàn) “在 elem[0..i1]中 查找 elem[i]的插入位置” 算法的實現(xiàn)要點： 四川大學計算機學院，主講教師：游洪躍 從 elem[i1]起向前進行順序查找 循環(huán)結(jié)束表明 elem[i]的插入位置為 j +1 j elem[i] for (j=i1。 j = 0 amp。amp。 elem[0]elem [j]。 j)。 // 從后往前找 j=i1 插入位置 四川大學計算機學院，主講教師：游洪躍 對于在查找過程中找到的那些關(guān)鍵字大于 elem[i](=e)的記錄，并在查找的同時實現(xiàn)記錄向后移動； for (j=i1。 e elem[j]。 j)。 elem[j+1] = elem[j] j elem[i] j= i1 上述循環(huán)結(jié)束后可以直接進行“插入” 插入位置 四川大學計算機學院，主講教師：游洪躍 令 i = 1， 3， …, n, 實現(xiàn)整個序列的排序。 for ( i=1。 in。 ++i ) if (elem[i] elem[i1]) { 在 elem[0..i1]中查找 elem[i]的插入位置 。 插入 elem[i] 。 } 四川大學計算機學院，主講教師：游洪躍 template class ElemType void StraightInsertSort(ElemType elem[], int n) // 操作結(jié)果 :對數(shù)組 elem作直接插入排序序 { for ( int i = 1。 i n。 i++) { // 第 i趟直接插入排序 ElemType e = elem[i]。 // 暫存 elem[i] int j。 // 臨時變量 for (j = i 1。 j = 0 amp。amp。 e elem[j]。 j) { // 將比 e大的計錄都后移 elem[j + 1] = elem[j]。 // 后移 } elem[j + 1] = e。 // j+1為插入位置 } } 四川大學計算機學院，主講教師：游洪躍 二、希爾排序（又稱縮小增量排序） 基本思想：對待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。 所謂“宏觀”調(diào)整，指的是，“跳躍式” 的插入排序。 具體做法為： 四川大學計算機學院，主講教師：游洪躍 將記錄序列分成若干子序列，分別對每個子序列進行插入排序。 其中， d 稱為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序 減為 1。 例如：將 n 個記錄分成 d 個子序列： {elem[0]， elem[0+d]， elem[0+2d]， … ， elem[0+kd] } {elem[1]， elem[1+d]， elem[1+2d]， … ， elem[1+kd] } … {elem[d1], elem[2d1], elem[3d1], …, elem[(k+1)d 1]} 四川大學計算機學院，主講教師：游洪躍 例如： 16 25 12 30 47 11 23 36 9 18 31 第一趟希爾排序，設(shè)增量 d =5 11 23 12 9 18 16 25 36 30 47 31 第二趟希爾排序，設(shè)增量 d = 3 9 18 12 11 23 16 25 31 30 47 36 第三趟希爾排序，設(shè)增量 d = 1 9 11 12 16 18 23 25 30 31 36 47 四川大學計算機學院，主講教師：游洪躍 template class ElemType void ShellInsert(ElemType elem[], int n, int incr) // 操作結(jié)果 : 對數(shù)組 elem作一趟增量為 incr的 Shell排序 ,對 // 插入排序作出的修改是子序列中前后相鄰記錄的增 // 量為 incr,而不是 1 { for ( int i = incr 。 i n。 i++) { // 第 i趟插入排序 ElemType e = elem[i]。 // 暫存 elem[i] int j。 // 臨時變量 for (j = i incr。 j = 0 amp。amp。 e elem[j]。 j = incr) { // 將子序列中比 e大的計錄都后移 elem[j + incr] = elem[j]。 // 后移 } elem[j + incr] = e。 // j+incr為插入位置 } } 四川大學計算機學院，主講教師：游洪躍 template class ElemType void ShellSort(ElemType elem[], int n, int inc[], int t) // 操作結(jié)果 : 按增量序列 inc[0 .. t 1 ]對數(shù)組 elem作 Shell排 // 序 { for ( int k = 0 。 k t。 k++) { // 第 k趟 Shell排序 ShellInsert(elem, n, inc[k])。 } } 四川大學計算機學院，主講教師：游洪躍 歸并排序 四川大學計算機學院，主講教師：游洪躍 歸 并 排 序 歸并排序的過程基于下列基本思想 進行： 將兩個或兩個以上的有序子序列 “歸并” 為一個有序序列。 四川大學計算機學院，主講教師：游洪躍 在內(nèi)部排序中，通常采用的是 2路歸并 排序。即： 將兩個 位置相鄰 的記錄有序子序列 歸并為 一個 記錄的有序序列 。 有 序 序 列 R[l..n] 有序子序列 R[l..m] 有序子序列 R[m+1..n] 這個操作對順序表而言，是輕而易舉的。 四川大學計算機學院，主講教師：游洪躍 歸并排序的算法 如果記錄無序序列 R[s..t] 的兩部分 R[s..?(s+t)/2?] 和 R[?(s+t)/2?+1..t] 分別按關(guān)鍵字有序， 則利用上述歸并算法很容易將它們歸并成整個記錄序列是一個有序序列。 由此，應該先分別對這兩部分進行 2路歸并排序。 四川大學計算機學院，主講教師：游洪躍 例如： 52, 23, 80, 36, 68, 14 (s=1, t=6) [ 52, 23, 80] [36, 68, 14] [ 52, 23][80] [ 52] [ 23, 52] [ 23, 52, 80] [36, 68][14] [36][68] [36, 68] [14, 36, 68] [ 14, 23, 36, 52, 68, 80 ] [23] 四川大學計算機學院，主講教師：游洪躍 快速排序 四川大學計算機學院，主講教師：游洪躍 一、起泡排序 假設(shè)在排序過程中，記錄序列 R[0..n1]的狀態(tài)為： 第 i 趟起泡排序 無序序列 R[0..ni] 有序序列 R[ni+1..n1] ni 無序序列 R[0..ni1] 有序序列 R[ni..n1] 比較相鄰記錄，將 關(guān)鍵字最大的記錄 交換到 ni 的位置上 四川大學計算機學院，主講教師：游洪躍 template class ElemType void BubbleSort(ElemType elem[], int n) // 操作結(jié)果 :在數(shù)組 elem中用起泡排序進行排序 { for (int i = n 1。 i 0。 i) { // 第 i趟起泡排序 for (int j = 0。 j i。 j++) { // 比較 elem[j]與 elem[j + 1] if (elem[j] elem[j + 1]) { // 如出現(xiàn)逆序 ,則交換 elem[j]和 // elem[j + 1] Swap(elem[j], elem[j + 1])。 } } } } 四川大學計算機學院，主講教師：游洪躍 二、一趟快速排序（一次劃分） 目標： 找一個記錄， 以它的關(guān)鍵字作為“樞軸” ， 凡其 關(guān)鍵字小于樞軸 的記錄均移動至該記錄之前 ， 反之，凡 關(guān)鍵字大于樞軸 的記錄均 移動至該記錄之后 。 致使 一趟排序 之后，記錄的無序序列 R[s..t]將 分割成兩部分 ： R[s..i1]和 R[i+1..t]， 且 R[j]≤ R[i] ≤ R[k] (s≤j≤i1) 樞軸 (i+1≤k≤t)。 四川大學計算機學院，主講教師：游洪躍 52 49 80 36 14 58 61 97 23 75s t low high 設(shè) R[s]=52 為樞軸 將 R[high].key 和 樞軸的關(guān)鍵字進行比較，要求 R[high].key ≥ 樞軸的關(guān)鍵字 將 R[low].key 和 樞軸的關(guān)鍵字進行比較，要求 R[low].key ≤ 樞軸的關(guān)鍵字 high 23 low 80 high 14 low 52 例如 R[0] 52 low high high high low 四川大學計算機學院，主講教師：游洪躍 可見，經(jīng)過“ 一次劃分 ” ，將關(guān)鍵字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 調(diào)整為 : 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在調(diào)整過程中，設(shè)立了兩個指針： low 和 high，它們的初值分別為： s 和 t， 之后逐漸減小 high，增加 low，并保證 R[high]≥52，和 R[low]≤52,否則進行記錄的 “ 交換 ” 。 四川大學計算機學院，主講教師：游洪躍 快速排序