堆排序的宗旨是：建立一个最大堆，然后堆顶元素为最大元素，依次将堆顶元素放在列表最后，即将第一个元素与最后一个元素交换，交换之后剩余部分再堆排序，直到只剩堆顶。
难点：如何建立最大堆：将列表元素标号，则最大堆满足，k(i)>=k(2i+1),k(i)>=k(2i+2),根据这个规则，从有叶子节点开始，从下往上依次选最大的放堆顶。
堆排序也是一个不稳定排序，其时间复杂度为O(nlogn),空间复杂度为O(1)
def heap_sort(nums): size=len(nums) build_heap(nums,size) for i in range(size-1,-1,-1): nums[0],nums[i]-nums[i],nums[0] adjust_heap(nums,0,i) def build_heap(nums,size): for i in range(size//2-1,-1,-1): adjust_heap(nums,i,size) def adjust_heap(nums,i,size): left=2*i+1 right=left+1 max=i if i<size/2: if left<size and nums[max]<nums[left]: max=left if right<size and nums[right]>nums[max]: max=right if max!=i: nums[max],nums[i]=nums[i],nums[max] adjust_heap(nums,max,size)