堆排序

1. 原理：

1. 利用堆这种数据结构所设计的一种排序算法，堆是一种近似完全二叉树的结构，并满足堆的性质：子节点的键值总是小于（或大于）其父节点的键值
2. 通常堆是用一维数组来实现的：
   • 父节点i的左子节点位置： 2 * i + 1，右子节点位置：2 * i + 2
   • 子节点 i的父节点位置： floor( (i - 1) / 2)
3. 堆的操作：
   • 最大堆调整：对堆的末端节点做调整，使子节点永远大于父节点
   • 创建最大堆：对堆中的所有数据重新排序
   • 堆排序：移除根节点的数据，并做最大堆调整的递归运算。

     2. 代码：

     void Maxiheapify(vector<int>& vec, int start, int end){
         int cur = start;
         int child = 2 * cur + 1;
         while(child < end){
             if(child + 1 < end && vec[child] < vec[child + 1]){
                 child++;
             }
             if(vec[cur] < vec[child]){
                 swap(vec[cur], vec[child]);
                 cur = child;
                 child = 2 * cur + 1;
             }else{
                 break;
             }
         }
     }
     void HeapSort(vector<int>& vec){
         int len = vec.size();
         for(int i = len / 2 - 1; i >= 0; i--){
             MaxHeapify(vec,i,len-1);
         }
         for(int i = len-1; i >0; i--){
             swap(vec[i],vec[0]);
             Maxiheapify(vec,0,i);
         }
     }
     

     3. 分析：

4. 时间复杂度：
   • 最优：O(nlgn)
   • 最差：O(nlgn)
   • 平均：O(nlgn)
5. 空间复杂度：O(n)
6. 稳定性：不稳定