Jak*_*man 5 sorting algorithm implementation
我知道大多数算法的实现,但我不知道使用它们的大小数据集(以及包含的数据):
首先,您采用所有具有O(n2)复杂性的排序算法并将其丢弃.
然后,您必须研究排序算法的几个特性,并确定它们中的每一个是否更适合您要解决的问题.最重要的是:
算法到位了吗？这意味着排序算法不使用任何(O(1)实际)额外内存.当您运行内存关键型应用程序时,这种适当性非常重要.
冒泡排序,插入排序和选择排序使用常量内存.Merge-sort也有一个就地变种.
算法稳定吗？这意味着,如果两个元素x和y是相等的给定的比较方法,和在输入x之前发现y,则在输出x将被发现之前y.
合并排序,冒泡排序和插入排序是稳定的.
算法可以并行化吗？如果您正在构建的应用程序可以使用并行计算,则可能需要选择可并行化的排序算法.
更多信息在这里.
仅当要排序的数据存储在旋转鼓存储器中时才使用冒泡排序.它最适合此目的,但不适用于随机存取存储器.这些天,相当于"不使用冒泡排序".
使用插入排序或选择通过针对您可用的其他排序对其进行测试,可以对您确定的某种大小进行排序.这通常约为20-30项,但是YMMV.特别是,当实现像Merge Sort和Quick Sort这样的分而治之的排序时,当你当前的数据块足够小时,你应该"分解"为Insertion排序或Selection排序.
还可以对几乎排序的数据使用插入排序,例如,如果您以某种方式知道您的数据曾经被排序,并且自那以后没有太大变化.
当您需要稳定排序时使用合并排序(在排序链接列表时也很好),请注意对于数组,它使用大量额外内存.
通常你根本不使用"普通"快速排序,因为即使有明智的枢轴选择,它仍然是Omega(n^2)最糟糕的情况,但与插入排序不同,它没有任何有用的最佳情况."杀手级"案例可以系统地构建,因此如果您对"不受信任"的数据进行排序,那么某些用户可能会故意扼杀您的性能,无论如何,可能存在某些特定于域的原因导致您的数据接近杀手级案例.如果您选择随机枢轴,那么杀手案例的概率可以忽略不计,因此这是一个选项,但通常的方法是"IntroSort" - 一个检测坏情况并切换到HeapSort的QuickSort.
Radix Sort有点奇怪.很难找到最好的常见问题,但它对固定宽度数据有很好的渐近限制(O(n)比较排序的地方Omega(n log n)).如果您的数据是固定宽度的,并且输入大于可能值的数量(例如,超过40亿个32位整数),则开始有可能某些基数排序将表现良好.