1.堆排序

时间复杂度: O(nlog2N)

思路: 堆排序主要分为三步:

1)利用二叉树性质,找到一个父节点与其子节点,并将最大子节点值与父节点值做比较,将最大值交换到父节点上(注意索引位置的调整)

2)利用第一步的过程,逐步形成大顶堆(正序)

3)在大顶堆基础上进行排序,将索引1位置值(最大值)与最后的叶子节点做交换并固定,直到从小到大固定所有值.排序完成.

代码:

origin = [3, 5, 6, 7, 2, 55, 2, 13, 5, 234, 54, 2, 90, 200]

n_origin = [0] + origin

length = len(n_origin) - 1

# 将列表打印为二叉树结构

def tree(li):

    for i in [2**x for x in range(length)]:

        for j in li[:i]:

            print("{:^{}}".format(j, length*(length//2)//i), end='')

        print()

        li = li[i:]

        if not li:

            break

print('\n', 'origin tree:')

tree(origin)

# 调整堆(找到父节点与其子节点,并交换值与索引位置)

def adjust_heap(li, num, cur_index):

    while cur_index * 2 <= num:

        l_index = cur_index * 2

        max_index = l_index

        if num > l_index and li[l_index+1] > li[l_index]:

            max_index = l_index + 1

        if li[max_index] > li[cur_index]:

            li[max_index], li[cur_index] = li[cur_index], li[max_index]

            cur_index = max_index

        else:

            break

    return li

print('\n', 'adjust node:')

print(adjust_heap(n_origin, length, length//2))

# 形成大顶堆

def max_heap(li, num):

    for i in range(num//2, 0, -1):

        adjust_heap(li, num, i)

    return li

print('\n', 'max heap:')

print(max_heap(n_origin, length))

# 在大顶堆基础上,进行排序

def heap_sort(li, num):

    while num > 1:

        li[1], li[num] = li[num], li[1]

        num -= 1

        if num == 2 and li[num] > li[num-1]:

            break

        else:

            adjust_heap(li, num, 1)

    return li[1:]

print('\nsorted heap:')

print(heap_sort(max_heap(n_origin, length), length))

tree(heap_sort(max_heap(n_origin, length), length))