由于数组 [a1b7c3d2] 转换为 [abcd1732] 与 O（1 ）的空间和 O（N）时间，即把左边和数字字母右边，使得它们的相对顺序是一样的。我能想到的 O（nlogn）的算法，而不是更好。可有人请帮助？

Given an array [a1b7c3d2] convert to [abcd1732] with O(1) space and O(n) time i.e. put the letters on the left and digits on the right such that their relative order is the same. I can think of an O(nlogn) algorithm, but not better. Can somebody please help?

推荐答案

AFAIK它不能做。这是本质上的基数排序的算法的一个步骤。而AFAIK稳定的基数排序的不能就地进行。

AFAIK it can't be done. This is essentially a single step of the RADIX sort algorithm. And AFAIK stable RADIX sort can't be done in-place.

修改百科同意我（什么是值得）：

edit Wikipedia agrees with me (for what that's worth):

http://en.wikipedia.org/wiki/Radix_sort#Stable_MSD_radix_sort_implementations

MSD基数排序可被实现为一个稳定的算法，但需要   使用相同大小的存储器缓冲器的作为输入阵列

MSD Radix Sort can be implemented as a stable algorithm, but requires the use of a memory buffer of the same size as the input array

EDIT2

如果输入的是总是成对信数，则解决方案是非常简单的，因为我们总是知道哪些字符应该去的地方：

If the input is always in pairs of letter-number, then the solution is quite simple, as we always know which character should go where:

for i=0...n/2-1
  tmp=array[i]
  if tmp is a letter 
    continue // nothing to do, we have a letter already!
  index=i
  do
    // we have the wrong think at index! Where is it supposed to be?
    if (index is even) // the wrong thing is a letter
      index=index/2
    else // the wrong thing is a number
      index=n/2+index/2
    // we found where temp should go! Lets put it there!
    // But we keep what was already there and look for its place next iteration
    tmp2=array[index]
    array[index]=tmp
    tmp=tmp2
  while index!=i

它看起来二次，为每个我我们做了，而，但实际上每一个元素都只有感动一旦因此它是线性的。

It might look quadratic, as for each i we do the while, but actually every element is only moved once hence it's linear.