數(shù)據(jù)結(jié)構(gòu) 選擇排序ppt課件.ppt

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