蓝桥杯算法基础（15）：十大排序算法（堆排序）c语言版

堆排序

外堆：
需要一段和原来数组长度大小的内存空间，这段内存空间是用来存储堆结构的
内堆：
不需要重新申请内存，直接原来的数组上进行排序

堆结构
本质上就是一个完全二叉树（不了解二叉树可以取学习一下二叉树的基本概念），每一个节点的存储都是连续的

知道当前下标为current
    从0开始计数
    左子树下标-->2*current+1
    右子树下标-->2*current+2

    从1开始计数
    左子树下标-->2*current
    右子树下标-->2*current+1

    大顶堆
    父亲的权值比左右子树的权值大
    小顶堆
    父亲的权值比左右子树的权值小

    (小顶堆)
             2
            / \
           3   4
          /\   /
         8  7 6
   （大顶堆）
              8
             /\
            7  3
           /\  /\
          3 5 2  0
         /
        2
        完全二叉树中间是不能有空的
        (以下二叉树就不是完全二叉树)
              8
             /\
            7  3
           /\  /\
          3 5 2  0
         /   \
        2     4

堆结构 

//外堆
typedef struct Heap{
 int* root;
 int length;
}Heap;

 (伪代码)

//入堆
void pushHeap(Heap* heap,int data);
//出堆
int popHeap(Heap* heap);

 
arr[MAXSIZE];
for(arr){
pushHeap(heap,arr[i])
}
for(heap){
arr[i]=popHeap(heap);
}

 创建一个堆

Heap* creatHeap(int length){
Heap* heap=(Heap*)malloc(sizeof(Heap)*length);//开辟一个较大的内存空间
 assert(heap);//断言一下
 heap->length=0;//让length从0开始
 heap->root=(int*)malloc(sizeof(int)*length);//开辟length长度的int数组，表示各个节点节点
 assert(heap->root);
 return heap;

}

  //5 74 94 12 60 33 14
  小顶堆
  每拿一个数，放到底部，每次都要与父亲比较，小于父亲则与父亲替换
            5(0)
           /     \
          12(1)   14(2)
         / \       /  \
       74(3)60(4)94(5)33(6)
   //入堆
  // 0 1 2 3 4 5 6 7 8
  void pushHeap(Heap* heap,int data){
       int current=heap->length++;
       int parent=(current-1)/2;
       heap->root[current]=data;
       while(parent!=current){
           if(heap->root[current]<heap->root[parent]){
           swap(heap->root,current,parent);
           current=parent;
           parent=current/2;
           }else
           break;
       }
   }

  拿走一个最小值，最后一个到第一个位置，再与左右子结点中比它小且二者中比较小的交换，直到回到再次满足小顶堆
            33
           /  \
          12   14
         / \    /
       74  60 94

            12
           /  \
          33   14
         / \    /
       74  60 94
       //出堆
  int popHeap(Heap* heap){
       int val=heap->root[0];//   拿走一个最小值
       int  current=0;//从第一个位置开始
       int rchild=2*current+2;//右子树（rchild-1为左子树）
       int small;
       int n=--heap->length;//最后一个位置
       heap->root[0]=heap->roo[--heap->length];//将最后的数放到第一个位置上
       while(rchild <= heap->length){
           small=arr[rchild-1]<arr[rchild]?richild-1:rchild;
           if(heap->root[small]<heap->root[current]){
           swap(heap->root,small,current);//heap->root是一个指针开辟空间形成的数组
           current=small;
           rchild=2*(current)+2;
           }
       }else
           break;
       return val;
  }



  viod heapSort(int arr[],int length){
  Heap *heap=creatHeap(MAXSIZE);
   for(int i=0;i<MAXSIZE;i++){
   pushHeap(heap,arr[i]);

   }

   for(inti=0;i<MAXSIZE;i++){
   arr[i]=popHeap(heap);}

   free(heap->root);

  }



  内堆实现
  //不需要重新申请空间
   heapify实现大顶堆
   再将大顶堆的最大值逐渐放到最后一位上
   最终实现从小到大有序的小顶堆


       //heapify 堆化
   void  heapify(int arr[],int length,int current){
   int rchild=2*current+2;
   int large;
       while(rchild<=length){
           //若右子节点为length位置上的，然而length位置上没有元素，则意味着只有左子节点，在length-1上
           //选子节点较大的元素
           large=rchild==length?rchild-1:(arr[rchild-1]>arr[rchild]?rchild-1:rchild);

           if(arr[large]>arr[current]){
           swap(arr,large,current);//与比自己大的子节点交换，并更新位置，继续与子节点比较，直至找到合适的位置
           current=large;
           rchild=2*current+2;
           }else
           break;//如果找到合适的位置，则推出循环
           //堆化就是将某一个位置的数按照大顶堆的方式，找到合适的位置
       }
   }
  void heapSort2(int arr[],int length){
       int current=length/2;//将除完全二叉树最后一层的叶子节点的数进行堆化
       while(current>=0)//直到所有的数都完成堆化，则结束
       {
           heapify(arr,length,current);
           current--;

       }



       showArr(arr,length);//输出arr所有元素


       while(length>=0){
        swap(arr,0,--length);//逐渐将大顶堆的最大值放到数组的后面，将最后一个数放到第一个位置
        heapify(arr,length,0);
        //然后对第一个位置上的数进行堆化，每次循环，length都减1，就把之前放到最后的最大值，给踢出对结构了，如此最大值便保留了下来，如此循环直到所有数都排好序
       //形成从小到大的序列。
       }

  }
*/