用python实现堆排序

一、概念

堆排序，顾名思义，就是基于堆。因此先来介绍一下堆的概念。 
堆分为最大堆和最小堆，其实就是完全二叉树。最大堆要求节点的元素都要大于其孩子，最小堆要求节点元素都小于其左右孩子，两者对左右孩子的大小关系不做任何要求，其实很好理解。有了上面的定义，我们可以得知，处于最大堆的根节点的元素一定是这个堆中的最大值。其实我们的堆排序算法就是抓住了堆的这一特点，每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最大堆，依次类推，最终得到排序的序列。

二、示例代码

三、其步骤如下：

堆排序就是把堆顶的最大数取出, 
将剩余的堆继续调整为最大堆,具体过程在第二块有介绍,以递归实现 
剩余部分调整为最大堆后,再次将堆顶的最大数取出,再将剩余部分调整为最大堆,这个过程持续到剩余数只有一个时结束

#_*_coding:utf-8_*_
__author__ = 'Alex Li'
import time,random
def sift_down(arr, node, end):root = node#print(root,2*root+1,end)while True:# 从root开始对最大堆调整child = 2 * root +1  #left childif child  > end:#print('break',)breakprint("v:",root,arr[root],child,arr[child])print(arr)# 找出两个child中交大的一个if child + 1 <= end and arr[child] < arr[child + 1]: #如果左边小于右边child += 1 #设置右边为大if arr[root] < arr[child]:# 最大堆小于较大的child, 交换顺序tmp = arr[root]arr[root] = arr[child]arr[child]= tmp# 正在调整的节点设置为root#print("less1:", arr[root],arr[child],root,child)root = child ##[3, 4, 7, 8, 9, 11, 13, 15, 16, 21, 22, 29]#print("less2:", arr[root],arr[child],root,child)else:# 无需调整的时候, 退出break#print(arr)print('-------------')def heap_sort(arr):# 从最后一个有子节点的孩子还是调整最大堆first = len(arr) // 2 -1for i in range(first, -1, -1):sift_down(arr, i, len(arr) - 1)#[29, 22, 16, 9, 15, 21, 3, 13, 8, 7, 4, 11]print('--------end---',arr)# 将最大的放到堆的最后一个, 堆-1, 继续调整排序for end in range(len(arr) -1, 0, -1):arr[0], arr[end] = arr[end], arr[0]sift_down(arr, 0, end - 1)#print(arr)
def main():# [7, 95, 73, 65, 60, 77, 28, 62, 43]# [3, 1, 4, 9, 6, 7, 5, 8, 2, 10]#l = [3, 1, 4, 9, 6, 7, 5, 8, 2, 10]#l = [16,9,21,13,4,11,3,22,8,7,15,27,0]array = [16,9,21,13,4,11,3,22,8,7,15,29]#array = []#for i in range(2,5000):#    #print(i)#    array.append(random.randrange(1,i))print(array)start_t = time.time()heap_sort(array)end_t = time.time()print("cost:",end_t -start_t)print(array)#print(l)#heap_sort(l)#print(l)if __name__ == "__main__":main()

•