堆排序·HeapSort

堆排序（英语：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，则整个排序过程完成。

算法演示

// 第一次堆排序
array:  [6] [3] [9] [4] [7] [1] [5] [2] [8] [0]
// 构建堆
       ┌──────[6]──────┐
   ┌──[3]──┐       ┌──[9]──┐
 ┌[4]┐   ┌[7]     [1]     [5]
[2] [8] [0]
// 比较最后一个非叶子节点及它的子节点值
7>0;不交换
       ┌──────[6]──────┐
   ┌──[3]──┐       ┌──[9]──┐
 ┌[4]┐   ┌[7]     [1]     [5]
[2] [8] [0]
4<8;交换;8>2不交换
       ┌──────[6]──────┐
   ┌──[3]──┐       ┌──[9]──┐
 ┌[8]┐   ┌[7]     [1]     [5]
[2] [4] [0]
9>5;不交换;9>1;不交换;
       ┌──────[6]──────┐
   ┌──[3]──┐       ┌──[9]──┐
 ┌[8]┐   ┌[7]     [1]     [5]
[2] [4] [0]
3<7;交换;7<8;交换;
       ┌──────[6]──────┐
   ┌──[8]──┐       ┌──[9]──┐
 ┌[7]┐   ┌[3]     [1]     [5]
[2] [4] [0]
6<9;交换;9>8;不交换
       ┌──────[9]──────┐
   ┌──[8]──┐       ┌──[6]──┐
 ┌[7]┐   ┌[3]     [1]     [5]
[2] [4] [0]
// 最大堆完成，交换堆根节点与最后一个元素
       ┌──────[0]──────┐
   ┌──[8]──┐       ┌──[6]──┐
 ┌[7]┐    [3]     [1]     [5]
[2] [4] [9]
array:  [0] [8] [6] [7] [3] [1] [5] [2] [4] [9]
// 第一次堆排序结束

// 第二次堆排序
array:  [0] [8] [6] [7] [3] [1] [5] [2] [4] [9]
// 构建堆
       ┌──────[0]──────┐
   ┌──[8]──┐       ┌──[6]──┐
 ┌[7]┐    [3]     [1]     [5]
[2] [4] [9]
7>4;不交换;7>2;不交换;
       ┌──────[0]──────┐
   ┌──[8]──┐       ┌──[6]──┐
 ┌[7]┐    [3]     [1]     [5]
[2] [4] [9]
6>5;不交换;6>1;不交换;
       ┌──────[0]──────┐
   ┌──[8]──┐       ┌──[6]──┐
 ┌[7]┐    [3]     [1]     [5]
[2] [4] [9]
8>3;不交换;8>7;不交换;
       ┌──────[0]──────┐
   ┌──[8]──┐       ┌──[6]──┐
 ┌[7]┐    [3]     [1]     [5]
[2] [4] [9]
0<6;交换;6<8;交换;
       ┌──────[8]──────┐
   ┌──[6]──┐       ┌──[0]──┐
 ┌[7]┐    [3]     [1]     [5]
[2] [4] [9]
// 最大堆完成，交换堆根节点与最后一个元素
       ┌──────[4]──────┐
   ┌──[6]──┐       ┌──[0]──┐
 ┌[7]     [3]     [1]     [5]
[2] [8] [9]
array:  [4] [6] [0] [7] [3] [1] [5] [2] [8] [9]
// 第二次堆排序结束

…

// 第N-1次堆排序
// 构建堆
       ┌──────[0]
      [1]             [2]
  [3]     [4]     [5]     [6]
[7] [8] [9]
0<1;交换;
       ┌──────[1]
      [0]             [2]
  [3]     [4]     [5]     [6]
[7] [8] [9]
// 最大堆完成，交换堆根节点与最后一个元素
              [0]
      [1]             [2]
  [3]     [4]     [5]     [6]
[7] [8] [9]
array:  [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
// 第N-1次堆排序结束

算法分析

时间复杂度

空间复杂度

稳定性

不稳定排序算法

代码实现

参考