f和一个元素数组。A或B；你可以这样显示元素ABBAABABAA。AAAAAABBBB。
A值的数量不必等于B值的数量。元素的总数可以是任意的（不固定）。请注意，您不会排序字符，而是对具有单个字符表示的对象进行排序。O(n)完成，a = first A
b = first B
loop while next A exists
if b < a
swap a,b elements
b = next B
a = next A
else
a = next A
ABBAABABAA，你将获得以下结果：ABBAABABAA
AABBABABAA
AAABBBABAA
AAAABBBBAA
AAAAABBBBA
AAAAAABBBB
B时，将迭代器递减。A时，将迭代器递增。sort(list) {
node = list.head, blast = null, bhead = null
while(node != null) {
nextnode = node.next
if(node.val == "a") {
if(blast != null){
//move the 'a' to the front of the 'B' list
bhead.prev.next = node, node.prev = bhead.prev
blast.next = node.next, node.next.prev = blast
node.next = bhead, bhead.prev = node
}
}
else if(node.val == "b") {
if(blast == null)
bhead = blast = node
else //accumulate the "b"s..
blast = node
}
3
node = nextnode
}
}
所以，你可以在数组中做到这一点，但是模拟列表交换的memcopies会使大型数组变得非常缓慢。
f。ABBAABABAA => AABB AABB AA + pointers to blocks of A's and B's
对于 A 或 B 的顺序访问将立即可用，而随机访问将使用区间树来定位特定的 A 或 B。一种选择是使区间编号为 A 和 B；例如，要查找第 4 个 A，请查找包含 4 的区间。
对于排序，一个由 1,000,000 个四字节元素（3.8MB）组成的数组足以存储索引，每个元素使用一个位来记录交换期间已访问的索引；并且两个临时变量的大小为最大的 A 或 B。对于十亿个元素的列表，最大的组合区间树将编号为 4000 个区间。每个区间使用 128 位，我们可以轻松地为 A 和 B 存储编号区间，并且我们可以使用未使用的位作为块索引（10 位）和在 B 的情况下的偏移量指针（20 位）。4000 * 16 字节 = 62.5KB。我们可以在 4KB 中存储仅包含 B 块偏移量的附加数组。对于一个拥有十亿个元素的列表，总空间不到 5MB。（实际上，空间取决于 n，但因为它与 n 相比极小，所以从实际目的出发，我们可以认为它是 O(1)。）
对于排序百万个元素段的时间将是 - 一次遍历以计数和索引（我们在这里也可以累积间隔和B偏移量），另一次遍历以进行排序。构建区间树的时间复杂度为O(nlogn)，但n在这里仅为4000（占十亿列表数量的0.00005）。总时间为O(2n) = O(n)
Object_Array[1...N]
Type_A 对象是 A1，A2，...，Ai
Type_B 对象是 B1，B2，...，Bj
i+j = N
FOR i=1 :N
if Object_Array[i] is of Type_A
obj_A_count=obj_A_count+1
else
obj_B_count=obj_B_count+1
LOOP
根据 obj_A > obj_B，将 obj_A 和 obj_B 的相应计数填充到结果数组中。
type_X 是哈希函数对象的结果之一。 - Sir Bohumil以下方法适用于双向链表，可以在线性时间内完成。但是对于涉及到N个插入/删除操作的数组，可能会导致二次时间复杂度。
找到“排序”后第一个B应该在的位置。通过计算A的数量，可以在线性时间内完成。
使用3个迭代器：iterA从容器的开头开始，iterB从上述As和Bs相遇的位置开始，iterMiddle从iterB的前一个元素开始。
使用iterA跳过As，找到第一个B，并将对象从iterA移动到iterB->previous的位置。现在，iterA指向移动元素之后的下一个元素，而移动的元素现在位于iterB之前。
继续执行步骤3，直到达到iterMiddle。此后，first()和iterB-1之间的所有元素都是A。
现在将iterA设置为iterB-1。
使用iterB跳过Bs。当找到A时，将其移动到iterA之后并增加iterA。
继续执行步骤6，直到iterB到达end()。
这将适用于任何容器的稳定排序。该算法包括O(N)的插入/删除操作，对于具有O(1)插入/删除操作的容器来说是线性时间，但对于数组来说则是O(N^2)。适用性取决于容器是否为数组而不是列表。
O(n^2)并不是最佳选择。 - Sir Bohumil这应该可以通过一些动态编程实现。
它的工作方式有点像计数排序，但有一个关键的区别。为a和b分别创建大小为n的数组count_a[n]和count_b[n]。将这些数组填充为在索引i之前有多少个A或B。
仅经过一次循环，我们就可以使用这些数组以O(1)的时间复杂度查找任何元素的正确索引。就像这样：
int final_index(char id, int pos){
if(id == 'A')
return count_a[pos];
else
return count_a[n-1] + count_b[pos];
}
最后，为了满足总的O(n)要求，交换需要按照一种聪明的顺序进行。一个简单的选择是拥有递归交换过程，直到两个元素都被放置在正确的最终位置之前，不会实际执行任何交换。编辑：实际上这并不是真的。即使是朴素的交换也会有O(n)次交换。但是采用这种递归策略将给您提供所需的绝对最小交换。
请注意，在一般情况下，这将是非常糟糕的排序算法，因为它具有O(n * 元素值范围)的内存要求。
O(n)的空间，那么我可以简单地创建两个大小为n的数组，将所有的A按出现顺序复制到第一个数组中，将所有的B复制到第二个数组中，然后合并。更简单了。 - Sir Bohumil
A!=B，但A1不一定等于A2。 - Sir Bohumil