1.堆排序
堆排序是用堆這種資料結構所設計的一種排序演算法，近似一顆完成二叉樹，同時具有一個特性，父節點的值大于（小于）子節點的值，
堆分兩種，父節點比子節點大的叫最大堆，父節點比子節點小的叫最小堆
下面就是一個最大堆
2.堆排序步驟
以最大堆為例，假設有n個元素,
1)構造最大堆
2）交換根節點與第n個節點的值
3）將當前的堆調整為最大堆
4）n減一，繼續2）3）步驟，直到n==1
3.如何構造最大堆
由最大堆的性質可知，每個父節點的值都比子節點的值大，所以要從下往上調整，調整后根節點就是最大的，舉個例子
假設陣列array : 
1）先把它想象成下面的形式（完全二叉樹），在陣列中還是按順序排序的，
2）開始構造最大堆
1.先找到最后一個父節點，由于最大堆的形式是上面的形式，所以很容易得到最后一個父節點的下標，上面的元素是8個
那么最后父節點的下標：i=8/2-1=3,而且該節點的左子節點的下標是：2i+1,右子節點下標是:2i+2 這是很重要的性質，
比較i和2i+1,2i+2的對應值，如果這兩個子節點比父節點大，那么就交換父子節點的值，要注意要判斷2i+1和2i+2存不存在（即下標不能越界）
第一次調整后:
第二次：
第三次
第四次
這時，要注意交換后可能導致后面的節點不滿足最大堆的性質，此時繼續按照上面的步驟來,其實就是一個遞回，等下看代碼就好理解了
第五次，調整完成
開始交換
3）交換根節點與第 n-i（i是已經交換的元素個數）個元素的值
4）然后把它調整成一個最大堆，此時要從上往下調整，即從根節點開始調整，
5) 繼續 3）,4)步驟，直到n-i==1,此時排序完成
結合代碼過一遍就很容易懂了
代碼如下：
1 #include<stdio.h> 2 //交換兩個數的值 3 void swap(int *a,int * b) 4 { 5 int temp=*a; 6 *a=*b; 7 *b=temp; 8 } 9 //構造最大堆程序 10 void maxHead(int *arr,int start,int end) 11 { 12 int parentNode=start;//父節點 13 int childNode=parentNode*2+1;//左子節點 14 while(childNode<=end) 15 { 16 //childNode+1是右子節點 17 if(childNode+1<=end&&arr[childNode+1]>arr[childNode]) 18 childNode++;//右子節點大，取右子節點 19 //父節點比子節點大，不用交換，直接回傳 20 if(arr[parentNode]>arr[childNode]) 21 return; 22 //否則，交換父節點與子節點的值 23 else 24 { 25 swap(&arr[parentNode],&arr[childNode]); 26 27 //交換后有可能導致后面的節點 28 //不滿足最大堆的要求，所以繼續對后面的節點進行構造 29 parentNode=childNode; 30 childNode=parentNode*2+1; 31 } 32 } 33 34 } 35 void headSort(int * arr,int num) 36 { 37 //num陣列元素個數 38 int i; 39 //一開始先構造一個最大堆 40 for(i=num/2-1;i>=0;i--) 41 maxHead(arr,i,num-1); 42 43 for(i=num-1;i>0;i--) 44 { 45 swap(&arr[i],&arr[0]);//交換第一個元素與第i(i從后面開始)個元素 46 maxHead(arr,0,i-1);//交換后繼續進行構造最大堆操作 47 } 48 } 49 int main() 50 { 51 int i; 52 int arr[8]={1,5,0,6,3,9,8,7}; 53 headSort(arr,8);//堆排序 54 for(i=0;i<8;i++) 55 printf("%d\n",arr[i]); 56 return 0; 57 }
堆排序的平均時間復雜度是：O(nlogn)
有問題，隨時聯系
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/40829.html
標籤：C
上一篇：C 實戰練習題目2