堆排序的逻辑非常简单,但是效率较高,代码如下:
#include <iostream> #include <vector> class heap { public: heap(int* array, size_t len):arr (array), length(len){ size_t point = (length -1)/2; for(size_t i = 0; i != point; ++i){ adjust(point-i, length); } } void sort(){ int tmp; for(size_t i = 0; i != length; ++i){ tmp = arr[0]; arr[0] = arr [length-1-i]; arr[length -1-i] = tmp; adjust(0, length-1-i); } } ~heap(){} private: void adjust( size_t pos, size_t len){ size_t next; for(int tmp = arr[pos]; 2*pos+1 < len; pos = next){ next = 2*pos+1; if(next < len-1 && arr [next] < arr[next+1]){ ++next; } if(tmp < arr [next]){ arr[pos] = arr [next]; arr[next] = tmp; } } } private: int* arr ; size_t length ; }; int main(){ int array[10] = {9, 5, 7, 4, 8, 1, 3, 4, 6, 5}; heap h(array, 10); h.sort(); for(size_t i = 0; i != 10; ++i){ std::cout << array[i] << " "; } std::cout << std:: endl; return 0; }
本文链接:http://blog.csdn.net/girlkoo/article/details/17606521
本文作者:girlkoo