sam*_*sam 157 sorting algorithm
当特定排序算法优于其他排序算法时,有什么用例 - __CODE__vs __CODE__vs __CODE__vs __CODE__等？
是否有基于数据结构的大小,类型,可用内存和缓存以及CPU性能使用它们的建议指南？
dsi*_*cha 292
首先,定义,因为它非常重要:稳定的排序是保证不用相同的键重新排序元素的排序.
建议:
快速排序: 当您不需要稳定的排序时,平均情况下的性能比最差情况下的性能更重要.快速排序平均为O(N log N),在最坏的情况下为O(N ^ 2).一个好的实现使用堆栈空间形式的O(log N)辅助存储进行递归.
合并排序: 当您需要稳定的O(N log N)排序时,这是您唯一的选择.唯一的缺点是它使用O(N)辅助空间并且具有比快速排序略大的常数.有一些就地合并排序,但AFAIK它们都不稳定或比O(N log N)更差.即使是O(N log N)就地排序也比普通的旧合并排序有更大的常数,它们比有用的算法更具理论上的好奇心.
堆排序: 当您不需要稳定排序时,您更关心最坏情况下的性能而不是平均情况.它保证为O(N log N),并使用O(1)辅助空间,这意味着在非常大的输入上不会意外地耗尽堆或堆栈空间.
Introsort: 这是一种快速排序,在某个递归深度之后切换到堆排序,以绕过快速排序的O(N ^ 2)最坏情况.它几乎总是比普通的快速排序更好,因为你得到了一个快速排序的平均情况,保证了O(N log N)性能.可能使用堆排序而不是使用堆排序的唯一原因是在严重的内存受限系统中,其中O(log N)堆栈空间实际上很重要.
插入排序:当N保证很小时,包括作为快速排序或合并排序的基本情况.虽然这是O(N ^ 2),但它具有非常小的常数并且是稳定的排序.
冒泡排序,选择排序:当你做一些快速而又脏的东西时,出于某种原因,你不能只使用标准库的排序算法.这些优于插入排序的唯一优势是稍微容易实现.
非比较排序: 在一些相当有限的条件下,可以打破O(N log N)障碍并按O(N)排序.以下是一些值得一试的案例:
计数排序: 当您对有限范围的整数进行排序时.
基数排序: 当log(N)明显大于K时,其中K是基数位数.
铲斗分类: 当您可以保证输入大致均匀分布时.
Eli*_*sky 26
Quicksort通常是平均速度最快的,但它有一些非常讨厌的最坏情况行为.因此,如果你必须保证没有错误的数据给你O(N^2),你应该避免它.
Merge-sort使用额外的内存,但特别适合外部排序(即不适合内存的大文件).
堆排序可以就地排序,并且没有最坏情况的二次行为,但在大多数情况下平均比快速排序慢.
如果只涉及限制范围内的整数,则可以使用某种基数排序来使其非常快.
在99%的情况下,您可以使用库排序,这通常基于快速排序.