數(shù)據(jù)結構 選擇排序ppt課件.ppt

選擇排序 Selectionsort 1 選擇排序 Selectionsort 是以選擇為基礎的一種常用排序方法 從記錄的無序子序列中 選擇 關鍵字最小或最大的記錄 并將其加入到有序子序列的一端 以增加記錄的有序子序列的長度 它也有幾種不同的實現(xiàn)方法 這里僅介紹簡單選擇排序 樹形排序和堆排序 2 1 簡單選擇排序 1 算法描述簡單選擇排序算法的基本思路 對于一組關鍵字 Kl K2 Kn 將其由小到大進行排序 首先從Kl K2 Kn中選擇最小值 假設是Kk 則將Kk與K1對換 然后從K2 K3 Kn中選擇最小值Kk 1 再將Kk 1與K2對換 如此進行選擇和調(diào)換 對第i趟選擇排序 進行n i次關鍵字比較 從n i 1個記錄中選出關鍵字最小的記錄 并與第i個記錄交換 令i從1至n 1 進行n 1趟選擇排序 一個由小到大的有序序列就形成了 3 例1設有一組關鍵字 49 39 66 49 76 11 27 96 這里n 8 試用簡單選擇排序方法 將這組記錄由小到大進行排序 其排序過程如圖所示 4 算法實現(xiàn)如下 voidSelectSort SqList SelectSort 5 2 算法分析在簡單選擇排序中 無論待排序的記錄初始序列是否有序 都需要執(zhí)行n n 1 2次關鍵字的比較操作 如果待排序的記錄初始序列就是已經(jīng)排好序的正列 則無須移動記錄 因為每個元素都位于其最終位置上了 而如果待排序的記錄初始序列是逆序 即在最壞情況下 則要做3 n 1 次記錄移動 所以 簡單選擇排序的時間復雜度是O n n 由上面的例1很顯然看到 49在排序前位于49 的前面 而經(jīng)簡單選擇排序后卻位于49 后面了 它們的相對位置發(fā)生了顛倒 因此簡單選擇排序算法是不穩(wěn)定排序算法 6 3 堆排序 1 堆的定義堆是一個記錄序列 k1 k2 kn 對于列表中位置i 編號從1開始 處的記錄的關鍵字ki 當且僅當滿足下列關系時 稱之為堆 ki k2i或ki k2iki k2i 1ki k2i 1 i 1 2 n 2 其中 每個結點關鍵字都不小于其子孫結點關鍵字的堆稱為 大根堆 而每個結點關鍵字都不小于其子孫結點關鍵字的堆稱為 小根堆 下面的討論中以小根堆為例 7 判斷下列序列是否為堆 100 85 98 77 80 60 82 40 20 15 67 100 98 85 82 80 77 60 40 20 15 67 15 20 40 60 67 77 80 82 85 98 100 8 我們已經(jīng)知道 對于一棵有n個結點的完全二叉樹 當它的結點由上而下 自左至右編號之后 編號為1 n 2 的結點為分支結點 編號大于 n 2 的結點為葉子結點 對于每個編號為i的分支結點 它的左孩子的編號為2i 它的右孩子的編號為2i 1 對于每個編號為i i 1 的結點 它的雙親的編號為 i 2 因此 我們還可以借助完全二叉樹來描述堆的概念 若完全二叉樹中任一非葉子結點的值均小于等于 或大于等于 其左 右孩子結點的值 則從根結點開始按結點編號排列所得的結點序列就是一個堆 9 10 2 算法描述堆頂記錄對應完全二叉樹的根結點 堆頂記錄關鍵字是所有記錄關鍵字的最值 堆排序就是利用堆的上述特征完成排序的 在輸出堆頂?shù)淖畲?或最小 之后 使得剩余的n 1個記錄的序列重新調(diào)整為一個堆 于是又得到次大 或次小 值 如此反復執(zhí)行 直至所以記錄都排序為一個有序序列 這就是堆排序 HeapSort 11 由于初始記錄序列不一定滿足堆關系 因此堆排序過程大體分兩步處理 初建堆 從堆的定義出發(fā) 先取i n 2 它一定是第n個結點雙親的編號 將以i結點為根的子樹調(diào)整成為堆 然后令i i 1 再將以i結點為根的子樹調(diào)整成為堆 此時可能會反復調(diào)整某些結點 直到i 1為止 堆初建完成 堆排序 首先輸出堆頂元素 一般是最小值 讓堆中最后一個元素上移到原堆頂位置 然后恢復堆 因為經(jīng)過第一步輸出堆頂元素的操作后 往往破壞了原來的堆關系 所以要恢復堆 重復執(zhí)行輸出堆頂元素 堆尾元素上移和恢復堆的操作 直到全部元素輸出完為止 按輸出元素的前后次序排列 就形成了有序序列 完成了堆排序的操作 12 例設有n個記錄 n 8 的關鍵字是 30 50 60 35 86 10 40 45 試用堆排序方法 將這組記錄由小到大進行排序 13 第一步 初始建堆 其建堆過程如圖所示 因為n 8 所以從i 4開始 14 第二步 堆排序 這是一個反復輸出堆頂元素 將堆尾元素移至堆頂 再調(diào)整恢復堆的過程 恢復堆的過程與初建堆中i 1時所進行的操作完全相同 請注意 每輸出一次堆頂元素 堆尾的邏輯位置退1 直到堆中剩下一個元素為止 排序過程如圖所示 15 16 輸出序列 1030354045506086 17 由上可知 調(diào)整恢復堆操作過程要被多次反復調(diào)用 即當i值確定之后 以ki為比較參照值 與其左 右孩子的關鍵字比較和調(diào)整 使以結點i為根的子樹成為堆 因此把此過程設計成函數(shù)Heap voidHeap RedTyper inti intm i是根結點編號 m是以i結點為根的子樹的最后一個結點編號 x r i j 2 i x保存根記錄的內(nèi)容 j為左孩子編號 while j m if j m r j key r j 1 key j 當結點i有左 右兩個孩子時 j取關鍵字值較小的孩子結點編號 if r j key x key r i r j i j j 2 i 向下一層探測 elsej m 1 x key小于左 右孩于的關鍵字 強制使j m 以便結束循環(huán) r i x Heap 18 另外 還需要設計一個主體算法 使在初建堆階段 讓i從 n 2 變化到1 循環(huán)調(diào)用heap函數(shù) 而在堆排序階段 每輸出一次堆頂元素 將堆尾元素移至堆頂之后 就要調(diào)用一次heap函數(shù)來恢復堆 主體算法由函數(shù)Heapsort來實現(xiàn) voidHeapsort RedTyper intn n為文件的實際記錄數(shù) r o 沒有使用 for i n 2 i 1 i Heap r i n 初建堆 for v n v 2 v x r 1 r 1 r v r v x 堆頂堆尾元素對換 Heap r 1 v 1 本次比上次少處理一個記錄 Heapsort 19 3 算法分析在堆排序圖示例中 堆越畫越小 堆中結點越來越少 實際上 在用來存儲堆的數(shù)組中堆頂元素輸出之后并未刪除 而是與堆尾元素對換 從圖示看輸出的是一個由小到大的升序序列 實際最后數(shù)組中記錄的關鍵字從r l key到r n key是一個由大到小的降序序列 算法Heap的時間復雜度與堆所對應的完全二叉樹的樹深log2n相關 而算法Heapsort中對Heap的調(diào)用數(shù)量級為n 所以整個堆排序的時間復雜度為O nlog2n 20 穩(wěn)定性如何 21 判斷下列序列是否為堆 若不是 則把