7-2 堆排序 (10 分)
对n个数,要求用堆排序(最大堆)对其进行排序。
输入格式:
第一行一个n(n<1000)。第二行给出n个数。
输出格式:
输出n行,每行n个数。第一行表示将n个数(将n个数看成一棵树)变成最大堆后的结果,第二行表示将上次结果的根节点交换到现有节点的最后一个节点(然后将除最后一个节点的数看成一颗树),然后将该剩余节点树从新变成最大堆后的结果输出(包括交换到最后的节点),依次类推。
输入样例:
6
7 1 6 4 3 5
结尾无空行
输出样例:
7 4 6 1 3 5
6 4 5 1 3 7
5 4 3 1 6 7
4 1 3 5 6 7
3 1 4 5 6 7
1 3 4 5 6 7
结尾无空行
非常基础的堆排序,建立好这棵后,不停交换首尾元素,再对前三个数做一个判断就行
至于怎们建这棵树也很简单,看下这个list内容和index,再看看这棵树,可以发现一个规律就是,假定节点位置为index,则左孩子就是2index+1,右孩子就是2index+2,这样就把二维的结构压缩成一个一维的结构了;
明白了这些构建就更简单了,从下往上构建,每一棵subTree建好都要确保节点是最大就行。
```python def heap_sort(lst): def adjust_heap(lst, i, size): left_index = 2 * i + 1 right_index = 2 * i + 2 largest_index = i if left_index < size and lst[left_index] > lst[largest_index]: largest_index = left_index if right_index < size and lst[right_index] > lst[largest_index]: largest_index = right_index if largest_index != i: lst[largest_index], lst[i] = lst[i], lst[largest_index] adjust_heap(lst, largest_index, size) def built_heap(lst, size): for i in range(len(lst) // 2)[::-1]: adjust_heap(lst, i, size) size = len(lst) built_heap(lst, size) print_list(lst) print() for i in range(len(lst))[::-1]: lst[0], lst[i] = lst[i], lst[0] adjust_heap(lst, 0, i) if i != 0: print_list(lst) print() return lst def print_list(lst): for i in range(0, len(lst)): print(lst[i], end=" ") number_count = eval(input()) number_list = input().split() number_list = [eval(i) for i in number_list] heap_sort(number_list)