堆排序 java 实现-蒲公英云

堆排序 java 实现

public class HeepSort {
    private static void heepSort(int[] arr) {
        int n = arr.length;
        int[] a = new int[n+1];//堆排序只能从1开始，新建一个从1开始的数组
        for(int i = 1; i < a.length; i++) {
            a[i] = arr[i-1];
        }
        //建大顶堆，然后交换到最后面
        for(int i = n/2; i >=1; i--) {
            adjustHeep(a, i, n);
        }        
        System.out.println("大顶堆：" + Arrays.toString(a));
        //n-1次交换
        for(int i = 1; i < n; i++) {        
            int tem = a[1];//最大的数交换到最后面
            a[1] = a[n-i+1];
            a[n-i+1] = tem;
            //剩下的从根节点调整大顶堆
            adjustHeep(a, 1, n-i);
        }
        for(int i = 0; i < arr.length; i++) {
            arr[i] = a[i+1];
        }        
    }
    private static void adjustHeep(int[] a, int k, int len) {
        int i = k, j = i * 2;
        int tem = a[i];
        while(j <= len) {
            if(j+1 <= len && a[j+1] > a[j]) {
                j++;//记录大的
            }
            if(tem < a[j]) {
                a[i] = a[j];
                i = j;
                j = i * 2;
            } else {
                break;
            }
        }
        a[i] = tem;
    }
    public static void main(String[] args) {
        int[] arr = {2, 13, 35, 12, 36, 4, 66, 93, 60};
        System.out.println("before:" + Arrays.toString(arr));
        heepSort(arr);
        System.out.println("after:" + Arrays.toString(arr));
    }
}