JAVA十大排序算法之堆排序详解

什么是堆排序

堆排序是一种经典的排序算法，在java的Collections.sort()方法中也采用了堆排序的实现方式。堆排序的基本思想是将待排序的序列视为一棵完全二叉树，每个节点的关键字都不大于（或不小于）其子节点的关键字，然后构建大（小）顶堆，最后依次取出堆顶元素并删除。

堆排序的原理

1.构建堆

堆排序首先需要将待排序的序列构建成一个堆。若是要对序列进行升序排序，则需要构建大顶堆；若是要对序列进行降序排序，则需要构建小顶堆。构建堆的过程一般采用从下往上的方式进行。

假设待构建的序列为A，该序列的长度为n，则A的最后一个非叶子节点为i=n/2-1。如果节点i的子节点存在，则节点i的左子节点为2i+1，右子节点为2i+2。从i开始循环，每次循环都是从父节点、左子节点、右子节点中找出最大值或最小值并交换位置，直到循环到根节点就结束，最终得到的堆就是大顶堆或小顶堆。

示例：

private static void buildMaxHeap(int[] arr) {  
    int n = arr.length;  
    for (int i = n/2-1; i >= 0; i--) {  
        maxHeapify(arr, n, i);  
    }  
}  

private static void maxHeapify(int[] arr, int n, int i) {  
    int left = 2 * i + 1;  
    int right = 2 * i + 2;  
    int largest = i;  
    if (left < n && arr[left] > arr[largest]) {  
        largest = left;  
    }  
    if (right < n && arr[right] > arr[largest]) {  
        largest = right;  
    }  
    if (largest != i) {  
        int temp = arr[i];  
        arr[i] = arr[largest];  
        arr[largest] = temp;  
        maxHeapify(arr, n, largest);  
    }  
}  

上面是对升序排列的堆排序的构建堆的函数实现。这里采用的是从下往上的方式，通过调用maxHeapify函数依次构建每一个堆，以最终构建好整个序列的堆。

2.取堆顶并删除

构建好一个堆之后，堆顶元素就是序列中最大的（或最小的）元素了。我们先将堆顶的元素与序列的最后一个元素交换位置，然后将序列的长度减一，这样原先的堆顶元素就被从堆中删除，并将其加入到了序列的"有序区间"中。最后，再用新的堆顶元素跟剩下的序列元素重新构建堆，重复以上步骤，直到所有元素都被从堆中删除并加入到序列的有序区间中。这就是堆排序的核心算法。

示例：

private static void heapSort(int[] arr) {  
    int n = arr.length;  
    // 构建堆（升序用大顶堆，降序用小顶堆）
    buildMaxHeap(arr);  
    for (int i = n - 1; i >= 0; i--) {  
        // 把堆顶元素与最后一个元素交换位置
        int temp = arr[0];  
        arr[0] = arr[i];  
        arr[i] = temp;  
        // 删掉堆顶元素，重新构建堆
        maxHeapify(arr, i, 0);  
    }  
}  

上面是堆排序的完整代码实现。此处先构建大顶堆用于升序排列，然后循环依次取出堆顶元素，并删除。每次删除之后都需要重新构建堆，从而得到新的堆顶元素，然后再次取出、删除，如此循环迭代，最终完成排序操作。

注意事项

1. 堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。
2. 堆排序不稳定，可能破坏稳定性。
3. 堆排序在序列长度较小时，被认为是不如其他排序算法的。
4. 堆排序虽然时间复杂度比较高，但是实现起来相对简单。

总结

堆排序是比较经典的排序算法之一。它采用的是构建堆和取堆顶并删除的方式，经过多次循环迭代，最终得到有序序列。虽然时间复杂度比较高，但是实现起来相对比较简单，而且不像快速排序、冒泡排序等算法会受到数据初始排列的影响，因此具有比较稳定的性能。但是，堆排序由于是不稳定的，所以在某些场景下可能不是最佳的选择。