原地堆排序思想

• 對于已經(jīng)“堆化”的數(shù)據(jù)，堆頂?shù)脑厥亲畲蟮慕徘蹋瑢?yīng)到數(shù)組就是數(shù)組的第一個元素是最大的绍哎，原地的堆排序就是以這個性質(zhì)作為出發(fā)點的；
• 將堆頂元素和最后一個元素交換崇堰，最大的元素就歸位了；
• 對新?lián)Q到堆頂?shù)脑刈鱿鲁敛僮鞣庇ǎ蛊渎湓诙训暮线m位置特幔，此時除了已歸位到數(shù)組最后的“大家伙”們，整個數(shù)組還是滿足堆的性質(zhì)的蚯斯；
• 繼續(xù)對堆頂?shù)脑睾同F(xiàn)存的未歸位序列的最后一個元素交換；

算法實現(xiàn)

• 先對待排序的數(shù)組heapify遭赂；
• 再拿堆頂元素和最后一個元素換横辆，換上堆頂?shù)脑刈鰝€下沉操作；

// 不使用一個額外的最大堆, 直接在原數(shù)組上進行原地的堆排序
public class HeapSort {

    // 我們的算法類不允許產(chǎn)生任何實例
    private HeapSort(){}

    public static void sort(Comparable[] arr){

        int n = arr.length;

        // 注意狈蚤，此時我們的堆是從0開始索引的
        // 從(最后一個元素的索引-1)/2開始
        // 最后一個元素的索引 = n-1
        for( int i = (n-1-1)/2 ; i >= 0 ; i -- )
            shiftDown(arr, n, i);

        for( int i = n-1; i > 0 ; i-- ){
            swap(arr, 0, i);
            shiftDown(arr, i, 0);
        }
    }

    // 交換堆中索引為i和j的兩個元素
    private static void swap(Object[] arr, int i, int j){
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // 原始的shiftDown過程
    private static void shiftDown(Comparable[] arr, int n, int k){

        while( 2*k+1 < n ){
            int j = 2*k+1;
            if( j+1 < n && arr[j+1].compareTo(arr[j]) > 0 )
                j += 1;

            if( arr[k].compareTo(arr[j]) >= 0 )break;

            swap( arr, k, j);
            k = j;
        }
    }

    // 優(yōu)化的shiftDown過程, 使用賦值的方式取代不斷的swap,
    // 該優(yōu)化思想和我們之前對插入排序進行優(yōu)化的思路是一致的
    private static void shiftDown2(Comparable[] arr, int n, int k){

        Comparable e = arr[k];
        while( 2*k+1 < n ){
            int j = 2*k+1;
            if( j+1 < n && arr[j+1].compareTo(arr[j]) > 0 )
                j += 1;

            if( e.compareTo(arr[j]) >= 0 )
                break;

            arr[k] = arr[j];
            k = j;
        }

        arr[k] = e;
    }

    // 測試 HeapSort
    public static void main(String[] args) {

        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        SortTestHelper.testSort("_04.HeapSort", arr);

        return;
    }
}