稳定，高效排序？ [英] Stable, efficient sort?

问题描述

我试图创造一个不同寻常的关联数组实现，这是非常节省空间的，我需要一个排序算法，以满足所有的以下内容：

I'm trying to create an unusual associative array implementation that is very space-efficient, and I need a sorting algorithm that meets all of the following:

1. 在稳定（不改变同键元素的相对顺序。）
2. 在就地或几乎就地（O（log n）的协议栈是好的，但没有O（n）的空间使用率或堆分配。
3. 为O（n log n）的时间复杂度。

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

Also note that the data structure to be sorted is an array.

可以很容易地看到，有一个基本的算法匹配任意2这三个（插入排序匹配1和2，归并排序匹配1和3，堆排序匹配2和3），但我不能为我的生活找到任何匹配所有这三个标准。

It's easy to see that there's a basic algorithm that matches any 2 of these three (insertion sort matches 1 and 2, merge sort matches 1 and 3, heap sort matches 2 and 3), but I cannot for the life of me find anything that matches all three of these criteria.

推荐答案

合并排序可以写为就地我相信。这可能是最好的途径。

Merge sort can be written to be in-place I believe. That may be the best route.

这篇关于稳定，高效排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！