算法思路：所谓的堆排序是利用完全二叉树的思想实现的。首先应该提到的是最大堆，在最大堆中（完全二叉树二叉树）中每个父节点都大于等于两个儿子节点的值，这时候很明 显堆顶是元素的最大值，然后把堆顶元素和堆中最后一个元素（分层遍历的节点编号最大的元素）交换，这样最大值就落到了数组的arr[n-1]的位置，然后把前n-1元素继续按照上面的方式处理，如此进行n-1次就完成堆排序。
算法代码：
#include <iostream> using namespace std; void swap(int &x,int &y) { x = x + y; y = x - y; x = x - y; } void restore(int *arr,int s,int e) { int i = s , m; while(i <= e/2) { if(2*i+1 <= e && arr[2*i] > arr[2*i-1]) { m = 2 * i + 1; } else { m = 2 * i; } if(arr[i-1] < arr[m-1]) { swap(arr[i-1],arr[m-1]); i = m; } else { i = e; } } } void heap_sort(int *arr,int n) { int i; for(i = n / 2 ; i > 0 ; --i) { restore(arr,i,n); } for(i = n ; i > 1 ; --i) { swap(arr[0],arr[i-1]); restore(arr,1,i-1); } } int main() { int arr[] = {2,1,4,3,8,7,5,6}; heap_sort(arr, 8); for(int i = 0 ; i < 8 ; ++i) { cout<<arr[i]<<" "; } cout<<endl; return 0; }
小结：堆排序是不稳定的排序，但是堆排序属于原地排序。时间复杂度是O(n*log n)，并且不需要额外的辅助空间，也就是说堆排序是一种不错的排序算法哦~~~
