本文共 1578 字，大约阅读时间需要 5 分钟。

package com.chenjian.heapsort;import java.util.Arrays;public class HeapSort {
       public static void main(String[] args) {
           int[] arr = {
   4,6,8,5,9};        heapSort(arr);    }    public static void heapSort(int[] arr) {
           //将无序序列构成一个堆        int temp = 0;        //i为非叶子节点的索引        for(int i = arr.length / 2 - 1; i >= 0; i--) {
               adjustHeap(arr, i, arr.length);        }        //将大顶堆变为升序数组  只需要排arr.length-1个  最后一个自然就好了        for(int j = arr.length - 1; j > 0; j--) {
               //将最后一个元素与第0个位置的元素进行交换，互换后末尾的元素就是最大的            temp = arr[j];            arr[j] = arr[0];            arr[0] = temp;            //j为每次需要调整的元素的数量，每次的数量慢慢减少，在把它变为大顶堆            adjustHeap(arr, 0, j);        }        System.out.println(Arrays.toString(arr));    }    /**     *     * @param arr   待调整的数组     * @param i     表示非叶子节点在数组中的索引     * @param length 表示对多少个元素进行调整  length是在逐渐的减少  也是数组的长度     */    public static void adjustHeap(int[] arr, int i, int length) {
           int temp = arr[i];//先取出当前元素的值  保存在临时变量        //开始调整        //k为i的左子节点  k = k * 2 + 1  表示找到k的左子节点        for(int k = i * 2 + 1; k < length; k = k * 2 + 1) {
               if(k + 1 < length && arr[k] < arr[k + 1]) {
   //左子节点小于右子节点                k++; //k指向右子节点            }            if(arr[k] > temp) {
   //如果子节点大于 父节点                arr[i] = arr[k];//把子节点赋给父节点                i = k;//i指向k，继续循环比较            }else {
                   break;            }        }        //for循环结束后  我们已经将以i为父节点的树最大值，放在了最顶（局部）        arr[i] = temp;//将temp放在调整后的位置    此时以i为根节点的树已经是一个大顶堆    }}

转载地址：http://ixhzi.baihongyu.com/