堆排序時間復雜度：O(NlogN).二叉堆：是完全二叉樹。將其結點存入數組的話，任意一非葉結點位置存在以下的兩種關系
1、k[i]<=k[2*i+1] && k[i]<=k[2*i+2] （小頂堆） 小頂堆堆頂關鍵字肯定是所有關鍵字中最小的
2、k[i]>=k[2*i+1] && k[i]>=k[2*i+2] （大頂堆） 大頂堆堆頂關鍵字肯定是所有關鍵字中最大的

　　堆排序的思想：
1、將初始待排序關鍵字序列（x1,x2,x3,...,Xn）構成大頂堆，此堆為初始的無序區；
2、將堆頂元素x1與最后一個元素xn交換，此時得到新的無序區（x1,x2,x3,..,Xn-1）和新的有序區（Xn） 且 Xn最大
3、由于交換后新的堆頂元素可能違反堆的性質，因此需要對當前無序區重新調整為堆，然后依次再將x1與Xn-1交換，如此重復直到有序區的個數為n-1。

1 ?#include<iostream>

?2 ?#include<algorithm>

?3 ?using namespace std;

?4 ?//調整堆 a[]={16,7,3,20,17,8}

?5 ?//上溯算法，將新的結點與父結點比較，如果其鍵值大于父結點，交換位置。如此一直上溯，直到不需要對換或到根結點為止

?6 ?void HeapAdjust(int *a,int i,int size)

?7 ?{

?8 ???????? int lchild=2*i+1;

?9 ???????? int rchild=2*i+2;

10 ???????? int max=i;

11 ???????? if(lchild<=size-1&&a[lchild]>a[max])

12 ???????? max=lchild;

13 ???????? if(rchild<=size-1&&a[rchild]>a[max])

14 ???????? max=rchild;

15 ???????? If(max!=i)

16 ??{

17 ??swap(a[i],a[max]);

18 ??HeapAdjust(a,max,size); //避免調整之后以max為父節點的子樹不是堆

19 ??}

20

21 ?}

22 ?//建立堆

23 ?void BuildHeap(int *a,int size)

24 ?{

25

26 ???????? int i;

27????????? for(i=size/2-1;i>=0;i--)

28 ?{

29 ? HeapAdjust(a,i,size);

30

31 ?}

32

33 ?}

34

35

36 ? void HeapSort(int *a,int size)

37 ? {

38?? ????? int i;

39 ???????? BuildHeap(a,size);

40?? for(i=size-1;i>=0;i--)

41 ?{

42 ???????? swap(a[0],a[i]);

43 ???????? HeapAdjust(a,0,i);

44 ?}

45 ?}

?　　堆排序是不穩定的排序算法，穩定的排序算法通俗地講就是能保證排序前2個相等的數其在序列的前后位置順序和排序后它們兩個的前后位置順序相同。在簡單形式化一下，如果Ai = Aj，Ai原來在位置前，排序后Ai還是要在Aj位置前，平均時間復雜度和最差時間復雜度都是O(NlogN)，空間復雜度為O(1)

轉載于:https://www.cnblogs.com/wsw-seu/p/7654753.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的排序之堆排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。