堆排序Heap_Sort

2019-11-14 12:18:12

字体：大中小

来源：转载

供稿：网友

#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.

上一篇：Visual Studio常用快捷键

下一篇：Atom的使用与solidity packages的安装配置