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