Java实现堆排序经典代码和算法思路

本文重点讲解Java实现堆排序经典代码和算法思路。

简介

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于(或者大于)它的父节点。

堆排序是一种基于比较的排序算法，它的基本思想是将待排序的元素构建成一个堆，然后依次将堆顶元素取出，放到已排序的序列中，直到堆中所有元素都被取出，最终得到一个有序的序列。

什么是堆

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图

堆排序算法思路

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

堆排序的基本步骤

构建堆：将待排序的元素构建成一个堆，可以使用数组来表示堆，数组中下标为 i 的元素的左子节点下标为 2i+1，右子节点下标为 2i+2。

取出堆顶元素：将堆顶元素取出，放到已排序的序列中。

调整堆：将剩余的元素重新构建成一个堆，然后重复步骤 2 和步骤 3，直到堆中所有元素都被取出。Java代码实现堆排序

构建大顶堆实现堆排序：

public class HeapSort {

    //声明全局变量，用于记录数组array的长度；
    static int len;

    public static void main(String[] args) {
        int[] arr={3,7,2,9,1,4,6,8,10,5};
        HeapSort(arr);
        System.out.println("交换后："+ Arrays.toString(arr));
    }

    /**
     * 堆排序算法
     *
     * @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--) { //感谢 @让我发会呆 网友的提醒，此处应该为 i = (len/2 - 1)
            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;
    }
}

小顶堆实现堆排序：

public class SmailHeap {
    public static void main(String[] args) {
        int[] array = new int[]{1,3,2,7,4,0,5,10};
        heapSort(array);
        System.out.println(Arrays.toString(array));
    }
    private static void heapSort(int[] array) {
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            adjustHeap(array,i,array.length);
        }
        for (int j = array.length - 1; j >= 0; j--) {
            int temp = array[0];
            array[0] = array[j];
            array[j] = temp;
            adjustHeap(array,0,j);
        }
    }
    private static void adjustHeap(int[] array, int i, int len) {
        int temp = array[i];
        for (int k = i * 2 + 1; i < len; k = 2 * k + 1) {
            if (k + 1 < len && array[k] > array[k + 1]) {
                k++;
            }
            if (k<len && array[k] < temp) {
                array[i] = array[k];
                i = k;
            } else {
                break;
            }
        }
        array[i] = temp;
    }
}

 总结

以上就是Java实现堆排序经典代码和算法思路的全部内容，希望对学习有帮助哦！

喜欢 (0)赏

【请潘老师喝杯Coffee吧！】

分享 (0)