[計算機(jī)軟件及應(yīng)用]第八章排序(編輯修改稿)
2024-11-12 23:21 本頁面
【文章內(nèi)容簡介】 6 [97 ] 排序結(jié)束： 13 27 38 49 65 76 97 k指示序列中最小數(shù)的位置 j指示當(dāng)前比較數(shù)的位置 簡單選擇排序算法簡單，但是速度較慢，時間復(fù)雜度為 O（ n2）， 并且是一種 不穩(wěn)定 的排序方法，在排序過程中也只需要一個用來交換記錄的暫存單元作為輔助空間。 選擇排序 堆排序 堆排序（ Heap Sort）是利用堆的特性進(jìn)行排序。 堆的定義如下 : n個元素的序列為｛ K1， K2， … ， Kn｝， 當(dāng)且僅當(dāng)滿足下列關(guān)系時，稱之為堆。 Ki≤K2i ， Ki≤K2i+1或 Ki≥K2i ， Ki≥K2i+1（ i=1， 2， … ， n/2） 若將與此序列對應(yīng)的一維數(shù)組看成是一棵完全二叉樹按層次編號的順序存儲，則堆的含義表明，完全二叉樹中所有非終端結(jié)點的值均不小于（或不大于）其左、右孩子結(jié)點的值。因此，堆頂元素的值必為序列中的最大值或最小值（即大頂堆或小頂堆）。 選擇排序 選擇排序 堆排序的基本思想是 :對一組待排序的記錄，首先把它們按堆的定義排成一個堆，將堆頂元素取出 。然后把剩下的記錄再排成堆，取出堆頂元素 。依次下去，直到取出全部元素，從而將全部記錄排成一個有序序列。 選擇排序 實現(xiàn)堆排序需要解決兩個問題 : （ 1）如何將一個無序序列建成一個堆 ? （ 2）如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個新的堆 ? 建堆就是把待排序的記錄序列｛ R1， R2， … ， Rn｝，按照堆的定義調(diào)整為堆，使父結(jié)點的關(guān)鍵字大于（或小于）子結(jié)點的關(guān)鍵字。為此，我們先把待排序數(shù)據(jù)初始次序置入完全二叉樹的各個結(jié)點中，然后由下而上逐層進(jìn)行父子結(jié)點的關(guān)鍵字比較并交換，直到使其最后滿足堆的條件。 建堆時是從最后一個非終端結(jié)點 n/2 開始的。 例如，假定待排序的一組數(shù)據(jù)序列為 : 42 36 56 78 67 11 27 36 選擇排序 40 55 49 73 81 64 36 12 27 98 例如 : 排序之前的關(guān)鍵字序列為 1236817349988155 現(xiàn)在，左 /右子樹都已經(jīng)調(diào)整為堆，最后只要調(diào)整根結(jié)點，使整個二叉樹是個“堆”即可。 9840對一組有 n個記錄的待排序序列進(jìn)行按關(guān)鍵字遞減排序時，先建立一個大頂堆，然后選取關(guān)鍵字值最大的堆頂記錄與最后一個記錄交換，再對前 n1個記錄調(diào)整為一個新的大頂堆，如此反復(fù)直到排序結(jié)束。 選擇排序 堆排序?qū)?n較大的文件很有效，對記錄數(shù)較少的文件不值得提倡。整個堆排序的時間復(fù)雜度為 O（ nlog2n）， 堆排序僅需一個記錄大小供交換用的輔助存儲空間。對于存在相同關(guān)鍵字的記錄的情況，堆排序是 不穩(wěn)定 的。 選擇排序 交換排序 基本思想是 : 兩兩比較待排序記錄的關(guān)鍵字，若發(fā)現(xiàn)兩個記錄的次序為逆序時，交換其存儲位置，直到?jīng)]有逆序的記錄為止。 ? 冒泡排序 ? 快速排序 交換排序 冒泡排序 冒泡排序是一種簡單的排序方法。 基本思想 :對所有相鄰記錄的關(guān)鍵字值進(jìn)行比較，如果是逆序（ r［ i］ r［ i+1］），則交換其位置，經(jīng)過多趟排序，最終使整個序列有序。 假設(shè)在排序過程中 ,記錄序列 R[1..n]的狀態(tài)為 : 第 i 趟起泡排序 無序序列 R[1..ni+1] 有序序列 R[ni+2..n] ni+1 無序序列 R[1..ni] 有序序列 R[ni+1..n] 比較相鄰記錄，將 關(guān)鍵字最大的記錄 交換到 ni+1 的位置上 交換排序 處理過程為 : 第一趟 :從第一條記錄 r［ 1］開始，直到最后一條記錄 r［ n］，對兩兩相鄰的記錄依此比較，若發(fā)現(xiàn)為逆序，則立即交換其位置，最后使這 n條記錄中關(guān)鍵字最大的記錄“下沉”到最底部，既被交換到第 n個位置上，它不參與下一趟排序 。 第二趟 :從第一條記錄 r［ 1］開始，直到第 n1條記錄 r［ n1］，對兩兩相鄰的記錄依此比較，若發(fā)現(xiàn)為逆序，則立即交換其位置，最后使這 n1條記錄中關(guān)鍵字最大的記錄“下沉”到次底部，既被交換到第 n1個位置上，它不參與下一趟排序 。 如此反復(fù)，最多經(jīng)過（ n1）趟冒泡排序，就可以使整個序列成為有序序列。 49 38 65 97 76 13 27 30 初始關(guān)鍵字 38 49 65 76 13 27 30 97 第一趟 38 49 65 13 27 30 76 第二趟 38 49 13 27 30 65 第三趟 38 13 27 30 49 第四趟 13 27 30 38 第五趟 13 27 30 第六趟 38 49 76 97 13 97 2797 97 30 13 76 76 76 13 65 2730 65 2765 3013 49 49 49 273013 38 27 38 3038 例如，一組待排序的記錄的關(guān)鍵字如下，要求按照關(guān)鍵字由小到大進(jìn)行排序。 42 36 56 78 67 11 27 36 交換排序 初始狀態(tài) 42 36 56 78 67 11 27 36 78 i=1 36 42 56 67 11 27 36 67 i=2 36 42 56 11 27 36 56 78 i=3 36 42 11 27 36 42 67 78 i=4 36 11 27 36 36
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1