堆排序Heap_Sort

2019-11-14 12:47:13

字體：大中小

供稿：網(wǎng)友

#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};//第一個(gè)位置不參加排序，為了方便在parent和Left 和Rightt函數(shù)時(shí)調(diào)用時(shí)返回正確的左孩子右孩子和父親，排序時(shí)參加建堆的元素的坐標(biāo)是從1開(kāi)始的，才能返回正確的父親和孩子。這個(gè)是在堆排序時(shí)最容易出錯(cuò)的地方。（話(huà)說(shuō)我堆排序自己寫(xiě)了三次這兒錯(cuò)了三次>__<）Build_max_heap(a,10);output(a+1,10);Heap_Sort(a,10);output(a+1,10);return 0;

}

時(shí)間復(fù)雜度：

堆排序的時(shí)間復(fù)雜度是O（n lg（n））；

max_heapify（）函數(shù)的時(shí)間復(fù)雜度是O（n lgn）；

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

排序過(guò)程要調(diào)用n次Build_max_heap（）函數(shù)所以堆排序的時(shí)間復(fù)雜度是O（n lgn）；

以上堆排序的時(shí)間復(fù)雜度的詳細(xì)推導(dǎo)過(guò)程參考《算法導(dǎo)論》第三版P85.

上一篇：堆排序Heap_Sort

下一篇：PAT B1041. 考試座位號(hào)(15)