堆排序

#include<iostream.h> /*************************************************************************************** 算法说明：按照数据结构上的讲解，该算法是将heap从start位置开始进行调整，直到end位置 ****************************************************************************************/ void swap( int &a, int &b ) { int temp = a; a = b; b = temp; } void AdjustHeap( int *heap, int start, int end ) { int childPos = 0; int key = heap[start]; //从第一个孩子开始不停的进行调整。 //因为child做了一次乘法，所以务必注意，数组中的第一个元素位置不能设为0， //那样在进行堆顶元素调整的时候就没办法调整了 for( childPos = start*2; childPos < end; childPos *= 2 ) { /********************************************************************/ /*这个条件最难确定,注意建立的是大顶堆，即堆顶元素为最大元素。 /*对上面的for循环去掉=，之后就好确定了，要注意，到最后一个元素的时候就不在比较了 /********************************************************************/ if( /*childPos < end&&*/heap[childPos] < heap[childPos+1] ) ++childPos; if( key > heap[childPos] ) break; /*换做swap函数之后也一样可以*/ swap( heap[start], heap[childPos] ); //heap[start] = heap[childPos]; //还要记录下目前start的位置，childPos要改变！ start = childPos; } //heap[start] = key; } void HeapSort( int *heap, int num ) { //调整堆 for( int i = num/2; i > 0; --i ) AdjustHeap( heap, i, num ); for( i = num; i > 1; --i) { swap( heap[1],heap[i] ); AdjustHeap( heap, 1, i-1 ); } } int main() { int heap[] = { 0,21,12,43,521,321,345,54,13,46,645,87,33,77,22}; int num = sizeof(heap)/sizeof(int) - 1 ; cout << "before sort:" << endl; for( int i = 0; i < num; i++ ) { cout << heap[i] << endl; } HeapSort( heap,num ); cout << "after sort:" << endl; for( i = 0; i < num; i++ ) { cout << heap[i] << endl; } }