首页 > 代码库 > 堆排序-c++
堆排序-c++
1 /************************************************************************* 2 > File Name: HeapSort.cpp 3 > Author: zhoukang 4 > Mail: zhoukang199191@126.com 5 > Created Time: 2014年08月11日 星期一 22时36分38秒 6 ************************************************************************/ 7 8 #include <iostream> 9 #include <vector>10 #include <algorithm>11 using namespace std;12 13 void max_heapfy(vector<int> & A,int index,int heapsize)14 {15 int l = 2*index+1;16 int r = 2*index+2;17 18 int largest = index;19 if(l <= heapsize && A[l] > A[index])20 largest = l;21 if(r <= heapsize && A[r] > A[largest])22 largest = r;23 if(largest != index)24 {25 swap(A[index],A[largest]);26 max_heapfy(A,largest,heapsize);27 }28 }29 30 void build_max_heap(vector<int> &A,int heapsize)31 {32 // assert(heapsize >= 0);33 int i;34 for(i = heapsize/2-1 ; i >= 0 ; --i)35 max_heapfy(A,i,heapsize);36 }37 38 void heap_sort(vector<int> &A,int heapsize)39 {40 build_max_heap(A,heapsize);41 int i;42 for(i = heapsize-1; i > 0 ; --i )43 {44 swap(A[0],A[i]);45 max_heapfy(A,0,i);46 }47 }48 49 int main()50 {51 cout<<"before"<<endl;52 vector<int> A;53 A.push_back(3);54 A.push_back(1);55 A.push_back(2);56 heap_sort(A,3);57 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。