堆排序

       堆的基本操作参考文章：[堆的基本操作](http://blog.csdn.net/u013074465/article/details/46741421)        对于小根堆来说，一般的思路是每次删除最小值，执行N次删除；每次将删除的元素拷贝到一个新的数组，那么新数组将按照从小到大的顺序排列。这里的主要问题是空间的：使用新数组，使存储空间增加了一倍。        一个技巧是：每次删除一个堆元素，堆大小会减少1。那么位于堆最后的那个空间可以用来存放刚刚被删除的元素。按照这种思路，不用额外的空间即可完成排序。       对小根堆，该方式排序完的数组是递减的，那么，如果我们建立堆时用大根堆，则该方式得到的排序结果是递增的。       堆排序中用到了下滤操作，因为堆排序其实就是堆删除的一系列操作，而堆的删除操作会下滤，参考[二叉堆的插入删除等操作C++实现](http://blog.csdn.net/u013074465/article/details/42028473)       在移动堆元素的时候（AdjustHeap函数中），用到了一个技巧来减少交换元素的次数，参考[插入排序和希尔排序](http://blog.csdn.net/u013074465/article/details/42043665)，这里不再赘述。 ~~~ /* （大根）堆排序，花费O(NlogN)。 */ template<typename T> void HeapSort(vector<T>& a) { int i; //先建立大根堆，该操作花费O(N) for (i = a.size() / 2; i >= 0; --i) { AdjustHeap(a, i, a.size()); } //将要删除的元素放入堆末尾的空间（交换根元素和尾元素）， //这样不需要额外的空间。 for (i = a.size() - 1; i > 0; --i) { T tmp = a[i]; a[i] = a[0]; a[0] = tmp; /* 每次删除时，根元素与根末尾元素交换了，在位置0处下滤。 由于不断从堆中删除，因此堆大小不断减小，为i */ AdjustHeap(a, 0, i); } } //该函数是堆操作中的下滤操作 template<typename T> void AdjustHeap(vector<T>&a, int pos, int n) { int pos_child; T tmp; for (tmp = a[pos]; (pos * 2 + 1) < n; pos = pos_child) { pos_child = 2 * pos + 1; if (pos_child != n -1 && a[pos_child] < a[pos_child + 1]) pos_child++; if (tmp < a[pos_child]) a[pos] = a[pos_child]; else break; } a[pos] = tmp; } //只是一个打印元素的函数 template<typename T> void PrintValue(vector<T>& a) {  vector<T>::iterator iter = a.begin();  while (iter != a.end()) {      cout << *iter++ << " ";  }  cout << endl; } int main() {  int value;  vector<int> ivec;  while (cin >> value)      ivec.push_back(value);  HeapSort<int>(ivec);  PrintValue(ivec); } ~~~