Skip to content

Latest commit

 

History

History
30 lines (19 loc) · 892 Bytes

README.md

File metadata and controls

30 lines (19 loc) · 892 Bytes

heapsort

堆排序

堆排序原理

利用最大堆顶部是最大值的特性,将最大堆顶部的值与最后一个元素交换,将最大值放在末位

假设数组[13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

初始化最大堆,堆的上一层数据是大于下一层的数据的

                          13
            12                          11
      10          9                 8         7
  6        5    4   3             2   1     0

第一层为13

第二层为12 11

第三层为10 9 8 7

第四层为6 5 4 3 2 1 0

上层数据必须大于下层数据

初始化最大堆之后,开始从数组的末位循环,每次将堆长度减1, 并将堆的最后一位和首位交换,交换完之后,再次生成最大堆, 此时堆顶又是最大值,再与之前交换值的位置的前一个位置值做交换。