2.6堆排序
时间复杂度o(n*logn)

堆排序.png

思路：0~N-1 个数
1.将数组中的n个数建成大小为n的大根堆
2.堆顶元素为整个元素的最大值，将堆顶元素和堆的最后一个元素进行交换，将最大值脱离出整个堆结构放在数组的最后位置，作为数组的有序部分
3.把N-1最大值大小的值进行堆调整，再将最大值和组数的最后位置进行交换，作为数组的有序部分
......
4.依次进行堆调整，最后位置交换，得到一个有序数列

import java.util.*;
public class HeapSort {

public int[] heapSort(int[] A, int n) {
    BUILD_MAX_HEAP(A);
        SORT_HEAP(A);
        return A;
    }

    /**
     * 堆排序
     * @param A
     */
    private void SORT_HEAP(int[] A) {
        for (int i = A.length-1;i >=0;i--) {
            swap(A, 0, i); // 将堆尾和堆顶交换
            // 0~length(A)-1 的堆，重新建堆
            MAX_HEAPIFY(A, 0, i-1);
            //
        }
    }
  
    /**
     * 建堆
     * @param A
     */
    private void BUILD_MAX_HEAP(int[] A) {
        for (int i = A.length/2-1;i >= 0;i--) {
            MAX_HEAPIFY(A, i, A.length-1); 

        }
    }
  
    
    /**
     * 保持堆的性质
     * @param A
     * @param i
     * @param end
     */
    private void MAX_HEAPIFY(int[] A, int i, int end) {
        int l = LEFT(i);
        int r = RIGHT(i);
        int largest;
        if (l <= end && A[l] > A[i]) {
            largest = l;
        }else {
            largest = i;
        }
        if (r <= end && A[r] > A[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(A, i, largest);
            MAX_HEAPIFY(A, largest, end);
        }
    }
  
    private int LEFT(int i) {
        return 2*i+1;
    }
  
    private int RIGHT(int i) {
        return 2*i+2;
    }
  
    private void swap(int[] A, int a, int b) {
        int temp = A[a];
        A[a] = A[b];
        A[b] = temp;
    }

}