如何与QUOT;排序＆QUOT; 2可能值线性时间到位的元素？ [英] How to "sort" elements of 2 possible values in place in linear time?

问题描述

假设我有一个函数 F 和元素的数组。

Suppose I have a function f and array of elements.

该函数返回 A 或 B 的任何元素;你能想象的元素这样 ABBAABABAA 。

The function returns A or B for any element; you could visualize the elements this way ABBAABABAA.

我需要根据功能的元素进行排序，因此结果是： AAAAAABBBB

I need to sort the elements according to the function, so the result is: AAAAAABBBB

的 A 值的数量并不一定等于 B 值的数量。元素的总数目可以是任意的（不固定）。请注意，您不排序字符，你那种有一个单个字符重新presentation对象。

The number of A values doesn't have to equal the number of B values. The total number of elements can be arbitrary (not fixed). Note that you don't sort chars, you sort objects that have a single char representation.

一些事项：

• 排序应采取线性时间 - O（N），
• 在它应该在的地方来执行，
• 在它应该是一个稳定的排序。

任何想法？

注意：如果以上是不可能的，你有没有想法算法牺牲的上述要求之一

Note: if the above is not possible, do you have ideas for algorithms sacrificing one of the above requirements?

推荐答案

如果它的的是线性和在地方，你可以做一个的半稳定的版本。通过半稳定我的意思是 A 或 B 可能是稳定的，但不能同时使用。类似Dukeling的答案，但你从同一侧移动这两个迭代器：

If it has to be linear and in-place, you could do a semi-stable version. By semi-stable I mean that A or B could be stable, but not both. Similar to Dukeling's answer, but you move both iterators from the same side:

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

在每一轮，如果你犯了一个交换您移动两个，如果不是你只是移动 A 。这将让 A 稳定，但 B 将失去它的排序。为了让 B 稳定的，而不是从月底开始，并以你的方式离开了。

on each turn, if you make a swap you move both, if not you just move a. This will keep A stable, but B will lose its ordering. To keep B stable instead, start from the end and work your way left.

这可能与全面稳定的做到这一点，但我怎么看不到。

It may be possible to do it with full stability, but I don't see how.

这篇关于如何与QUOT;排序＆QUOT; 2可能值线性时间到位的元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！