我有一个值数组，几乎但不是完全排序，有一些值被替换（例如，100000 中有 50 个）。如何最有效地排序？（性能在这里绝对至关重要，应该比 O(N) 快得多）。
我知道smoothsort，但我找不到Java 实现。有谁知道它是否已经实施？或者我可以用什么来代替smoothsort？
问问题
12251 次
10 回答
19
实际上，维基百科包含一个平滑排序的 Java 实现。你可以在这里找到它：
于 2009-09-07T20:23:46.900 回答
10
鸡尾酒排序
如果你想要一个易于实现的简单算法，你可以做一个鸡尾酒排序。它在几乎排序的输入上工作得相当好。
于 2009-09-07T20:32:53.597 回答
7
正如 Botz3000 所指出的，您无法比 O(N) 更快地执行此类操作。任何算法的最基本元素都是在数组中找到那些乱序的条目。这需要 O(N)，甚至在你弄清楚如何处理它们之前。
如果确实“无序”元素的数量比元素总数低几个数量级，则可以使用以下算法（假设链表）：
- 找出所有乱序项，并从原始列表中提取到一个单独的列表中，O(N)
- 结果是两个列表：排序列表和提取的简短列表
- 对于每个提取的元素，将它们插入到排序列表中。每个都是 O(log(N))，总计是 O(Xlog(N))，其中 X 是提取元素的数量。如果 X 相对于 N 非常小，那么最终的总和为 O(N)。
于 2009-09-07T20:23:15.723 回答
6
有很多很好的算法。
Smoothsort 是我个人最喜欢的……如果你好奇它为什么这么好用，我实际上已经把所有的数学都计算出来了。
对于已经排序的数据，一个相当好的算法是自然归并排序，它是归并排序的自下而上版本，其工作原理是将输入视为排序的子范围序列，然后在范围上进行多次遍历，合并相邻的排序范围。如果数据已经排序（因为它可以检测到只有一个排序范围），它会在 O(n) 时间内运行，在最坏的情况下运行 O(n lg n)。如果数据是“块排序”的，这个算法效果很好；也就是说，它由许多彼此相邻放置的排序块组成。
直接插入排序绝对适用于大多数排序的数据，但在大量输入上可能会非常糟糕地退化。一些非常好的排序（如introsort）实际上使用插入排序的这个属性来对输入进行“清理步骤”。
于 2010-11-09T07:09:20.210 回答
4
[Sun] JDK7 已经（或将要）实现Tim 排序（来自 Python）。这是一种利用数组中已经存在的顺序的合并排序。
于 2009-09-07T20:58:51.807 回答
3
Smoothsort 或 Timsort 是很棒的算法，使用起来很明智。
我要补充一点，您可能没有意识到卑微的插入排序是自适应的。确实，对于真正几乎排序的列表，正如您似乎拥有的那样，我的理解（我无法通过参考支持）是它比更复杂的算法更快。问题是，如果输入不是几乎排序的，它会迅速降级到 O(n^2)。尽管如此，正确实现它还是非常简单的，所以如果你确定你的输入总是几乎排序的，那将是一个不错的选择。
于 2009-11-21T18:10:16.343 回答
2
只是把它放在桌面上，一个良好实现的冒泡排序肯定是这里最简单的算法。在 O(n*m) 的最坏情况下，m 是位移的数量。m 部分很大程度上取决于位移的模式，通常总复杂度为 O(n)。
于 2009-09-07T20:35:42.020 回答
0
你说的不可能达到 O(N) 是对的，但是假设一台多核机器（我有），我们可以通过使用并行排序算法来作弊。
于 2009-09-07T20:35:53.923 回答
0
实现我们在学校所说的Shell 的排序。那是冒泡排序子数组。具有步长 k 的子数组是具有索引 0、k、2k、3k...的元素数组
如果你选择k = 3i+1，并执行多个冒泡排序，从高到0，几乎排序的数组的时间会更小。
于 2009-09-07T20:55:10.550 回答
0
这是以前可通过Wikipedia 文章获得的 Smoothsort 的原始 Java 实现。
// by keeping these constants, we can avoid the tiresome business
// of keeping track of Dijkstra's b and c. Instead of keeping
// b and c, I will keep an index into this array.
static final int LP[] = { 1, 1, 3, 5, 9, 15, 25, 41, 67, 109,
177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529, 21891,
35421, 57313, 92735, 150049, 242785, 392835, 635621, 1028457,
1664079, 2692537, 4356617, 7049155, 11405773, 18454929, 29860703,
48315633, 78176337, 126491971, 204668309, 331160281, 535828591,
866988873 // the next number is > 31 bits.
};
public static <C extends Comparable<? super C>> void sort(C[] m,
int lo, int hi) {
int head = lo; // the offset of the first element of the prefix into m
// These variables need a little explaining. If our string of heaps
// is of length 38, then the heaps will be of size 25+9+3+1, which are
// Leonardo numbers 6, 4, 2, 1.
// Turning this into a binary number, we get b01010110 = 0x56. We represent
// this number as a pair of numbers by right-shifting all the zeros and
// storing the mantissa and exponent as "p" and "pshift".
// This is handy, because the exponent is the index into L[] giving the
// size of the rightmost heap, and because we can instantly find out if
// the rightmost two heaps are consecutive Leonardo numbers by checking
// (p&3)==3
int p = 1; // the bitmap of the current standard concatenation >> pshift
int pshift = 1;
while (head < hi) {
if ((p & 3) == 3) {
// Add 1 by merging the first two blocks into a larger one.
// The next Leonardo number is one bigger.
sift(m, pshift, head);
p >>>= 2;
pshift += 2;
} else {
// adding a new block of length 1
if (LP[pshift - 1] >= hi - head) {
// this block is its final size.
trinkle(m, p, pshift, head, false);
} else {
// this block will get merged. Just make it trusty.
sift(m, pshift, head);
}
if (pshift == 1) {
// LP[1] is being used, so we add use LP[0]
p <<= 1;
pshift--;
} else {
// shift out to position 1, add LP[1]
p <<= (pshift - 1);
pshift = 1;
}
}
p |= 1;
head++;
}
trinkle(m, p, pshift, head, false);
while (pshift != 1 || p != 1) {
if (pshift <= 1) {
// block of length 1. No fiddling needed
int trail = Integer.numberOfTrailingZeros(p & ~1);
p >>>= trail;
pshift += trail;
} else {
p <<= 2;
p ^= 7;
pshift -= 2;
// This block gets broken into three bits. The rightmost
// bit is a block of length 1. The left hand part is split into
// two, a block of length LP[pshift+1] and one of LP[pshift].
// Both these two are appropriately heapified, but the root
// nodes are not necessarily in order. We therefore semitrinkle
// both of them
trinkle(m, p >>> 1, pshift + 1, head - LP[pshift] - 1, true);
trinkle(m, p, pshift, head - 1, true);
}
head--;
}
}
private static <C extends Comparable<? super C>> void sift(C[] m, int pshift,
int head) {
// we do not use Floyd's improvements to the heapsort sift, because we
// are not doing what heapsort does - always moving nodes from near
// the bottom of the tree to the root.
C val = m[head];
while (pshift > 1) {
int rt = head - 1;
int lf = head - 1 - LP[pshift - 2];
if (val.compareTo(m[lf]) >= 0 && val.compareTo(m[rt]) >= 0)
break;
if (m[lf].compareTo(m[rt]) >= 0) {
m[head] = m[lf];
head = lf;
pshift -= 1;
} else {
m[head] = m[rt];
head = rt;
pshift -= 2;
}
}
m[head] = val;
}
private static <C extends Comparable<? super C>> void trinkle(C[] m, int p,
int pshift, int head, boolean isTrusty) {
C val = m[head];
while (p != 1) {
int stepson = head - LP[pshift];
if (m[stepson].compareTo(val) <= 0)
break; // current node is greater than head. Sift.
// no need to check this if we know the current node is trusty,
// because we just checked the head (which is val, in the first
// iteration)
if (!isTrusty && pshift > 1) {
int rt = head - 1;
int lf = head - 1 - LP[pshift - 2];
if (m[rt].compareTo(m[stepson]) >= 0
|| m[lf].compareTo(m[stepson]) >= 0)
break;
}
m[head] = m[stepson];
head = stepson;
int trail = Integer.numberOfTrailingZeros(p & ~1);
p >>>= trail;
pshift += trail;
isTrusty = false;
}
if (!isTrusty) {
m[head] = val;
sift(m, pshift, head);
}
}
于 2015-02-05T19:36:21.697 回答