堆排序Java实现（大堆）-蒲公英云

堆排序Java实现（大堆）

Java实现堆排序（建立大堆的形式）

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

在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。
堆中定义以下几种操作：

最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点。
创建最大堆：将堆中的所有数据重新排序。
堆排序：移除位在第一个数据的根节点，并做最大堆调整的递归运算。

代码如下：

import java.util.Arrays;
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[]{
    6, 8, 3, 4, 1, 9, 0, 12, 7, 5};
        System.out.println(Arrays.toString(arr));
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
//堆排序
    private static void heapSort(int[] arr) {
        if (arr.length <= 1 ) {
            return;
        }
        buildMaxHeap(arr);//建立大堆
        for (int i = arr.length - 1; i >= 1; i--) {
            swap(arr, 0, i);//进行交换
            maxHeap(arr, i, 0);//在进行建立大堆
        }
    }
//建立大堆
    private static void buildMaxHeap(int[] arr) {
        int half = (arr.length-1)/2;
        for (int i = half; i >=0; i--) {
            maxHeap(arr,arr.length,i);
        }
    }
//进行交换
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }
//length 为 每次建立大堆的数组长度  i为从哪开始
    private static void maxHeap(int[] arr, int length, int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int max = i;
        if (left < length && arr[i] < arr[left]) {
            max = left;
        }
        if (right < length && arr[max] < arr[right]) {
            max = right;
        }
        if (max != i) {
            swap(arr, max, i);
            maxHeap(arr, length, max);
        }
    }
}