稳定高效的排序算法？

Question

稳定高效的排序算法？

algorithmlanguage-agnosticdata-structuressorting

14

我正在尝试创建一种非常节省空间的不寻常的关联数组实现，需要一个满足以下所有条件的排序算法：

稳定（不改变具有相同键的元素的相对顺序）。
原地或几乎原地（O(log n)堆栈大小是可以接受的，但不能使用O(n)空间或堆分配）。
O(n log n)时间复杂度。

还要注意，要排序的数据结构是一个数组。

很容易看出，存在基本算法可以匹配其中任意两个条件（插入排序符合1和2，归并排序符合1和3，堆排序符合2和3），但我却找不到任何符合这三个条件的算法。

- dsimcha

1

你的数据是否会定期更新？如果是，那么将所有数据放入一个巨大的数组中是不明智的。考虑使用可以分段的结构，例如B树或Rope。 - finnw

似乎很奇怪，对于O(n log n)的时间复杂度感到满意，但对于O(n)的空间使用有问题。您能详细说明一下您的实际目标是什么吗？有可能您正在陷入XY问题陷阱中。 - mikera

13个回答

9

注意：标准快速排序算法并不是O(n log n)！在最坏的情况下，它可能需要O(n^2)的时间。问题在于你可能选择了远离中位数的元素作为枢轴，使得递归调用高度不平衡。

有一种方法可以解决这个问题，就是仔细选择一个被保证或至少非常可能接近中位数的中位数。令人惊讶的是，你实际上可以在线性时间内找到确切的中位数，但在你的情况下，我不建议这样做，因为你关心速度。

我认为最实用的方法是实现一个稳定的快速排序（很容易保持稳定），但在每个步骤中使用5个随机值的中位数作为枢轴。这使得你几乎不可能有慢速排序，并且是稳定的。

顺便说一下，归并排序可以原地进行，尽管同时进行原地和稳定排序有些棘手。

- Tyler

1

《算法基础》第237页介绍了一种使快速排序的时间复杂度达到O(n log n)的方法，除非所有元素都相同。它递归地选择中位数作为枢轴，并返回已经进行过快速排序的列表，然后再进行递归操作。话虽如此，我认为在五个元素中选择中位数是最好的方法。 - Michael Deardeuff

3

快速排序怎么样？

Exchange也可以做到这一点，按照您的术语可能更“稳定”，但快速排序速度更快。

- davenpcj

1

在http://en.wikipedia.org/wiki/Quicksort#Algorithm中给出的示例是稳定的，尽管它不是qsort最有效的版本。 - freespace

据我所知，快速排序的变种可以使其稳定或高效，但不能同时兼备。 - cjm

3

在维基百科上有一份排序算法列表。它包括按执行时间、稳定性和分配方式分类。

最好的方法可能是修改一个高效但不稳定的排序算法，使其变得稳定，从而降低其效率。

- davenpcj

2

快速排序可以通过在链表上进行来实现稳定性。这会花费n来选择随机或中位数的3个枢轴，但代价非常小（列表遍历）。

通过分割列表并确保左侧列表已排序，所以相同值向左走，右侧列表已排序，所以相同值向右走，排序将隐式地稳定，而没有真正额外的成本。此外，由于这处理的是赋值而不是交换，我认为速度可能比对数组进行快速排序要稍微快一点，因为只有一个写入。

因此，总之，列出所有项目并在列表上运行快速排序。

- nik3daz

2

有一类稳定的原地归并算法，虽然它们很复杂且线性时间复杂度下常数较高（O(n)），但是你可以阅读这篇文章以及它的参考文献来了解更多相关知识。

编辑：归并阶段是线性的，因此归并排序的时间复杂度是nlog_n。

- Rafał Dowgird

2

通过为每个记录添加一个序列字段，将其初始化为排序之前的索引，并将其用作排序键的最低有效部分，可以相对容易地使快速排序保持稳定性。

这会略微影响所需的时间，但不会影响算法的时间复杂度。对于每个记录来说，它还需要一些额外的存储成本开销，但在记录数量很大时才会对性能产生实际影响（并且在更大的记录大小下可以最小化此成本）。

我使用了这种方法，通过为每个记录添加一个32位整数并在调用C语言中的qsort()函数之前用起始序列号填充它，避免编写自己的排序算法。

接着比较函数检查键值和序列号（这样可以确保没有重复的键值），将快速排序转变为稳定排序。我记得，对于我正在处理的数据集，它仍然优于内置的稳定归并排序算法。

由于数据情况各异，因此请永远记住：量入为出，不要臆测！

- Pax

2

由于您的元素是在一个数组中（而不是链表），因此您可以利用数组索引本身来获得有关它们原始顺序的一些信息。您可以通过编写排序和比较函数使它们意识到这一点来利用它：

function cmp( ar, idx1, idx2 )
{
   // first compare elements as usual
   rc = (ar[idx1]<ar[idx2]) ? -1 : ( (ar[idx1]>ar[idx2]) ? 1 : 0 );

   // if the elements are identical, then compare their positions
   if( rc != 0 )
      rc = (idx1<idx2) ? -1 : ((idx1>idx2) ? 1 : 0);

   return rc; 
}

只要排序算法仅涉及元素交换，此技术即可用于使任何类型的排序稳定。元素的索引将会改变，但相同元素的相对顺序将保持不变，因此排序算法仍然是鲁棒的。这种技术无法直接用于像堆排序这样的排序算法，因为原始堆化操作“抛弃”了元素之间的相对顺序，尽管您可能能够将此想法应用于其他排序算法。

- Eric

我也打算提出同样的建议。 - Konrad Rudolph

1

这并不适用于所有算法。排序可能会将a_1与某个b进行比较，导致它相对于它们之间的某个a_2被交换。你可能可以在某些情况下使用它，但你需要承担沉重的证明责任。 - wnoise

1

这里有一个很好的排序函数在维基百科上，可以帮助你找到任何类型的排序函数。

例如，针对你的具体问题，似乎原地归并排序是你想要的。

然而，你也可能想看看串排序，它具有一些非常有趣的特性。

- ReaperUnreal

1

在你能够证明它很重要之前，不要过于担心O(n log n)。如果你能找到一个具有极低常数的O(n^2)算法，那就采用它！

通常最坏情况并不相关，如果数据高度受限。

简而言之：进行一些测试。

- phyzome

2

总的来说，我同意phyzome的观点，除非N有很大的机会变得很大，否则大O并不重要。然而，我正在尝试编写一个空间高效的关联数组，以适应大量数据在RAM中存储，所以整个重点是N非常巨大。 - dsimcha

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jjnguy · Accepted Answer

我相信归并排序可以写成原地算法，这可能是最好的方法。