1. /**
    2.  * 堆排序思路：
    3.  *     1.拷贝数组
    4.  *     2.按i/2位置开始构造大堆或者小堆
    5.  *         堆排序交换（从下往上，将大值向下交换）
    6.  *     3.进行排序，将堆顶与尾标识进行交换
    7.  *
    8.  * 堆排序属于选择排序
    9.  */
    10. public class HeapSort  {
    12.     public int[] sort(int[] sourceArray)  {
    13.         // 对 arr 进行拷贝，不改变参数内容
    14.         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    15.         // 获取数组的长度
    16.         int len = arr.length;
    17.         // 构造大堆
    18.         buildMaxHeap(arr, len);
    20.         for (int i = len - 1; i > 0; i--) {
    21.             swap(arr, 0, i);//将堆顶即树根与最后一个值进行交换，即把最大值逐步往后放，来完成排序
    22.             len--;
    23.             heapify(arr, 0, len);//大堆位置交换
    24.         }
    25.         return arr;
    26.     }
    28.     /**
    29.      * 大堆
    30.      *              b0
    31.      *         b1             b2
    32.      *  b3        b4     b5         b6
    33.      *b7  b8  b9
    34.      * 
    35.      * 左孩子节点下标i = 父节点下标z*2+1
    36.      * 右孩子节点下标i = 父节点下标z*2+2
    37.      * 进行二叉树大堆构造的时候,只需要知道最后一个节点的父节点,然后从该父节点下标往前构造即可
    38.      * 最后一个节点的父节点的下标 i = length
    39.      */
    40.     //构建堆的时候，需要从最下层往上层排，按从小到大顺序往上排，然后将上面小的值和其子节点大的值互换位置
    41.     private void buildMaxHeap(int[] arr, int len) {
    42.         //节点(在数组中下标为i)
    43.             //其左孩子节点下标 = 2i+1
    44.             //其有孩子节点下标 = 2i+2
    45.         for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
    46.             //从后往前，从下往上进行排序
    47.             heapify(arr, i, len);
    48.         }
    49.     }
    51.     // 判断父节点和子节点的大小关系，并进行位置交换
    52.     private void heapify(int[] arr, int i, int len) {
    53.         // i下标 节点位置为 父节点位置
    54.         // 2*i+1 left节点位置为 左孩子节点位置
    55.         // 2*i+2 right节点位置为 右孩子节点位置
    56.         int left = 2 * i + 1;
    57.         int right = 2 * i + 2;
    58.         int largest = i;
    61.         // 如果left节点下标大于等于len了，说明 i 节点是没有左孩子节点的
    62.         if (left < len
    63.                 // 此时largest的值 = i，即父节点和左孩子节点比较大小
    64.                 // 如果左孩子节点大于父节点
    65.                 && arr[left] > arr[largest]) {
    66.             // 则把以i节点为子树中的最大值确定为左孩子节点
    67.             largest = left;
    68.         }
    69.         // 如果right节点下标大于等于len了，说明 i 节点是没有右孩子节点的
    70.         if (right < len 
    71.                 // 如果上面的if成立，则此时largest的值 为 left
    72.                 // 那么如果右孩子节点的值大于 largest节点即左孩子节点的值
    73.                 && arr[right] > arr[largest]) {
    74.             // 则以i节点为子树中的最大值确定为右孩子节点
    75.             largest = right;
    76.         }
    78.         // 如果largest发生了改变，不为 i 值，则进行位置交换
    79.         if (largest != i) {
    80.             swap(arr, i, largest);
    81.             //发生了交换
    82.             heapify(arr, largest, len);
    83.         }
    84.     }
    86.     private void swap(int[] arr, int i, int j) {
    87.         int temp = arr[i];
    88.         arr[i] = arr[j];
    89.         arr[j] = temp;
    90.     }
    92.     public void println(int [] a) {
    93.         for(int x:a) {
    94.             System.out.print(" "+x);
    95.         }
    96.         System.out.println("");
    97.     }    
    99.     public static void main(String[] args) {
    100.         HeapSort heapSortTest = new HeapSort();
    101.         int[] nums = {5,9,6,8,7,3,5,10,15,22,69,36};
    102.         heapSortTest.println(heapSortTest.sort(nums));
    103.     }
    105. }