本文共 2260 字，大约阅读时间需要 7 分钟。

#!coding=utf-8

交换函数，python中直接交换的引用，直接return 对方的引用即可

def swap(a,b):        return b,a

这个函数根据传进来的begin，按照一定规则可以实现将数组中的部分数”挂“到树上去，这个规则是父节点一定大于两个孩子节点

首先判断left<=end，树的结构我们都知道：已知父节点i，左孩子是2*i，右孩子是2*i+1，而实际排序中可能没有右孩子，除去第一个占位符，若数组中有14个元素，那么14/2 = ７, 这时只有左节点而没有右节点

left <= end，只是为了确定这个left节点是不是数组中的元素：不越界

def heap(arr,begin,end):        k=begin        left=2*k        while left<=end:                if left                        left+=1                        #print "left is : %s,k is : %s"%(left,k)                if arr[k]                        arr[k],arr[left]=swap(arr[k],arr[left])                else:                        break                k=left                left=left*2

建立堆的函数：来分析一下这个流程（假设这里有15个元素，从a[1] ~~ a[15]）

def buildheap(arr,n):        i=n/2        while i>=1:                heap(arr,i,n)                i-=1

　　可以看到，堆排序首先先用建堆，这个过程运行的同时得到最上面的元素a[1]最大，那么，我们就可以将最大的那个元素a[1]放到数组的最后一位a[15]，之后无论其他元素大小怎么样，总之a[15]成了最大的那个元素

　　那么剩下的就是一直执行类似建堆的过程了

　　经过上面那个过程可知：每一次最顶上的元素是最大的，我们将其换到末尾元素，末尾元素下表减１，这样一直到２，那么这个就变成了一个从小到达的有序数组了

def heapsort(arr,n):        buildheap(arr,n)        num=n        while num>1:                arr[1],arr[num]=swap(arr[1],arr[num])                num-=1                heap(arr,1,num)if __name__=='__main__':        arr1=[]        myfile=open('num.txt')        str=myfile.read()        for each in str.split():                each=int(each)                arr1.append(each) #　　这里是我们构造了一个新的数组，第一个元素a[0]是占位符        mylen=len(arr1)        print arr1        duiarr=[0]*16        index=1        while index<=mylen:                duiarr[index]=arr1[index-1]                index+=1        print "\n"        heapsort(duiarr,mylen)        print duiarr

主要还是看分析建堆过程，我之前一直以为这个代码是没有问题的，但是仔细去尝试，发现了代码中貌似是有一些多余的步骤，希望看过的朋友有意见随时指出来，代码仅供参考

还有一点坑爹的地方，开头我写的swap只是返回两个交换的引用，而没有执行进行交换，需要赋值才能使用，发现的时候我瞬间蒙逼了….希望以后不要再犯这种低级错误