14

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

  1. 稳定（不更改具有相同键的元素的相对顺序。）
  2. 就地或几乎就地（O(log n) 堆栈很好，但没有 O(n) 空间使用或堆分配。
  3. O(n log n) 时间复杂度。

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

很容易看出，有一个基本算法可以匹配这三个中的任何 2 个（插入排序匹配 1 和 2，合并排序匹配 1 和 3，堆排序匹配 2 和 3），但我一生都找不到任何符合所有这三个条件。

4

13 回答 13

10

我相信合并排序可以写成就地。这可能是最好的路线。

于 2008-09-22T03:25:40.060 回答
9

注意：标准快速排序不是O(n log n) ！在最坏的情况下，它可能需要 O(n^2) 时间。问题是您可能会以远离中位数的元素为中心，因此您的递归调用非常不平衡。

有一种方法可以解决这个问题，即仔细选择一个可以保证或至少很可能接近中位数的中位数。令人惊讶的是，您实际上可以在线性时间内找到确切的中位数，尽管在您的情况下，这听起来像是您关心速度，所以我不建议这样做。

我认为最实用的方法是实现一个稳定的快速排序（它很容易保持稳定），但使用5 个随机值的中值作为每一步的枢轴。这使得您不太可能进行缓慢的排序，并且是稳定的。

顺便说一句，归并排序可以在原地完成，尽管在原地和稳定的情况下都很难。

于 2008-09-22T04:14:33.093 回答
3

快速排序呢？

Exchange 也可以这样做，按照您的条款可能更“稳定”，但快速排序更快。

于 2008-09-22T03:25:36.363 回答
3

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

您最好的选择可能是将有效的不稳定排序修改为稳定，从而降低其效率。

于 2008-09-22T04:07:14.190 回答
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; 
}

只要排序只执行元素交换，此技术可用于使任何排序稳定。元素的索引会改变，但相同元素的相对顺序将保持不变，因此排序保持稳健。对于像 heapsort 这样的排序，它不会开箱即用，因为原始的 heapification “丢弃”了相对排序，尽管您可以将这个想法应用于其他排序。

于 2008-10-04T14:26:01.060 回答
2

有一类稳定的就地合并算法，尽管它们复杂且线性，在 O(n) 中隐藏了相当高的常数。要了解更多信息，请查看这篇文章及其参考书目。

编辑：合并阶段是线性的，因此合并排序是 nlog_n。

于 2008-09-22T08:32:47.967 回答
2

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

通过拆分列表并确保对左列表进行排序，使相同的值向左，对右列表进行排序，使相同的值向右，排序将是隐式稳定的，没有真正的额外成本。此外，由于这涉及分配而不是交换，因此我认为速度实际上可能比对数组的快速排序稍好一些，因为只有一次写入。

所以总而言之，列出所有项目并在列表上运行快速排序

于 2009-11-04T16:51:29.603 回答
2

Quicksort can be made stable reasonably easy simply by having an sequence field added to each record, initializing it to the index before sorting and using it as the least significant part of the sort key.

This has a slightly adverse effect on the time taken but it doesn't affect the time complexity of the algorithm. It also has a minimal storage cost overhead for each record, but that rarely matters until you get very large numbers of records (and is mimimized with larger record sizes).

I've used this method with C's qsort() function to avoid writing my own. Each record has a 32-bit integer added and populated with the starting sequence number before calling qsort().

Then the comparison function checked the keys and the sequence (this guarantees there are no duplicate keys), turning the quicksort into a stable one. I recall that it still outperformed the inherently stable mergesort for the data sets I was using.

Your mileage may vary, so always remember: Measure, don't guess!

于 2009-02-25T11:16:22.917 回答
1

在你能证明它很重要之前，不要太担心 O(n log n)。如果你能找到一个常数大大降低的 O(n^2) 算法，那就去吧！

如果您的数据受到高度限制，则一般最坏的情况是不相关的。

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

于 2008-09-23T15:15:03.670 回答
1

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

例如，为了解决您的特定问题，看起来就地合并排序是您想要的。

但是，您可能还想看看strand sort，它有一些非常有趣的属性。

于 2009-08-17T20:04:02.217 回答
1

我已经实现了一个稳定的就地快速排序和一个稳定的就地合并排序。合并排序要快一点，并且保证在 O(n*log(n)^2) 中工作，但不是快速排序。两者都使用 O(log(n)) 空间。

于 2011-12-09T15:11:04.877 回答
0

也许是shell 排序？如果我正确回忆我的数据结构课程，它往往是稳定的，但更糟糕的情况是时间是 O(n log^2 n)，尽管它对几乎排序的数据执行 O(n)。它基于插入排序，所以它就地排序。

于 2008-09-22T03:27:44.970 回答
0

也许我有点墨守成规，但我喜欢手工编码的合并排序。它简单、稳定且表现良好。它需要的额外临时存储只有N*sizeof(int)，还不错。

于 2009-08-17T19:44:33.347 回答