CH07-堆排序

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

算法描述

  1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;
  2. 将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]
  3. 由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。

动图演示

NAME

代码实现

注意:这里用到了完全二叉树的部分性质.

//声明全局变量,用于记录数组array的长度;
static int len;
/**
 * 堆排序算法
 *
 * @param array
 * @return
 */
public static int[] HeapSort(int[] array) {
    len = array.length;
    if (len < 1) return array;
    //1.构建一个最大堆
    buildMaxHeap(array);
    //2.循环将堆首位(最大值)与末位交换,然后在重新调整最大堆
    while (len > 0) {
        swap(array, 0, len - 1);
        len--;
        adjustHeap(array, 0);
    }
    return array;
}
/**
 * 建立最大堆
 *
 * @param array
 */
public static void buildMaxHeap(int[] array) {
    //从最后一个非叶子节点开始向上构造最大堆
    for (int i = (len/2 - 1); i >= 0; i--) { //感谢 @让我发会呆 网友的提醒,此处应该为 i = (len/2 - 1) 
        adjustHeap(array, i);
    }
}
/**
 * 调整使之成为最大堆
 *
 * @param array
 * @param i
 */
public static void adjustHeap(int[] array, int i) {
    int maxIndex = i;
    //如果有左子树,且左子树大于父节点,则将最大指针指向左子树
    if (i * 2 < len && array[i * 2] > array[maxIndex])
        maxIndex = i * 2;
    //如果有右子树,且右子树大于父节点,则将最大指针指向右子树
    if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])
        maxIndex = i * 2 + 1;
    //如果父节点不是最大值,则将父节点与最大值交换,并且递归调整与父节点交换的位置。
    if (maxIndex != i) {
        swap(array, maxIndex, i);
        adjustHeap(array, maxIndex);
    }
}

算法分析

  • 最佳情况:T(n) = O(nlogn)
  • 最差情况:T(n) = O(nlogn)
  • 平均情况:T(n) = O(nlogn)