【十大经典排序算法】堆排序及其JAVA代码实现

3,336 views

阅读模式

之前写了十大经典排序算法的桶排序，现在，我们再来看看堆排序以及其Java代码的实现...

原理

既然是堆排序，肯定是涉及到数据结果中的堆，堆排序是利用堆来实现排序；其排序既用到完全二叉树的特性，又用到了堆父节点大于子节点的特性。

先将所有数据当成一颗完全二叉树，然后使得所有的父节点都大于子节点（满足堆的特性），然后将完全二叉树最后一个叶子节点与根节点交换（此时最后一个节点属于有序的，我们暂称其存在于有序区，而其他节点存在无序区），此时数据不再满足堆的特性，因此再继续调整，让所有父节点大于子节点，再替换最后一个叶子节点与根节点（此时有序区存在两个节点），依此循环，直至所有节点都加入有序区，则排序完成。

示意图

发现自己上面表达得有点太啰嗦了，却又不知道怎么去更改，暂且自认为已经表达了意思吧。

我们再来看看其示意图（画图太麻烦，只好百度之，注：下图来自网络）

堆排序

java代码

堆排序算法java实现代码如下：

public class BucketSort implements IArraySort {  
    //声明全局变量，用于记录数组array的长度；
    static int len;
    /**
     * 堆排序算法
     *
     * @param array
     * @return
     */
    public static int[] HeapSort(int[] array) {
        len = array.length;
        if (len < 1) return array;
        //1.构建一个最大堆
        buildMaxHeap(array);
        //2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆
        while (len > 0) {
            swap(array, 0, len - 1);
            len--;
            adjustHeap(array, 0);
        }
        return array;
    }
    /**
     * 建立最大堆
     *
     * @param array
     */
    public static void buildMaxHeap(int[] array) {
        //从最后一个非叶子节点开始向上构造最大堆
        for (int i = (len/2 - 1); i >= 0; i--) { 
            adjustHeap(array, i);
        }
    }
    /**
     * 调整使之成为最大堆
     *
     * @param array
     * @param i
     */
    public static void adjustHeap(int[] array, int i) {
        int maxIndex = i;
        //如果有左子树，且左子树大于父节点，则将最大指针指向左子树
        if (i * 2 < len && array[i * 2] > array[maxIndex])
            maxIndex = i * 2;
        //如果有右子树，且右子树大于父节点，则将最大指针指向右子树
        if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])
            maxIndex = i * 2 + 1;
        //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
        if (maxIndex != i) {
            swap(array, maxIndex, i);
            adjustHeap(array, maxIndex);
        }
    }
    /**
     * 交换数组内两个元素
     * @param array
     * @param i
     * @param j
     */
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}