1. 简介

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

2. 算法描述

  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)。
  4. 不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

堆排序动图.gif

3. 代码示例

  1. //声明全局变量，用于记录数组array的长度；
  2. static int len;
  3.     /**
  4.      * 堆排序算法
  5.      *
  6.      * @param array
  7.      * @return
  8.      */
  9.     public static int[] HeapSort(int[] array) {
  10.         len = array.length;
  11.         if (len < 1) return array;
  12.         //1.构建一个最大堆
  13.         buildMaxHeap(array);
  14.         //2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆
  15.         while (len > 0) {
  16.             swap(array, 0, len - 1);
  17.             len--;
  18.             adjustHeap(array, 0);
  19.         }
  20.         return array;
  21.     }
  22.     /**
  23.      * 建立最大堆
  24.      *
  25.      * @param array
  26.      */
  27.     public static void buildMaxHeap(int[] array) {
  28.         //从最后一个非叶子节点开始向上构造最大堆
  29.         for (int i = (len/2 - 1); i >= 0; i--) { //感谢 @让我发会呆 网友的提醒，此处应该为 i = (len/2 - 1) 
  30.             adjustHeap(array, i);
  31.         }
  32.     }
  33.     /**
  34.      * 调整使之成为最大堆
  35.      *
  36.      * @param array
  37.      * @param i
  38.      */
  39.     public static void adjustHeap(int[] array, int i) {
  40.         int maxIndex = i;
  41.         //如果有左子树，且左子树大于父节点，则将最大指针指向左子树
  42.         if (i * 2 < len && array[i * 2] > array[maxIndex])
  43.             maxIndex = i * 2;
  44.         //如果有右子树，且右子树大于父节点，则将最大指针指向右子树
  45.         if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])
  46.             maxIndex = i * 2 + 1;
  47.         //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
  48.         if (maxIndex != i) {
  49.             swap(array, maxIndex, i);
  50.             adjustHeap(array, maxIndex);
  51.         }
  52.     }

4. 性能分析

  1. 最佳情况：T(n) = O(nlogn)
  2. 最差情况：T(n) = O(nlogn)

    平均情况：T(n) = O(nlogn)