排序算法是《數(shù)據(jù)結(jié)構(gòu)與算法》中最基本的算法之一。排序算法可以分為內(nèi)部排序和外部排序,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序,而外部排序是因排序的數(shù)據(jù)很大,一次不能容納全部的排序記錄,在排序過程中需要訪問外存。常見的內(nèi)部排序算法有:插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。以下是堆排序算法:
堆排序(Heapsort)是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。堆積是一個近似完全二叉樹的結(jié)構(gòu),并同時滿足堆積的性質(zhì):即子結(jié)點的鍵值或索引總是小于(或者大于)它的父節(jié)點。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法:
大頂堆:每個節(jié)點的值都大于或等于其子節(jié)點的值,在堆排序算法中用于升序排列;小頂堆:每個節(jié)點的值都小于或等于其子節(jié)點的值,在堆排序算法中用于降序排列;堆排序的平均時間復(fù)雜度為 Ο(nlogn)。
1. 算法步驟創(chuàng)建一個堆 H[0……n-1];
把堆首(最大值)和堆尾互換;
把堆的尺寸縮小 1,并調(diào)用 shift_down(0),目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置;
重復(fù)步驟 2,直到堆的尺寸為 1。
2. 動圖演示代碼實現(xiàn)JavaScript 實例 var len; ? ?// 因為聲明的多個函數(shù)都需要數(shù)據(jù)長度,所以把len設(shè)置成為全局變量function buildMaxHeap(arr) { ? // 建立大頂堆? ? len = arr.length;? ? for (var i = Math.floor(len/2); i >= 0; i--) {? ? ? ? heapify(arr, i);? ? }}function heapify(arr, i) { ? ? // 堆調(diào)整? ? var left = 2 * i + 1,? ? ? ? right = 2 * i + 2,? ? ? ? largest = i;? ? if (left < len && arr[left] > arr[largest]) {? ? ? ? largest = left;? ? }? ? if (right < len && arr[right] > arr[largest]) {? ? ? ? largest = right;? ? }? ? if (largest != i) {? ? ? ? swap(arr, i, largest);? ? ? ? heapify(arr, largest);? ? }}function swap(arr, i, j) {? ? var temp = arr[i];? ? arr[i] = arr[j];? ? arr[j] = temp;}function heapSort(arr) {? ? buildMaxHeap(arr);? ? for (var i = arr.length-1; i > 0; i--) {? ? ? ? swap(arr, 0, i);? ? ? ? len--;? ? ? ? heapify(arr, 0);? ? }? ? return arr;}Python實例 def buildMaxHeap(arr):? ? import math? ? for i in range(math.floor(len(arr)/2),-1,-1):? ? ? ? heapify(arr,i)def heapify(arr, i):? ? left = 2*i+1? ? right = 2*i+2? ? largest = i? ? if left < arrLen and arr[left] > arr[largest]:? ? ? ? largest = left? ? if right < arrLen and arr[right] > arr[largest]:? ? ? ? largest = right? ? if largest != i:? ? ? ? swap(arr, i, largest)? ? ? ? heapify(arr, largest)def swap(arr, i, j):? ? arr[i], arr[j] = arr[j], arr[i]def heapSort(arr):? ? global arrLen? ? arrLen = len(arr)? ? buildMaxHeap(arr)? ? for i in range(len(arr)-1,0,-1):? ? ? ? swap(arr,0,i)? ? ? ? arrLen -=1? ? ? ? heapify(arr, 0)? ? return arrGo實例 func heapSort(arr []int) []int {? ? ? ? arrLen := len(arr)? ? ? ? buildMaxHeap(arr, arrLen)? ? ? ? for i := arrLen - 1; i >= 0; i-- {? ? ? ? ? ? ? ? swap(arr, 0, i)? ? ? ? ? ? ? ? arrLen -= 1? ? ? ? ? ? ? ? heapify(arr, 0, arrLen)? ? ? ? }? ? ? ? return arr}func buildMaxHeap(arr []int, arrLen int) {? ? ? ? for i := arrLen / 2; i >= 0; i-- {? ? ? ? ? ? ? ? heapify(arr, i, arrLen)? ? ? ? }}func heapify(arr []int, i, arrLen int) {? ? ? ? left := 2*i + 1? ? ? ? right := 2*i + 2? ? ? ? largest := i? ? ? ? if left < arrLen && arr[left] > arr[largest] {? ? ? ? ? ? ? ? largest = left? ? ? ? }? ? ? ? if right < arrLen && arr[right] > arr[largest] {? ? ? ? ? ? ? ? largest = right? ? ? ? }? ? ? ? if largest != i {? ? ? ? ? ? ? ? swap(arr, i, largest)? ? ? ? ? ? ? ? heapify(arr, largest, arrLen)? ? ? ? }}func swap(arr []int, i, j int) {? ? ? ? arr[i], arr[j] = arr[j], arr[i]}Java實例 public class HeapSort implements IArraySort {? ? @Override? ? public int[] sort(int[] sourceArray) throws Exception {? ? ? ? // 對 arr 進行拷貝,不改變參數(shù)內(nèi)容? ? ? ? int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);? ? ? ? int len = arr.length;? ? ? ? buildMaxHeap(arr, len);? ? ? ? for (int i = len - 1; i > 0; i--) {? ? ? ? ? ? swap(arr, 0, i);? ? ? ? ? ? len--;? ? ? ? ? ? heapify(arr, 0, len);? ? ? ? }? ? ? ? return arr;? ? }? ? private void buildMaxHeap(int[] arr, int len) {? ? ? ? for (int i = (int) Math.floor(len / 2); i >= 0; i--) {? ? ? ? ? ? heapify(arr, i, len);? ? ? ? }? ? }? ? private void heapify(int[] arr, int i, int len) {? ? ? ? int left = 2 * i + 1;? ? ? ? int right = 2 * i + 2;? ? ? ? int largest = i;? ? ? ? if (left < len && arr[left] > arr[largest]) {? ? ? ? ? ? largest = left;? ? ? ? }? ? ? ? if (right < len && arr[right] > arr[largest]) {? ? ? ? ? ? largest = right;? ? ? ? }? ? ? ? if (largest != i) {? ? ? ? ? ? swap(arr, i, largest);? ? ? ? ? ? heapify(arr, largest, len);? ? ? ? }? ? }? ? private void swap(int[] arr, int i, int j) {? ? ? ? int temp = arr[i];? ? ? ? arr[i] = arr[j];? ? ? ? arr[j] = temp;? ? }}PHP 實例 function buildMaxHeap(&$arr){? ? global $len;? ? for ($i = floor($len/2); $i >= 0; $i--) {? ? ? ? heapify($arr, $i);? ? }}function heapify(&$arr, $i){? ? global $len;? ? $left = 2 * $i + 1;? ? $right = 2 * $i + 2;? ? $largest = $i;? ? if ($left < $len && $arr[$left] > $arr[$largest]) {? ? ? ? $largest = $left;? ? }? ? if ($right < $len && $arr[$right] > $arr[$largest]) {? ? ? ? $largest = $right;? ? }? ? if ($largest != $i) {? ? ? ? swap($arr, $i, $largest);? ? ? ? heapify($arr, $largest);? ? }}function swap(&$arr, $i, $j){? ? $temp = $arr[$i];? ? $arr[$i] = $arr[$j];? ? $arr[$j] = $temp;}function heapSort($arr) {? ? global $len;? ? $len = count($arr);? ? buildMaxHeap($arr);? ? for ($i = count($arr) - 1; $i > 0; $i--) {? ? ? ? swap($arr, 0, $i);? ? ? ? $len--;? ? ? ? heapify($arr, 0);? ? }? ? return $arr;}C實例 #include參考文章:
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/7.heapSort.md
https://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F
以下是熱心網(wǎng)友對堆排序算法的補充,僅供參考:
熱心網(wǎng)友提供的補充1:
上方又沒些 C# 的堆排序,艾孜爾江補充如下:
////// 堆排序 /// /// 待排序數(shù)組 static void HeapSort(int[] arr) { int vCount = arr.Length; int[] tempKey = new int[vCount + 1]; // 元素索引從1開始 for (int i = 0; i < vCount; i++) { tempKey[i + 1] = arr[i]; } // 初始數(shù)據(jù)建堆(從含最后一個結(jié)點的子樹開始構(gòu)建,依次向前,形成整個二叉堆) for (int i = vCount / 2; i >= 1; i--) { Restore(tempKey, i, vCount); } // 不斷輸出堆頂元素、重構(gòu)堆,進行排序 for (int i = vCount; i > 1; i--) { int temp = tempKey[i]; tempKey[i] = tempKey[1]; tempKey[1] = temp; Restore(tempKey, 1, i - 1); } //排序結(jié)果 for (int i = 0; i < vCount; i++) { arr[i] = tempKey[i + 1]; } } ////// 二叉堆的重構(gòu)(針對于已構(gòu)建好的二叉堆首尾互換之后的重構(gòu)) /// /// /// 根結(jié)點j /// 結(jié)點數(shù) static void Restore(int[] arr, int rootNode, int nodeCount) { while (rootNode <= nodeCount / 2) // 保證根結(jié)點有子樹 { //找出左右兒子的最大值 int m = (2 * rootNode + 1 <= nodeCount && arr[2 * rootNode + 1] > arr[2 * rootNode]) ? 2 * rootNode + 1 : 2 * rootNode; if (arr[m] > arr[rootNode]) { int temp = arr[m]; arr[m] = arr[rootNode]; arr[rootNode] = temp; rootNode = m; } else { break; } } }
熱心網(wǎng)友提供的補充2:
堆排序是不穩(wěn)定的排序!
既然如此,每次構(gòu)建大頂堆時,在 父節(jié)點、左子節(jié)點、右子節(jié)點取三者中最大者作為父節(jié)點就行。我們追尋的只是最終排序后的結(jié)果,所以可以簡化其中的步驟。
我將個人寫的 Java 代碼核心放在下方,有興趣的同學(xué)可以一起討論下:
public int[] sort(int a[]) { int len = a.length - 1; for (int i = len; i > 0; i--) { maxHeap(a, i); //交換 跟節(jié)點root 與 最后一個子節(jié)點i 的位置 swap(a, 0, i); //i--無序數(shù)組尺寸減少了 } return a; } /**構(gòu)建一個大頂堆(完全二叉樹 ) * 從 最后一個非葉子節(jié)點 開始,若父節(jié)點小于子節(jié)點,則互換他們兩的位置。然后依次從右至左,從下到上進行! * 最后一個非葉子節(jié)點,它的葉子節(jié)點 必定包括了最后一個(葉子)節(jié)點,所以 最后一個非葉子節(jié)點是 a[(n+1)/2-1] * @param a * @param lastIndex 這個數(shù)組的最后一個元素 */ static void maxHeap(int a[], int lastIndex) { for (int i = (lastIndex + 1) / 2 - 1; i >= 0; i--) { //反正 堆排序不穩(wěn)定,先比較父與左子,大則交換;與右子同理。(不care 左子與右子位置是否變了!) if (i * 2 + 1 <= lastIndex && a[i] < a[i * 2 + 1]) { swap(a, i, i * 2 + 1); } if (i * 2 + 2 <= lastIndex && a[i] < a[i * 2 + 2]) { swap(a, i, i * 2 + 2); } } } private void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }以上為堆排序算法詳細介紹,插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等排序算法各有優(yōu)缺點,用一張圖概括:
關(guān)于時間復(fù)雜度
平方階 (O(n2)) 排序 各類簡單排序:直接插入、直接選擇和冒泡排序。
線性對數(shù)階 (O(nlog2n)) 排序 快速排序、堆排序和歸并排序;
O(n1+§)) 排序,§ 是介于 0 和 1 之間的常數(shù)。 希爾排序
線性階 (O(n)) 排序 基數(shù)排序,此外還有桶、箱排序。
關(guān)于穩(wěn)定性
穩(wěn)定的排序算法:冒泡排序、插入排序、歸并排序和基數(shù)排序。
不是穩(wěn)定的排序算法:選擇排序、快速排序、希爾排序、堆排序。
名詞解釋:
n:數(shù)據(jù)規(guī)模
k:"桶"的個數(shù)
In-place:占用常數(shù)內(nèi)存,不占用額外內(nèi)存
Out-place:占用額外內(nèi)存
穩(wěn)定性:排序后 2 個相等鍵值的順序和排序之前它們的順序相同