python实现的堆排序算法代码

python实现的堆排序算法代码

def heapSort(a): 
    def sift(start, count): 
        root = start 
   
        while root * 2 + 1 < count: 
            child = root * 2 + 1 
            if child < count - 1 and a[child] < a[child + 1]: 
                child += 1 
            if a[root] < a[child]: 
                a[root], a[child] = a[child], a[root] 
                root = child 
            else: 
                return 
   
    count = len(a) 
    start = count / 2 - 1 
    end = count - 1 
   
    while start >= 0: 
        sift(start, count) 
        start -= 1 
   
    while end > 0: 
        a[end], a[0] = a[0], a[end] 
        sift(0, end) 
        end -= 1 
   
a = [-8,0,1,3,11,35,68] 
heapSort(a) 
print a # [-8, 0, 1, 3, 11, 35, 68]
 

Recursive sift(and more readable IMHO) Version:

def heapsort(a): 
   
    def swap(a,i,j): 
        tmp = a[i] 
        a[i] = a[j] 
        a[j] = tmp   
           
    def siftdown(a, i, size): 
        l = 2*i+1 
        r = 2*i+2 
        largest = i 
        if l <= size-1 and a[l] > a[i]: 
            largest = l 
        if r <= size-1 and a[r] > a[largest]: 
            largest = r 
        if largest != i: 
            swap(a, i, largest) 
            siftdown(a, largest, size) 
               
    def heapify(a, size): 
        p = (size/2)-1 
        while p>=0: 
            siftdown(a, p, size) 
            p -= 1 
               
    size = len(a)         
    heapify(a, size) 
    end = size-1 
    while(end > 0): 
        swap(a, 0, end) 
        siftdown(a, 0, end) 
        end -= 1 

标签： swap 代码

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。