优化堆排序

优化堆排序

上一节的堆排序，我们开辟了额外的空间进行构造堆和对堆进行排序。这一小节，我们进行优化，使用原地堆排序。

对于一个最大堆，首先将开始位置数据和数组末尾数值进行交换，那么数组末尾就是最大元素，然后再对W元素进行 shift down 操作，重新生成最大堆，然后将新生成的最大数和整个数组倒数第二位置进行交换，此时到处第二位置就是倒数第二大数据，这个过程以此类推。

整个过程可以用如下图表示：

Java 实例代码

源码包下载：Download

src/zhishitu/heap/HeapSort.java 文件代码：

package zhishitu.heap;



import zhishitu.sort.SortTestHelper;



/**

 * 原地堆排序

 */

public class HeapSort<T extends Comparable> {





    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;

        }

    }



    // 测试 HeapSort

    public static void main(String[] args) {



        int N = 100;

        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);

        sort(arr);

        // 将heapify中的数据逐渐使用extractMax取出来

        // 取出来的顺序应该是按照从大到小的顺序取出来的

        for (int i = 0; i < N; i++) {

            System.out.print(arr[i] + " ");

        }

        // 确保arr数组是从大到小排列的

        for (int i = 1; i < N; i++)

            assert arr[i - 1] >= arr[i];

    }

}