合并排序具有较好的运行时间复杂度O(nlogn)，但却需要额外的O(n)的空间；插入排序不需要开辟新的空间，但其时间开销却维持在O(n^2)。这两种算法各有所长，但都不尽如人意，综合看来：不是用时间买空间，就是用空间换时间。有没有这样一种集众家所长的算法？既保持一个较好的时间复杂度，又不必开辟额外的空间。堆排序无疑是不二选择。

以下即是用模版实现的堆排序的算法。

 

#include<iostream>
usingnamespace std;#define MAX_HEAP_SIZE 100//////////////////////////////////////////////////////////////////////////
// 使用大顶堆进行堆排序template<class T>
struct MaxHeap
{int size;T data[MAX_HEAP_SIZE+1];MaxHeap(){size = 0;}
};template<class T>
void MaxHeapify(MaxHeap<T> &maxHeap,int k)
{int left, right, largest;while(k <= maxHeap.size/2){largest = k;left = k*2;right = k*2+1;if (left<=maxHeap.size && maxHeap.data[left]>maxHeap.data[largest])largest = left;if (right<=maxHeap.size && maxHeap.data[right]>maxHeap.data[largest])largest = right;if (largest !=k ){T temp = maxHeap.data[largest];maxHeap.data[largest] = maxHeap.data[k];maxHeap.data[k] = temp;k = largest;}elsebreak;}}template<class T>
MaxHeap<T> BuildHeap(T* arr, int len)
{MaxHeap<T> heap;heap.size = len;if (len > MAX_HEAP_SIZE){cout << "space is not enough" << endl;exit(0);}memcpy(&heap.data[1], arr,sizeof(T)*len);for (int i= len/2; i>0; --i){MaxHeapify(heap, i);}return heap;
}template<class T>
void HeapSort(T* arr,int len)
{MaxHeap<T> heap = BuildHeap(arr, len);for (int i=len; i>1; --i){T temp = heap.data[1];heap.data[1] = heap.data[i];heap.data[i] = temp;heap.size --;MaxHeapify(heap, 1);}memcpy(arr, &heap.data[1],sizeof(T)*len);
}template <class T>
void print(T* arr,int len)
{for (int i=0; i<len; ++i)cout << arr[i] <<" ";cout << endl;
}// 测试部分
template <class T>
void print(T* arr,int len)
{for (int i=0; i<len; ++i)cout << arr[i] <<" ";cout << endl;
}int main()
{int ai[] = {3, 2, 7, 8, 5, 1, 3};HeapSort(ai,7);print(ai, 7);double ad[] = {1.2, 3.5, 4.2, 1.3, 0.7, 6.2, 0.1};HeapSort(ad, 7);print(ad, 7);return 0;
}