heapsort

堆，我们可以把它看做是一个完全二叉树（本质不是完全二叉树），一般分为大顶堆和小顶堆。在堆排序中大顶堆用于从小到大的排列，小顶堆用于从大到小的排列。堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

大致的步骤：

堆排序每次从最后一个非叶子节点开始，比较根与两个孩子的大小关系（如果是小顶堆的话，根要比孩子节点小；如果是大顶堆的话根要比孩子节点大），逐个节点比较最后整棵树的根一定就是值最大（最小）的那个点。之后把它和二叉树的最后一个节点作交换。并脱离二叉树。之后把之前的步骤反复进行直到二叉树只剩一个节点。

树那数组存储的话求最后一个非叶子节点有一个公式：i = arr.length()/2-1。

把上面说的堆排序的步骤抽象成模型就是：构造堆，交换，构造堆，。。。

因此算法函数分为两部分，构造堆函数和交换函数。

交换函数很好解决，就是一个swap

1 void Swap(vector<int> &arr,int index){
2     int temp = arr[0];
3     arr[0] = arr[index];
4     arr[index] = temp;
5 }

而构造堆就要有些难度了（这以大顶堆排序为例）

 1 void adjustHeap(vector<int> &arr,int i,int len){
 2     int temp = arr[i];
 3     for(int k=2*i+1;k<len;k=k*2+1){
 4         //k指向左右孩子中最大的那个 
 5         if(k+1<len && arr[k]<arr[k+1]){
 6             k++;
 7         }
 8         //这里使用了优化方法只需要一次交换 
 9         if(arr[k]>temp){
10             arr[i] = arr[k]; 
11             i = k;
12         }else{
13             break;
14         }
15     }
16     arr[i] = temp;
17 }

最后给出排序函数：

 1 void heapSort(vector<int> &arr){
 2     //第一次初始化堆 
 3     for(int i=arr.size()/2-1;i>=0;i--){
 4         adjustHeap(arr,i,arr.size());
 5     }
 6     //从后往前循环能很好地模拟树的不断缩小 
 7     for(int i = arr.size()-1;i>0;i--){
 8         //交换&构建堆 
 9         Swap(arr,i);
10         adjustHeap(arr,0,i);
11     }
12 }

参考：堆排序

heapsort

推荐阅读