代码
#coding:utf-8 #author:徐卜灵 # 堆排序适用于记录数很多的情况 #与快速排序，归并排序 时间复杂一样都是n*log（n） #################################################### #################################################### #################################################### # from collections import deque # # # 这里需要说明元素的存储必须要从1开始 # # 涉及到左右节点的定位，和堆排序开始调整节点的定位 # # 在下标0处插入0，它不参与排序 # L = deque([49,38,65,97,76,13,27,49]) # L.appendleft(0) # # #L = [0,49,38,65,97,76,13,27,49] # # def element_exchange(numbers,low,high): # # temp = numbers[low] # # # j 是low的左孩子节点(cheer!) # i = low # j = 2*i # # while j<=high: # # 如果右节点较大，则把j指向右节点 # if j<high and numbers[j]<numbers[j+1]: # j = j+1 # if temp<numbers[j]: # # 将numbers[j]调整到双亲节点的位置上 # numbers[i] = numbers[j] # i = j # j = 2*i # else: # break # # 被调整节点放入最终位置 # numbers[i] = temp # # def top_heap_sort(numbers): # # length = len(numbers)-1 # # # 指定第一个进行调整的元素的下标 # # 它即该无序序列完全二叉树的第一个非叶子节点 # # 它之前的元素均要进行调整 # # cheer up！ # first_exchange_element = length/2 # # #建立初始堆 # print first_exchange_element # for x in range(first_exchange_element): # element_exchange(numbers,first_exchange_element-x,length) # # # 将根节点放到最终位置，剩余无序序列继续堆排序 # # length-1 次循环完成堆排序 # for y in range(length-1): # temp = numbers[1] # numbers[1] = numbers[length-y] # numbers[length-y] = temp # element_exchange(numbers,1,length-y-1) # # if __name__=='__main__': # top_heap_sort(L) # LL = [] # for x in range(1,len(L)): # # print L[x], # LL.append(L[x]) # print LL ############################################## ############################################## ############################################## def build_maxheap(L,len): for i in range(len/2,0,-1): # print i adjustdown(L,i,len) return L def adjustdown(L,low,high): #这里只是把一个位于low位置上的数向下移动。 temp = L[low] i = low j = 2 * i while j <= high: # if j <= high and L[j] < L[j+1]:#z这里的L[j+1]可能不存在，所有会有out of index 报错. # j+=1 if j <= high and j + 1 <= high: if L[j] < L[j+1]: j+=1 if L[j]>temp: L[i] = L[j] i = j j = 2 * i else: break L[i] = temp # return L #由于这里是中间列表，不要输出。 # print L # L = [0,49,38,65,97,76,13,67,47] # L = build_maxheap(L,8) # del L[0] # # print type(L) # print "大根堆第一次：",L len = len(L)-1 def Heap_sort(L,len): build_maxheap(L,len) for i in range(len,1,-1): L[i],L[1] = L[1],L[i] # print i # print L[len],L[1] adjustdown(L,1,i-1) return L L = [49,38,65,97,76,13,67,47] print "原列表：" ,L L.insert(0,0) L = Heap_sort(L,len) del L[0] print "堆排序：",L #基本思路是： # 1先从后到前进行小数下移的操作。这个后是指len（L）/2 #2.第一步完成后，最大的那个数就上移到了根节点。把这个根节点与最后一个元素交换位置，这时最后一个元素就在有序区里。则只需要将第一个元素再进行下移操作即可。 #3.循环第二步，直到只剩下根节点。
堆排序真的是排序算法中我花费时间最多的算法了，最开始是理解原理上出了问题。理解了之后写代码又出了问题。
对于二叉树不是很熟的最好复习一下树的知识。
理解了之后就能很好的写代码了。
思路：
1.从len(L)/2 到1开始，建立大根堆。这里需要注意的是：这里的元素并不是一次就能移动到最终的位置的。只有迭代到第一个元素，才能建立一个大根堆。
2.将堆顶元素与无序区最后一个元素交换位置，破坏了大根堆，则重新建立大根堆。
3.迭代第二步，直到只剩下一个元素。
时间复杂度：O（nlogn）
空间复杂读：O（nlogn）
跟快排是一样的。
堆排序也是不稳定的排序方法，这一定要搞清楚。