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

• 稳定(不更改具有相同键的元素的相对顺序。)
• 就地或者几乎就地(O(log n)堆栈都可以，但是没有O(n)空间使用或者堆分配。
• O(n log n)时间复杂度。

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

显而易见，有一个基本算法可以匹配这三个中的任意两个(插入排序匹配1和2，合并排序匹配1和3，堆排序匹配2和3)，但是我一生都找不到任何符合所有这三个条件。

解决方案

快排序呢？

Exchange也可以做到这一点，按照说法可能更"稳定"，但是quicksort更快。

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

也许壳排序？如果我正确地回忆起我的数据结构过程，它趋于稳定，但更糟糕的是时间为O(n log ^ 2 n)，尽管它对几乎排序的数据执行O(n)。它基于插入排序，因此可以就位排序。

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

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

注意：标准快速排序不是O(n log n)！在最坏的情况下，它可能需要O(n ^ 2)的时间。问题是我们可能会选择远离中位数的元素，从而使递归调用高度不平衡。

有一种解决方法，那就是仔细选择一个保证或者至少非常可能接近该中间值的中间值。令人惊讶的是，我们实际上可以找到线性时间的确切中位数，尽管在情况下，这听起来像我们在乎速度，所以我不建议这样做。

我认为最实用的方法是实施稳定的快速排序(很容易保持稳定)，但将5个随机值的中位数用作每一步的关键。这使得我们排序缓慢且稳定的可能性很小。

顺便说一句，合并排序可以就地完成，尽管就地和稳定都很难。

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

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

在我们可以证明它很重要之前，不必担心O(n log n)。如果我们可以找到常数大大降低的O(n ^ 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; 
}

只要排序仅执行元素交换，该技术就可以使任何排序稳定。元素的索引将更改，但是相同元素的相对顺序将保持不变，因此排序仍然很可靠。对于像堆排序这样的排序，它不能开箱即用，因为原始的堆化会"抛弃"相对的顺序，尽管我们可能可以将其改编为其他类型。

通过将序列字段添加到每个记录，在排序之前将其初始化为索引并将其用作排序键的最低有效部分，可以使Quicksort变得相当稳定稳定。

这对所花费的时间有轻微的不利影响，但不影响算法的时间复杂度。每条记录的存储成本开销也最小，但是这很少要紧，直到我们获得大量记录(并在记录量更大时被最小化)。

我将这种方法与C的qsort()函数一起使用，以避免编写自己的方法。每个记录都有一个32位整数，并在调用qsort()之前填充起始序列号。

然后比较功能检查键和顺序(这确保没有重复的键)，从而将快速排序转变为稳定的排序。我记得对于我正在使用的数据集，它仍然优于固有稳定的mergesort。

里程可能会有所不同，因此请始终记住：量度，不要猜测！

也许我有点发情，但是我喜欢手工编码的合并排序。它简单，稳定且行为良好。它需要的额外临时存储空间仅为N * sizeof(int)，这还不错。

维基百科上有一个很好的排序功能列表，可以找到想要的任何类型的排序功能。

例如，要解决特定问题，就好像我们想要的是就地合并排序。

但是，我们可能还想看一下链排序，它具有一些非常有趣的属性。

通过在链接列表上进行操作，可以使Quicksort变得稳定。这花费n来选择3个枢轴的随机值或者中值，但常数很小(遍历列表)。

通过拆分列表并确保对左侧列表进行排序，使相同的值向左移动，对右侧列表进行排序，使相同的值向右移动，排序将隐式稳定，而不会产生任何实际额外成本。另外，由于这是处理分配而不是交换，因此我认为速度实际上可能比对数组进行快速排序要好一些，因为只有一次写入。

因此，总而言之，列出所有项目并在列表上运行quicksort