堆排序这个名称一直困扰着我,现在扫一下盲。

首先介绍一下堆的概念:堆是一棵完全二叉树,即指允许最后一层的叶子是不满的,其他层都是满的。叶子节点的出现顺序也是从左边开始向右边累加,不允许中断。父结点必须比子节点要大。

堆排序

堆排序的算法复杂度是O(nlog(n))。由于节点满足完全二叉树,因此可以通过下标的关系找到父节点,子节点。

例如当前节点为i,父节点:(i - 1) /2。左孩子:2i+1,右孩子:2i+2。因此堆排序的策略如下:

堆排序步骤

  1. 构造堆结构,从最后一个元素(叶子)的父节点开始,循环到根节点,每次执行heapify函数(三个节点,找最大的放到根位置)。
  2. 位于根节点的元素是最大的,每次将根节点的数拿出来,作为排序的最后一个值。然后将最后一个叶节点放到根的位置。依次循环下去,直到结束。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
nums = [9,3,4,1,5,6,8,7]

def heapify(nums,n,i):
'''
i 表示要进行调换的根节点位置
'''
c1 = 2*i + 1
c2 = 2*i + 2
max_index = i
if c1 <= n and nums[c1] > nums[i]:
max_index = c1
if c2 <= n and nums[c2] > nums[max_index]:
max_index = c2
if max_index != i:
nums[max_index],nums[i] = nums[i],nums[max_index]

def build_heap(nums):
n = len(nums) - 1
last_index = (n - 1) // 2
for i in range(last_index+1)[::-1]:
heapify(nums,n,i)

def heap_sort(nums):
print(nums)
build_heap(nums)
print(nums)
for i in range(len(nums))[::-1]:
print(i)
nums[0],nums[i] = nums[i],nums[0]
heapify(nums,i-1,0)
print(nums)


heap_sort(nums)