堆排序

有关堆这个数据结构请参考数据结构之堆。

有关批量建堆请参考完全二叉堆之批量建堆。

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

堆排序可以认为是对选择排序算法中寻找最小（大）元素的优化。

一般升序采用大顶堆，降序采用小顶堆。

算法思想

对数组进行原地建堆（heapify）重复执行以下操作，直到堆的元素数量为1 交换堆顶元素与尾元素堆的元素数量减1对0位置进行1次下滤（siftDown）操作

动图演示

算法实现

package com.morris.data.struct.sort; /** * 堆排序 */ public class HeapSort<E extends Comparable> extends AbstractSort<E> { private int heapSize; @Override protected void sort() { heapSize = array.length; // 先原地构建大顶堆，采用自下而上的下滤 int lastNotLeafIndex = (heapSize >> 1) - 1; // 最后一个非叶子节点的索引 for (int i = lastNotLeafIndex; i >= 0; i--) { siftDown(i); } for (int end = heapSize - 1; end > 0; end--) { // 最大元素与最后一个元素交换 swap(0, end); heapSize--; // 对索引为0的元素进行下滤 siftDown(0); } } /** * 对index的元素进行下滤 * @param index */ private void siftDown(int index) { E v = array[index]; int childIndex; // index的左子节点 while ((childIndex = (index << 1) + 1) < heapSize) { if(childIndex + 1 < heapSize && cmp(childIndex, childIndex + 1) < 0) { // 如果有右子节点，并且右子节点大于左子节点 childIndex = childIndex + 1; } if(cmp(v, array[childIndex]) < 0) { // 父节点小于最大子节点，用最大子节点覆盖父节点 array[index] = array[childIndex]; } else { break; } index = childIndex; } array[index] = v; } }

堆排序的最好、最坏、平均时间复杂度为O(nlogn)，空间复杂度为O(1)，是一个不稳定的排序算法。

更多精彩内容关注本人公众号：架构师升级之路