排序算法七--堆排序

╰+攻爆jí腚メ 2022-05-10 14:34 174阅读 0赞

什么是堆？   
堆是一棵顺序存储的完全二叉树。   
小根堆：每个结点的关键字都不大于其孩子结点的关键字。   
大根堆：每个结点的关键字都不小于其孩子结点的关键字。   
对于n个元素的序列\{R0, R1, … , Rn\}当且仅当满足下列关系之一时，称之为堆：   
(1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)   
(2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)   
利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。   
其基本思想为(大顶堆)：   
1)将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；   
2)将堆顶元素R\[1\]与最后一个元素R\[n\]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R\[1,2…n-1\]<=R\[n\];    
3)由于交换后新的堆顶R\[1\]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R\[1\]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

![70][]

![SouthEast][]

**平均时间复杂度：**O(NlogN)  
由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N \* logN)。

代码实现：

//构建最小堆
    public static void MakeMinHeap(int a[], int n){
     for(int i=(n-1)/2 ; i>=0 ; i--){
         MinHeapFixdown(a,i,n);
     }
    }
    //从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2  
    public static void MinHeapFixdown(int a[],int i,int n){
    
       int j = 2*i+1; //子节点
       int temp = 0;
    
       while(j<n){
           //在左右子节点中寻找最小的
           if(j+1<n && a[j+1]<a[j]){   
               j++;
           }
    
           if(a[i] <= a[j])
               break;
    
           //较大节点下移
           temp = a[i];
           a[i] = a[j];
           a[j] = temp;
    
           i = j;
           j = 2*i+1;
       }
    }
    public static void MinHeap_Sort(int a[],int n){
      int temp = 0;
      MakeMinHeap(a,n);
    
      for(int i=n-1;i>0;i--){
          temp = a[0];
          a[0] = a[i];
          a[i] = temp; 
          MinHeapFixdown(a,0,i);
      }     
    }

部分参考：https://blog.csdn.net/lyhkmm/article/details/78920769

[70]: /images/20220505/c0ace84e5a364742bcec0990684627bb.png
[SouthEast]: /images/20220505/eb3480ec7cc142a5a7609b6fcf0eacb7.png