我正在尝试在 Python 中实现堆排序，但我似乎做不好。我试图实现这个 pseudo code ，但我的代码没有排序!它只是过滤到荒谬的效果。我倾向于认为问题出在这一行:

swap the root(maximum value) of the heap with the last element of the heap

如何获得最大值？

这就是我所拥有的:

def my_heap_sort(sqc):                    
    def heapify(count):                
        start = (count-2)/2            
        while start >= 0:              
            sift_down(start, count-1)  
            start -= 1                 

    def swap(i, j):                    
        sqc[i], sqc[j] = sqc[j], sqc[i]

    def sift_down(start, end):         
        root = start                   

        while (root * 2 + 1) <= end:   
            child = root * 2 + 1       
            temp = root                
            if sqc[temp] < sqc[child]: 
                temp = child+1         
            if temp != root:           
                swap(root, temp)       
                root = temp            
            else:                      
                return                 

    count = len(sqc)                   
    heapify(count)                     

    end = count-1                      

    while end > 0:                     
        swap(end, 0)                   
        end -= 1                       
        sift_down(0, end)              

我发现了一个问题几乎相同的例子:

def heap_sort_example(a):                                 
    def heapify(a):                                       
        start = (len(a) - 2) / 2                          
        start -= 1                                        

    def sift_down(a, start, end):                         
        root = start                                      
        while root * 2 + 1 <= end:                        
            child = root * 2 + 1                          
            if child + 1 <= end and a[child] < a[child+1]:
                child += 1                                
            if child <= end and a[root] < a[child]:       
                a[root], a[child] = a[child], a[root]     
                root = child                              
            else:                                         
                return                                    

    heapify(a)                                            
    end = len(a) - 1                                      
    while end > 0:                                        
        a[end], a[0] = a[0], a[end]                       
        sift_down(a, 0, end-1)                            
        end -= 1                                          

结果是不同的，但都是荒谬的:

>>> my_heap_sort(sqc)
[2, 7, 1, -2, 56, 5, 3]

>>> heap_sort_example(sqc)
[-2, 1, 7, 2, 56, 5, 3]

最佳答案

我如何获得最大值？您不需要“获得”它。根正好是最大值，这是堆的定义属性。

如果你觉得很难理解堆排序，this chapter将非常有帮助。

我重写了你的代码:

def swap(i, j):                    
    sqc[i], sqc[j] = sqc[j], sqc[i] 

def heapify(end,i):   
    l=2 * i + 1  
    r=2 * (i + 1)   
    max=i   
    if l < end and sqc[i] < sqc[l]:   
        max = l   
    if r < end and sqc[max] < sqc[r]:   
        max = r   
    if max != i:   
        swap(i, max)   
        heapify(end, max)   

def heap_sort():     
    end = len(sqc)   
    start = end // 2 - 1 # use // instead of /
    for i in range(start, -1, -1):   
        heapify(end, i)   
    for i in range(end-1, 0, -1):   
        swap(i, 0)   
        heapify(i, 0)   

sqc = [2, 7, 1, -2, 56, 5, 3]
heap_sort()
print(sqc)

它给出:

[-2, 1, 2, 3, 5, 7, 56]  

关于python - 堆排序 : how to sort?，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13979714/