摘要:概述堆排序是一種樹形選擇排序,是對直接選擇排序的有效改進。稱這個過程為堆排序。步驟實例實現堆排序需解決兩個問題如何將個待排序的數建成堆輸出堆頂元素后,怎樣調整剩余個元素,使其成為一個新堆。
概述
堆排序是一種樹形選擇排序,是對直接選擇排序的有效改進。
堆的定義如下:具有n個元素的序列(k1,k2,...,kn), 當且僅當滿足:
時稱之為堆。由堆的定義可以看出,堆頂元素(即第一個元素)必為最小項(小頂堆)或最大項(大頂堆)。
若以一維數組存儲一個堆,則堆對應一棵完全二叉樹,且所有非葉結點(有子女的結點)的值均不大于(或不小于)其子女的值,根結點(堆頂元素)的值是最小(或最大)的。
(a)大頂堆序列:(96, 83, 27, 38, 11, 09)
(b)小頂堆序列:(12, 36, 24, 85, 47, 30, 53, 91)
初始時把要排序的n 個數的序列看作是一棵順序存儲的二叉樹(一維數組存儲二叉樹),調整它們的存儲序,使之成為一個堆,將堆頂元素輸出,得到n 個元素中最小(或最大)的元素。然后對剩下的n-1個元素重新調整使之成為堆,輸出堆頂元素,得到n 個元素中次小(或次大)的元素。依此類推,直到最后得到有n個節點的有序序列。稱這個過程為堆排序。
步驟&實例實現堆排序需解決兩個問題:
如何將n 個待排序的數建成堆;
輸出堆頂元素后,怎樣調整剩余n-1 個元素,使其成為一個新堆。
建堆方法(小頂堆):
對初始序列建堆的過程,就是一個反復進行篩選的過程。
n 個結點的完全二叉樹,則最后一個結點是第n/2個結點的子樹。
篩選從第n/2個結點為根的子樹開始(n/2是最后一個有子樹的結點),使該子樹成為堆。
之后向前依次對各結點為根的子樹進行篩選,使之成為堆,直到根結點。
如圖建堆初始過程
無序序列:(49, 38, 65, 97, 76, 13, 27, 49)
(a) 無序序列,初始二叉樹,97(第8/2=4個結點)為最后一個結點(49)的父結點。
(b) 97>=49,替換位置,接下來對n/2的上一個結點65進行篩選。
(c) 13<=27且65>=13,替換65和13的位置,接下來對38進行替換(都大于它,不需操作),對49進行篩選。
(d) 13<=38且49>=13,替換49和13的位置,49>=27,替換49和27的位置。
(e) 最終得到一個堆,13是我們得到的最小數。
調整堆的方法(小頂堆):
設有m 個元素的堆,輸出堆頂元素后,剩下m-1 個元素。將堆底元素送入堆頂,堆被破壞,其原因僅是根結點不滿足堆的性質。
將根結點與左、右子樹中較小元素的進行交換。
若與左子樹交換:如果左子樹堆被破壞,則重復方法(2).
若與右子樹交換,如果右子樹堆被破壞,則重復方法(2).
繼續對不滿足堆性質的子樹進行上述交換操作,直到葉子結點,堆被建成。
調整堆只需考慮被破壞的結點,其他的結點不需調整。
代碼實現(Java)運行代碼結合注釋與上面的實例步驟進行對比思考。
package com.coder4j.main; public class HeapSort { /** * 調整為小頂堆(排序后結果為從大到?。? * * @param array是待調整的堆數組 * @param s是待調整的數組元素的位置 * @param length是數組的長度 * */ public static void heapAdjustS(int[] array, int s, int length) { int tmp = array[s]; int child = 2 * s + 1;// 左孩子結點的位置 System.out.println("待調整結點為:array[" + s + "] = " + tmp); while (child < length) { // child + 1 是當前調整結點的右孩子 // 如果有右孩子且小于左孩子,使用右孩子與結點進行比較,否則使用左孩子 if (child + 1 < length && array[child] > array[child + 1]) { child++; } System.out.println("將與子孩子 array[" + child + "] = " + array[child] + " 進行比較"); // 如果較小的子孩子比此結點小 if (array[s] > array[child]) { System.out.println("子孩子比其小,交換位置"); array[s] = array[child];// 把較小的子孩子向上移動,替換當前待調整結點 s = child;// 待調整結點移動到較小子孩子原來的位置 array[child] = tmp; child = 2 * s + 1;// 繼續判斷待調整結點是否需要繼續調整 if (child >= length) { System.out.println("沒有子孩子了,調整結束"); } else { System.out.println("繼續與新的子孩子進行比較"); } // continue; } else { System.out.println("子孩子均比其大,調整結束"); break;// 當前待調整結點小于它的左右孩子,不需調整,直接退出 } } } /** * 調整為大頂堆(排序后結果為從小到大) * * @param array是待調整的堆數組 * @param s是待調整的數組元素的位置 * @param length是數組的長度 * */ public static void heapAdjustB(int[] array, int s, int length) { int tmp = array[s]; int child = 2 * s + 1;// 左孩子結點的位置 System.out.println("待調整結點為:array[" + s + "] = " + tmp); while (child < length) { // child + 1 是當前調整結點的右孩子 // 如果有右孩子且大于左孩子,使用右孩子與結點進行比較,否則使用左孩子 if (child + 1 < length && array[child] < array[child + 1]) { child++; } System.out.println("將與子孩子 array[" + child + "] = " + array[child] + " 進行比較"); // 如果較大的子孩子比此結點大 if (array[s] < array[child]) { System.out.println("子孩子比其大,交換位置"); array[s] = array[child];// 把較大的子孩子向上移動,替換當前待調整結點 s = child;// 待調整結點移動到較大子孩子原來的位置 array[child] = tmp; child = 2 * s + 1;// 繼續判斷待調整結點是否需要繼續調整 if (child >= length) { System.out.println("沒有子孩子了,調整結束"); } else { System.out.println("繼續與新的子孩子進行比較"); } // continue; } else { System.out.println("子孩子均比其小,調整結束"); break;// 當前待調整結點大于它的左右孩子,不需調整,直接退出 } } } /** * 堆排序算法 * * @param array * @param inverse true 為倒序排列,false 為正序排列 */ public static void heapSort(int[] array, boolean inverse) { // 初始堆 // 最后一個有孩子的結點位置 i = (length - 1) / 2, 以此向上調整各結點使其符合堆 System.out.println("初始堆開始"); for (int i = (array.length - 1) / 2; i >= 0; i--) { if (inverse) { heapAdjustS(array, i, array.length); } else { heapAdjustB(array, i, array.length); } } System.out.println("初始堆結束"); for (int i = array.length - 1; i > 0; i--) { // 交換堆頂元素H[0]和堆中最后一個元素 int tmp = array[i]; array[i] = array[0]; array[0] = tmp; // 每次交換堆頂元素和堆中最后一個元素之后,都要對堆進行調整 if (inverse) { heapAdjustS(array, 0, i); } else { heapAdjustB(array, 0, i); } } } public static void main(String[] args) { int[] array = { 49, 38, 65, 97, 76, 13, 27, 49 }; heapSort(array, false); for (int i : array) { System.out.print(i + " "); } } }
運行結果:
初始堆開始 待調整結點為:array[3] = 97 將與子孩子 array[7] = 49 進行比較 子孩子比其小,交換位置 沒有子孩子了,調整結束 待調整結點為:array[2] = 65 將與子孩子 array[5] = 13 進行比較 子孩子比其小,交換位置 沒有子孩子了,調整結束 待調整結點為:array[1] = 38 將與子孩子 array[3] = 49 進行比較 子孩子均比其大,調整結束 待調整結點為:array[0] = 49 將與子孩子 array[2] = 13 進行比較 子孩子比其小,交換位置 繼續與新的子孩子進行比較 將與子孩子 array[6] = 27 進行比較 子孩子比其小,交換位置 沒有子孩子了,調整結束 初始堆結束 待調整結點為:array[0] = 97 將與子孩子 array[2] = 27 進行比較 子孩子比其小,交換位置 繼續與新的子孩子進行比較 將與子孩子 array[6] = 49 進行比較 子孩子比其小,交換位置 沒有子孩子了,調整結束 待調整結點為:array[0] = 97 將與子孩子 array[1] = 38 進行比較 子孩子比其小,交換位置 繼續與新的子孩子進行比較 將與子孩子 array[3] = 49 進行比較 子孩子比其小,交換位置 沒有子孩子了,調整結束 待調整結點為:array[0] = 65 將與子孩子 array[1] = 49 進行比較 子孩子比其小,交換位置 繼續與新的子孩子進行比較 將與子孩子 array[4] = 76 進行比較 子孩子均比其大,調整結束 待調整結點為:array[0] = 76 將與子孩子 array[2] = 49 進行比較 子孩子比其小,交換位置 沒有子孩子了,調整結束 待調整結點為:array[0] = 97 將與子孩子 array[1] = 65 進行比較 子孩子比其小,交換位置 沒有子孩子了,調整結束 待調整結點為:array[0] = 76 將與子孩子 array[1] = 97 進行比較 子孩子均比其大,調整結束 待調整結點為:array[0] = 97 97 76 65 49 49 38 27 13
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/65436.html
摘要:之所以把歸并排序快速排序希爾排序堆排序放在一起比較,是因為它們的平均時間復雜度都為。歸并排序是一種穩定的排序方法。因此,快速排序并不穩定。希爾排序思想先將整個待排序的記錄序列分割成為若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言 算法為王。 想學好前端,先練好內功,只有內功深厚者,前端之路才...
摘要:前面介紹了七大算法的思想與實現步驟,下面來做一個歸總。直到無序區中的數為零,結束排序。步驟以從小到大為例,排序數組大小為。比較完以后則排序結束。堆排序思想堆排序是采用樹的形式的數據結構來進行排序的,其中每一個堆都是完全二叉樹。 前面介紹了七大算法的思想與實現步驟,下面來做一個歸總。 排序方法 平均復雜度 最壞復雜度 最好復雜度 輔助空間 穩定性 直接選擇排序 O(n^2...
摘要:奇妙的記憶點不穩定內排序基本思想分為兩步建堆與維持堆的性質首先我們要先理解堆是什么東西堆其實就是一個完全二叉樹我們可以使用順序表存儲一個二叉樹如下圖所示來存儲其中分為最大堆最小堆而最大堆就是上頭大下頭小最小堆則反之明白了堆的定義我們就可以開 奇妙的記憶點: 不穩定 內排序 基本思想: 分為兩步,建堆與維持堆的性質,首先我們要先理解堆是什么東西.堆其實就是一個完全二叉樹,我們可以使用...
摘要:當到達時等同于直接插入排序,此時序列已基本有序,所有記錄在統一組內排好成有序序列。當面對大量數據時,希爾排序將比直接插入排序更具優勢圖示講解第一趟取增量,所有間隔為的元素分在一組,在各個組中分別進行直接插入排序。 ...
閱讀 2772·2021-11-02 14:42
閱讀 3163·2021-10-08 10:04
閱讀 1184·2019-08-30 15:55
閱讀 1025·2019-08-30 15:54
閱讀 2311·2019-08-30 15:43
閱讀 1680·2019-08-29 15:18
閱讀 863·2019-08-29 11:11
閱讀 2362·2019-08-26 13:52