12

配列が空間と時間[a1b7c3d2]に変換された場合、つまり、相対的な順序が同じになるように、文字を左側に、数字を右側に配置します。私はアルゴリズムを考えることができますが、それ以上のものはありません。誰か助けてくれませんか？[abcd1732]O(1)O(n)O(nlogn)

4

2 に答える 2

3

私の知る限り、それはできません。これは基本的に、RADIX ソートアルゴリズムの 1 つのステップです。また、AFAIK の安定したRADIX ソートはインプレースで実行できません。

編集ウィキペディアは私に同意します（その価値について）：

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

MSD Radix Sort は安定したアルゴリズムとして実装できますが、入力配列と同じサイズのメモリ バッファーを使用する必要があります。

編集2

入力が常に文字と数字のペアである場合、解決策は非常に簡単です。どの文字がどこに行くべきかは常にわかっているからです。

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

iを行うたびに 2 次的に見えるかもしれませんwhileが、実際にはすべての要素が 1 回だけ移動されるため、線形です。

于 2013-09-28T21:51:25.703 に答える
1

まず、これは実際にはこの SO questionの複製であり、少し異なる方法で記述されています。

（あなたの問題は本当に安定した0-1ソートと見なされる可能性があるため）

残念ながら、アルゴリズムを理解することも、単純な疑似コードを見つけることもできませんが、必要に応じてアルゴリズムをここで説明します: http://www.diku.dk/~jyrki/Paper/KP1992bJ.pdf

于 2013-09-28T21:31:04.157 に答える