堆排序 - 简书

堆排序

个人主页：https://chengang.plus/

文章将会同步到个人微信公众号：Android部落格

1.1 描述

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

1.2 代码

public class HelloWorld {
    static int[] numbers = {5,4,3,7,2,5,1,9,12,6,8,1,34};
    static int size = numbers.length;
    
    public static void buildMaxHeap(){
        int startPoint = size / 2 - 1;
        for(int index = startPoint;index >= 0;index--){
             adjustMaxHeap(index);
        }
    }
    
    public static void adjustMaxHeap(int maxPoint){
        int leftPoint = 2 * maxPoint + 1;
        int rightPoint = 2 * maxPoint + 2;
        int maxNumber = numbers[maxPoint];
        int largestIndex = maxPoint;
        if(leftPoint < size && numbers[leftPoint] > maxNumber){
            largestIndex = leftPoint;
        }
        if(rightPoint < size && numbers[rightPoint] > maxNumber){
            largestIndex = rightPoint;
        }
        if(largestIndex != maxPoint){
            swap(maxPoint,largestIndex);
            adjustMaxHeap(largestIndex);
        }
    }
    
    public static void swap(int i,int j){
        int temp = numbers[I];
        numbers[i] = numbers[j];
        numbers[j] = temp;
    }
    
    public static void heapSort(){
        buildMaxHeap();
        for(int index = size - 1;index > 0;index--){
            swap(0,index);
            --size;
            adjustMaxHeap(0);
        }
    }
    
    public static void main(String []args) {
        heapSort();
        for(int value : numbers){
            System.out.println("quick value is:" + value);
        }
    }
}

1.3 总结

堆排序运用了二叉树的相关知识，使用大顶堆实现。Java中的PriorityQueue默认是小顶堆，可以通过改造Comparator成为小顶堆。

代码的基本流程是：

先构建一颗二叉树，2n + 1为左节点，2n + 2为右节点，index从最后一个父节点开始创建，并不断循环到根节点。
第一步创建的时候，父节点与值较大的子节点交换位置，以此循环。
将二叉树根节点与最后一个叶子节点交换，同时将整棵树节点数减一，然后重新将整棵树重复第二步。
在构建大顶堆的过程中，父节点与左右节点比较，选取值最大的节点作为父节点，并再去找这个最大值序号的左右节点，再去与自己的左右节点比较，重复进行，一直到最后一个父节点。

上述步骤的示意图如下：

堆排序.jpg