August 24, 2010
heap sort
heap sort, 参考wikipedia
void sift_down(int *a, int start,int end){
int i=start;
while(i*2+1<=end) {
int child=i*2+1;
if (child<end && a[child]<a[child+1])
child++;
if (a[i]<a[child]){
std::swap(a[i],a[child]);
i=child;
}
else return;
}
}
void heapify(int *a,int n){
for (int i=(n-2)/2;i>=0;i--) {
sift_down(a,i,n-1);
}
}
void heap_sort(int *a, int n){
heapify(a,n);
for (int i=n-1;i>0;i--) {
std::swap(a[0],a[i]);
sift_down(a,0,i-1);
}
}
Comments(0)
