堆排序Heap_Sort

2019-11-14 12:47:10

字體：大中小

來源：轉載

供稿：網友

#include<iostream>using namespace std;int Parent(int i){return i/2;}int Left(int i){return 2*i;}int Right(int i){return 2*i+1;}void exchange(int *a,int *b){int t=*a;*a=*b;*b=t;}void max_heapify(int *a,int i,int heap_size){int l=Left(i);int r=Right(i);int largest;if(l<=heap_size&&a[l]>a[i])largest=l;elselargest=i;if(r<=heap_size&&a[r]>a[largest])largest=r;if(largest!=i){ exchange(&a[largest],&a[i]); max_heapify(a,largest,heap_size);}}void Build_max_heap(int *a,int length){int heap_size=length;for(int i=length/2;i>0;--i) max_heapify(a,i,heap_size);}void output(int *a,int size){for(int i=0;i<size;++i)cout<<a[i]<<" ";cout<<endl;}void Heap_Sort(int *a,int size){Build_max_heap(a,size);for(int i=size;i>1;--i) { exchange(&a[i],&a[1]); --size; max_heapify(a,1,size); }}int main(){int a[11]={2222,4,1,3,2,16,9,10,14,8,7};//第一個位置不參加排序，為了方便在parent和Left 和Rightt函數時調用時返回正確的左孩子右孩子和父親，排序時參加建堆的元素的坐標是從1開始的，才能返回正確的父親和孩子。這個是在堆排序時最容易出錯的地方。（話說我堆排序自己寫了三次這兒錯了三次>__<）Build_max_heap(a,10);output(a+1,10);Heap_Sort(a,10);output(a+1,10);return 0;

}

時間復雜度：

堆排序的時間復雜度是O（n lg（n））；

max_heapify（）函數的時間復雜度是O（n lgn）；

建最大堆（Build_max_heap()）的時間復雜度度為O（n）；

排序過程要調用n次Build_max_heap（）函數所以堆排序的時間復雜度是O（n lgn）；

以上堆排序的時間復雜度的詳細推導過程參考《算法導論》第三版P85.

上一篇：關于C++抽象類建立對象的問題

下一篇：堆排序Heap_Sort