1. package sort;
    3. import java.util.Arrays;
    4. import java.util.stream.Collectors;
    6. public class HeapSort {
    8.     /**
    9.      * 选择排序-堆排序-不稳定排序
    10.      * @param array 待排序数组
    11.      * @return 已排序数组
    12.      */
    13.     public static int[] heapSort(int[] array){
    14.         //这里元素的索引是从0开始的,所以最后一个非叶子结点array.length/2 - 1
    15.         for(int i= array.length/2-1; i>=0; i--){
    16.             adjustHeap(array, i, array.length); // 调整堆
    17.         }
    19.         // 上述逻辑，建堆结束
    20.         // 下面，开始排序逻辑
    21.         for(int j = array.length-1; j>0; j--){
    22.             // 元素交换，作用是去掉大顶堆
    23.             // 把大顶堆的根元素，放到数组的最后；
    24.             // 换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置
    25.             swap(array, 0, j);
    26.             adjustHeap(array, 0, j);
    27.         }
    28.         return array;
    29.     }
    31.     /**
    32.      * 整个堆排序最关键的地方
    33.      * @param array 待组堆
    34.      * @param i 起始结点
    35.      * @param length 堆的长度
    36.      */
    37.     public static void adjustHeap(int[] array, int i, int length){
    38.         // 先把当前元素取出来，因为当前元素可能要一直移动
    39.         int temp = array[i];
    40.         // 2*i+1 为i的左子树
    41.         // 2*k+1 为k的左子树
    42.         for(int k = 2 * i + 1; k < length; k = 2 * k + 1){
    43.             // 让 k 先指向子节点中最大的节点
    44.             if(k+1 < length && array[k] < array[k+1]){  // 如果有右子树，并且右子树大于左子树
    45.                 k++;
    46.             }
    47.             // 如果发现节点（左右子节点）大于根节点，则进行值的交换
    48.             if(array[k] > temp){
    49.                 swap(array, i, k);
    50.                 i = k;
    51.             } else {
    52.                 break;
    53.             }
    54.         }
    55.     }
    57.     public static void swap(int[] arr, int a, int b){
    58.         int temp = arr[a];
    59.         arr[a] = arr[b];
    60.         arr[b] = temp;
    61.     }
    64.     public static void main(String[] args) {
    65.         int []arr = {9,8,7,6,5,4,3,2,1};
    66.         arr = heapSort(arr);
    67.         System.out.println(Arrays.stream(arr).boxed().collect(Collectors.toList()));
    69.     }
    70. }