堆排序

import java.util.Arrays;

/**
 *  堆排序
 * @author SUJiannan
 */
public class Main {

    public static void main(String[] args) {
        int[] a = {1,4,2,66,7,88,12,34,11,2,-1,0};
        initHeap(a);
        System.out.println(Arrays.toString(a));
        sortArray(a);
        System.out.println(Arrays.toString(a));
    }

    /**
     * 初始化堆
     */
    private static void initHeap(int[] a) {
        for (int i = (a.length - 1)/2; i>= 0 ;i--) {
            int k = i;
            int j = k*2 + 1; 
            while (j < a.length) {
                if(j < a.length - 1) {
                    if(a[j] < a[j+1]) {
                        j++;
                    }
                }
                if(a[k] < a[j] ) {
                    swap(k,j,a);
                    k = j;
                } else {
                    break;
                }
                j = 2*k +1;
            }
        }
    }
    
    /**
     * 排序
     */
    private static void sortArray(int[] a) {
        for (int i = a.length - 1; i > 0; i--) {
            swap(0, i, a);
            reNewHead(a,i);
        }
    }

    private static void reNewHead(int[] a, int last) {
        int k = 0;
        int j = 2*k + 1;
        while (j < last) {
            if(j < a.length - 1) {
                if(a[j] < a[j+1]) {
                    j++;
                }
            }
            if(a[j] > a[k]) {
                swap(k, j, a);
                k = j;
            } else {
                break;
            }
            j = 2*k + 1;
        }
    }

    /**
     * 交换
     */
    private static void swap(int k, int i,int[] a) {
        int temp = a[k];
        a[k] = a[i];
        a[i] = temp;
    }
}

常见排序算法复杂度：

21457204_1326898064RUxx.jpg