排序二、堆排序

image
*图片演示的是大根堆-升序排列的情况，本文代码是小根堆-降序排列，思想是一样的

时间复杂度：O（nlogn）
空间复杂读：O（1）
不稳定排序

代码中，heapdown用于构造小根堆
heap_sort首先构造小根堆，然后交换首尾元素（则尾元素最小），再对余下元素构造小根堆，循环即可

        # 堆排序
        # 小根堆降序
        def heapdown(self, elems, begin, end):
            i, j = begin, begin * 2 + 1  # j为i的左子结点
            while j < end:
                # 让j指向子节点中小的那个
                if j + 1 < end and elems[j] > elems[j + 1]:
                    j += 1
                # 比较父节点和子节点的大小，父节点小则不需要再调动，父节点大交换父节点和子节点
                if elems[i] > elems[j]:
                    elems[i], elems[j] = elems[j], elems[i]
                    print('swap--', elems)
                i, j = j, j * 2 + 1

        def heap_sort(self, elems):
            end = len(elems)
            # 初始化，构造小根堆
            for i in range(end//2-1, -1, -1):  # 构造堆序。
                # print(i)
                self.heapdown(elems, i, end)
            # print(elems)
            # 交换堆顶和最后一个元素，余下元素再构造小根堆
            for i in range((end-1), 0, -1):  # 进行堆排序.i最后一个值为1，不需要到0
                print(elems)
                elems[i],elems[0] = elems[0],elems[i]
                self.heapdown(elems, 0, i)

            return elems

*自己写给自己看的博客
*文章内容不保证正确
*部分内容来源于网络，侵删
今天也是元气满满的一天哦~~
冲鸭~~QWQ