堆排序

堆排序思路：建立大根堆或小根堆，然后堆顶就是有序的，将堆顶和数组的最后一个元素对调位置，那么最后一个元素就是最大的元素，然后调整堆，将堆顶元素和数组倒数第二个元素对调位置，以此类推，重复，就能得到排序序列了.

实现：
/**
     * 堆排序.
     * 思路：第一步建立大根堆.
     */
    @Test
    public void testHeapSort(){
        int[] arr = {4,2,5,1,2,9,8,3,5,6,2,8};

        // 从最后一个非叶子节点开始进行调整.
        for(int i=arr.length/2-1; i>=0; i--){
            heapAdjust(arr, 0 , arr.length-1);
        }

        for(int i=arr.length-1; i>0; i--){
            Util.swap(i, 0, arr);
            heapAdjust(arr, 0, i-1);
        }
        System.out.println(Arrays.toString(arr));
    }

    private void heapAdjust(int[] arr, int index, int len){
        int temp = arr[index];
        for(int i=2*index+1; i<=len; i=i*2+1){
            if(i+1<len && arr[i]<arr[i+1]) i++;
            if(temp > arr[i]) break;

            arr[index] = arr[i];
            index = i;
        }
        arr[index] = temp;
    }