Cul*_*lex 5 c sorting algorithm computer-science
我已经看到很多问题,询问quicksort或mergesort是否"更好",以及何时使用它们,但我想看到的是关于何时使用它们关于数据大小的一些输入排序.假设我有很多项目,无论是整数还是自定义对象.我把这些物品分类.
在某种程度上,我认为mergesort是每个步骤中快速排序(选择中位数作为枢轴)的最佳情况,但有一些开销.因此,在某个大小的情况下,当与mergesort的一致最优性质相比,开销可以忽略不计时,使用它来支持quicksort是有意义的.
基数排序具有"线性"运行时,因为被排序的键的位数不接近被排序的单独项的数量.但是,根据我的知识,基数排序在运行时也有一个相对较大的常量.
如果我从过去的一些测试中回忆起来,当被分类的项目数量开始数以百万计,并且基数高达数百万/亿的范围时,使用mergesort是有意义的.
我在这些评估中是否合理准确？有人可以在某种程度上确认,否认或纠正它们吗？
(我说的是每种类型的'简单'实现.而且,在基数排序的情况下,假设最大的单个键不大于被分类的项目数的两倍.即排序4,000,000个项目,最大可能的关键是8,000,000)
编辑 - 我想在通用数字范围上输入一些给定排序最快的输入.我在问题中提供了一些,这可能是一个错误.我想在答案中看到的是对数字范围的看法.我知道quicksort往往是默认的,因为它通常"足够好"并且没有合并的空间复杂性,并且没有用有意识的大键(基数)有目的地制造恶意数据的担心.