1. 簡介
堆排序是建立在堆這種數據結構基礎上的選擇排序，是原址排序，時間復雜度O(nlogn)，堆排序并不是一種穩定的排序方式。堆排序中通常使用的堆為最大堆。
2. 堆的定義
堆是一種數據結構，是一顆特殊的完全二叉樹，通常分為最大堆和最小堆。最大堆的定義為根結點最大，且根結點左右子樹都是最大堆；同樣，最小堆的定義為根結點最小，且根結點左右子樹均為最小堆。
最大堆滿足其每一個父結點均大于其左右子結點，最小堆則滿足其每一個父結點均小于其左右子結點。
3. 堆排序
3.1 堆的存放
在堆排序中，堆所表示的二叉樹并不需要使用指針的方式在計算機中存放，只需要使用數組即可，將樹的結點，從上至下，從左至右一個個放到數組中去。
因此，如果數組的起始索引為0，對于一個結點i來說，它的父結點索引為⌊i/2⌋，它的左子結點索引為2i+1，右子結點索引為2i+2。最后一個非葉子節點就是最后一個結點的父親，如果數組長度為n，那么其索引為⌊(n-1)/2⌋。
3.2 堆排序主要步驟
將無序序列構建成最大堆
將數組分成兩個區域，有序區和無序區，初始時創建一個整數i為數組的長度，用來劃分有序區和無序區，有序區初始為空。
將堆頂元素和最后一個無序區的元素交換，然后i-1。
調整使得所有無序區的元素重新為最大堆。
重復3，4步，直到 i = 0
3.3 堆的調整
假設有某棵完全二叉樹，其左右子樹均為最大堆，如何調整使得該二叉樹成為最大堆呢？如果根結點大于左右子結點，那么已經是最大堆了，無需調整。否則，交換根結點和左右子結點中較大的那個。假設交換的是左結點，那么目前這棵完全二叉樹右子樹仍然是一個最大堆，左子樹則不一定，但是左子樹的左右子樹還是最大堆，因此不斷遞歸下去調整即可。
因此，交換最后一個元素和堆頂元素后的調整步驟，就和上面所說的一致。而將無序序列構建成最大堆，同樣也可以運用這一點。從最后一個非葉子結點到第一個非葉子結點（根結點），對這些結點作為根結點的子樹，按順序調用一次上述描述的調整即可（每次調用時，該子樹的左右子樹必定是最大堆）。
4. 算法實現
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include <stdio.h>void swap(int *a,int *b) { int temp = *a; *a = *b; *b = temp;}//左右子樹都是最大堆，從上至下調整使得最大堆, root_index是要調整的樹的根節點，length是無序區的長度void adjust(int array[],int root_index,int length) { int left_child = root_index*2+1; int right_child = left_child+1; int left_or_right = 0; if((left_child >= length && right_child >= length) || (left_child >= length && array[root_index] >= array[right_child]) || (right_child >= length && array[root_index] >= array[left_child]) || (array[root_index] >= array[left_child] && array[root_index] >= array[right_child])){ return; } else if (array[left_child] >= array[root_index] && (right_child >= length || array[left_child] >= array[right_child])) { left_or_right = 1; } else if (array[right_child] >= array[root_index] && (left_child >= length || array[right_child] >= array[left_child])) { left_or_right = 0; } if(left_or_right) { swap(&array[left_child],&array[root_index]); adjust(array,left_child,length); } else { swap(&array[right_child],&array[root_index]); adjust(array,right_child,length); }}//heapsort主遞歸，每一次將無序區最后一個元素與堆頂元素交換，將堆頂元素加入有序區，因此有序區加1,無序區減1，無序區只剩一個元素的時候遞歸終止void heapsort_main(int array[],int length,int last_index) { int i; if(last_index == 0) return; swap(&array[0],&array[last_index]); adjust(array,0,last_index); heapsort_main(array,length,last_index-1);} //入口函數，array是待排序的數組，length是其長度void heapsort(int array[],int length) { int i; for(i = length/2-1;i >= 0;i--) { adjust(array,i,length); } heapsort_main(array,length,length-1);}int main(int argc,char *argv[]) { int array[9] = {1,1,1,2,3,5,2,3,5}; heapsort(array,9); int i; for(i = 0;i < 9;i++) { printf("%d ",array[i]); }} |
5.堆排序性質
時間復雜度O(nlogn)
空間復雜度O(1)
不穩定排序
本篇文章對堆排序所整理的內容，希望可以幫到需要的朋友
原文鏈接：http://blog.csdn.net/qq_20448859/article/details/69951382
