标签: heapsort

quicksort和heapsort都进行就地排序.哪个更好？什么是首选的应用程序和案例？

该堆排序排序算法似乎有O(nlogn)的最差情况的复杂性,并且使用O(1)排序操作空间.

这似乎比大多数排序算法更好.那么,为什么不总是使用Heap Sort作为排序算法(为什么人们使用排序机制,如Merge sort或Quick sort)？

此外,我看到人们使用Heap排序中的"不稳定"一词.这意味着什么？

在学校我们正在学习Java中的排序算法,而我的作业是Heap Sort.我做了我的阅读,我试图尽可能多地发现,但似乎我无法掌握这个概念.

我不是要求你给我写一个Java程序,如果你可以像Heap Sort那样简单地向我解释.

堆排序具有最差的情况复杂性,O(nlogn)而Quicksort O(n^2).但是,经验证据表明,快速排序是优越的.这是为什么？

作为Haskell的一个练习,我正在尝试实现heapsort.堆通常在命令式语言中实现为数组,但在纯函数式语言中这将是非常低效的.所以我看了二进制堆,但到目前为止我发现的所有内容都是从命令性的角度描述的,所提出的算法很难转化为功能设置.如何在Haskell等纯函数式语言中有效地实现堆？

编辑:通过有效我的意思是它应该仍然在O(n*log n),但它不必击败C程序.另外,我想使用纯函数式编程.在Haskell中做这件事还有什么意义呢？

我试图理解为什么heapsort不稳定.我用Google搜索了这个,但没有找到一个好的,直观的解释.

我理解稳定排序的重要性 - 它允许我们基于多个键进行排序,这可能是非常有益的(即,进行多个排序,每个排序基于不同的键.因为每种排序都将保留元素的相对顺序,以前的排序可以加起来给出按多个标准排序的元素的最终列表.但是,为什么heapsort也不会保留这个呢？

谢谢你的帮助!

我想知道是否允许最大或最小堆树具有重复值？我一直试图通过在线资源找到有关这方面的信息是不成功的.

众所周知,heapsort的最坏情况运行时为Ω(n lg n),但我很难理解为什么会这样.特别是,heapsort的第一步(制作最大堆)需要时间Θ(n).然后是n次删除.我理解为什么每个堆删除需要时间O(lg n); 重新平衡堆涉及一个向下泡沫的操作,它在堆的高度花费时间O(h),并且h = O(lg n).但是,我没有看到为什么第二步应该采用Ω(n lg n).似乎任何单个堆出列都不一定会导致节点移动到顶部以一直向下冒泡到树中.

我的问题是 - 有没有人知道heapsort的最佳案例行为的良好下限证明？

我需要在C中编写一个排序程序,如果文件可以在适当的位置排序以节省磁盘空间,那将是很好的.数据很有价值,所以我需要确保如果进程被中断(ctrl-c),文件没有被破坏.我可以保证机器上的电源线不会被拉扯.

额外细节:文件大约40GB,记录是128位,机器是64位,操作系统是POSIX

有关实现此目的的任何提示,或一般说明？

谢谢!

澄清一下:我希望用户想要ctrl-c进程.在这种情况下,我想要优雅地退出并确保数据是安全的.所以这个问题是关于处理中断和选择一个排序算法,如果请求可以快速包装.

跟进(2年后):为了后代,我已经安装了SIGINT处理程序,它运行良好.这不能保护我免受电源故障的影响,但这是我可以处理的风险.代码位于https://code.google.com/p/pawnsbfs/source/browse/trunk/hsort.c和https://code.google.com/p/pawnsbfs/source/browse/trunk/qsort.c

我正在尝试用Python实现Heap Sort,但我似乎无法做到正确.我试图实现这个伪代码,但我的代码没有排序!它只是筛选到荒谬的效果.我倾向于认为问题出在这一行:

将堆的根(最大值)与堆的最后一个元素交换

我如何获得最大值？

这就是我所拥有的:

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 …