O（N）インプレースアルゴリズムが可能です。すべての文字を配列の先頭に、すべての数字を最後に並べ替えることから始めることができます。次に、2x（N / 2）行列をインプレース転置して、配列の前半から偶数の位置にすべての要素を配置し、他の要素を奇数の位置に配置します。この質問は、この転置を行う方法を説明しています（実際には、そこで説明されているアルゴリズムは、逆に適用する必要があります）。
最も難しい部分は並べ替えです。安定していて、所定の位置にある必要があります。
O（N 2）時間でソートするのは簡単です。挿入ソートまたはバブルソートがそれを行います。
O（N log N）時間はもっと複雑です。この回答で説明されている、安定したインプレースマージソートを使用します。この回答は、O（ N ）アルゴリズムを構成するために使用できるアイデアを説明するリンクのペアを提供します。これは、安定したインプレースマージソートよりも単純ですが、それでもかなり複雑なので、スケッチのみを示します。
アレイを2つの領域に分割します。それらの1つは、アルゴリズムの他の部分に必要なデータを一時的に格納するために使用されます（この領域には引き続き配列要素が格納されるため、追加情報はこれらの要素の順序でエンコードされます）。その他の領域は正方行列として解釈され、最初に行、次に列の順に要素を並べ替える必要があります。両方の領域がソートされた後、転置アルゴリズムがそれぞれに適用され、文字と数字が適切な場所に配置されます。
配列のほとんどの要素は、サイズKの正方行列として編成されます。Kは最大の偶数であり、 2 * 8 * K + K2はNより大きくありません。一時ストレージのサイズM = N - K 2 、これは2 * 8 * sqrt（ N ）にほぼ等しくなります。
一時ストレージ用にM個の要素を準備するには、配列の最初のM個の要素をスキャンして、この範囲で最も少なく表されている要素の種類を判別します。たとえば、「数字」とします。サイズM /2のグループに数字をパックします。これを行うには、次の例に示すように、文字と数字のブロックを繰り返し交換します。
ddaaaddddadddaaaaad
aaaDDddddadddaaaaad
aaaaDDDDDDdddaaaaad
aaaaaaaaaDDDDDDDDDd
1つのグループに少なくともM /2桁が収集されたら停止します。ブロック交換手順（インプレースサブアレイローテーションとしても示される場合があります）は、この回答の最初のアルゴリズムとして、または次のように実装できます。
例：
123abcd
321abcd
321dcba
abcd123
サイズM /2のグループに数字をパックするには、最大（M / 2）2桁、最大N / 2文字移動する必要があるため、これはO（N）時間で実行できます。
正確には、O（N log 2 U）時間です。ASCII文字を並べ替えても問題ありませんが、代わりに他の種類の値を並べ替える必要がある場合は大きすぎます（Uは値セットのサイズです）。実行時間をO（N * log U * log log U ）に改善するには、サイズ2 * Kの小さな一時ストレージから開始し、それを使用してlog U範囲を並べ替えてから、これらの範囲をログのブロック交換手順とペアごとにマージします適切なサイズの一時ストレージを取得するためのUステップをログに記録します。
この時点で、M / 2サイズの数字のブロックがあり、その前に文字のブロック（おそらくより大きなサイズ）があります。ブロック交換手順を使用して、同じサイズの2つのブロックM /2を作成します。
データのビットを一時ストレージに格納するために、位置iおよびi + M /2で要素を交換する場合があります。位置iが文字を格納し、位置i + M / 2が数字を格納する場合、ゼロビットになります。数字が最初に来る場合、ゼロ以外のビットがあります。8つの連続するビットが1つの文字をエンコードします。つまり、一時ストレージに最大K文字を記憶できます。
一時ストレージにビットを格納する他の代替手段は、その「数」の半分です。各数値は、「0」..「9」（ビット0を意味する）または「a」..「j」（ビット1を意味する）のいずれかとして格納できます。可能な文字数が桁数の3倍以上であれば、各値に2ビットを格納できます。各値から4ビットを絞り出すために、2桁ごとに1バイトにパックする場合があります。これにより、M /4の空きバイトが得られます。したがって、Mは4* Kに減少する可能性があります。
この時点から、追加メモリとして一時ストレージを使用して、アレイのメイン領域を再配置する必要があります。サイズ2* Kのサブ配列で最も少なく表されている要素の種類を決定します。たとえば、「数字」とします。配列を順番にスキャンし、数字を一時的なストレージに移動し、文字を連続した順序でパックします。K桁を収集すると、L文字が順番に表示され、L>= Kになります。最後のL％K文字を空いている領域の最後に移動し、空いている領域の残りの部分を一時ストレージからの数字で埋めます。次に、アレイを順番にスキャンし続けます。
このプロシージャは、配列の各要素を1回または2回だけコピーするため、完了するにはO（N）時間が必要です。最後に、文字/数字のすべてのブロックが整列され、マトリックスの各行に1種類の要素が含まれるようになります。
これは、前の手順を簡略化したものです。マトリックス列ごとに、数字を一時ストレージに移動し、文字を連続した行にパックしてから、数字を一時ストレージから空いている行にコピーします。
この手順を完了するには、O（N）時間も必要です。最後に、配列のメイン領域が完全にソートされます。次に、一時ストレージをソートします（各「ビット」にゼロを書き込みます）。
残りの唯一のステップは、文字と数字が適切な場所に配置されるように、一時ストレージと配列のメイン領域の両方を転置することです。（ K x K行列ではなく、両方のサブ配列から作成された2つの2 x J行列が、リンクされた回答の1つに記載されているアルゴリズムで置き換えられることに注意してください）。
この手順とアルゴリズム全体には、O（N）時間が必要です。
2番目のアルゴリズム。
ASCIIには10桁と52文字しか含まれていないため、次の方法でアルゴリズムを大幅に簡略化できます。
3番目のアルゴリズム。
この問題を解決するための他のアプローチは、すべての文字を配列の先頭に、すべての数字を、このpdfで説明されているインプレースの安定した基数ソート（の一部の変更）でソートすることです。ソート後、前述の転置アルゴリズムを適用します。
ここで最も難しいのは、この基数ソートアルゴリズムの圧縮部分です。各値から1ビットを節約することはできません。代わりに、算術符号化を使用する必要があります。
これがO（N²）の実装です
def is_digit(s):
if isinstance(s, str):
return False
return True
def interleave(items):
if len(items) < 2:
return
loc = 1
max_loc = len(items)
prev_is_digit = is_digit(items[0])
while loc < max_loc:
if is_digit(items[loc]) == prev_is_digit:
# proceed through the list looking for the next item that has the
# opposite type
for i in xrange(loc + 1, max_loc + 1):
if is_digit(items[i]) != prev_is_digit:
# found the opposite type
val = items[i]
# once the item is found, shift everything up to the item
# over by one
for j in xrange(i, loc, -1):
items[j] = items[j - 1]
# move the item to It's new place
items[loc] = val
break
loc += 2
else:
# invert the type we are looking for
prev_is_digit = not prev_is_digit
loc += 1
items = ["a","b",2,"c",3,"d",4,1]
interleave(items)
print items
この問題は、2つのシーケンスの安定したインプレースマージと見なすことができると思います。その観点から、同じサイズの配列の安定したインプレースマージはO（n）時間で実行できるため、O（n）時間とO（1）空間で解決できるはずです（たとえば、 http：//を参照）。 comjnl.oxfordjournals.org/content/38/8/681.abstract）。
ただし、これを行うためのアルゴリズムは、実装するのが完全に簡単ではありません（そして、CSの学部生のためのまともなミニ研究プロジェクトを作ることができます）。
いずれにせよ、O（n log n）時間とO（1）時間で配列を安定してソートすることは間違いなく可能です（たとえば、http ：//www.springerlink.com/content/d7348168624070v7/？MUD = MPを参照）。アルゴリズムの複雑さに上限を設定します。
もう1つの簡単なインプレースO（n2）ソリューションは、次のようになります。1）2つのptrs：srcおよびdestを使用します。数字以外の場合は、最初の数字を探して、dest +1locと交換します
public static void permute_alt(char arr[]) {
int src=0, dest=0;
while (dest < arr.length) {
if (isChar(arr[dest])) { //We have a non-digit at dest idx .Now lets look for
// digit and put it in dest+1 place
dest++;
src=dest;
while (!Character.isDigit(arr[src])) {
src++;
}
swap(arr, src, dest);
dest++;
} else {
src=dest;
while (!isChar(arr[src])) {
src++;
}
swap(arr, src, dest);
dest++;
}
}
}
src ptrは、次の反復のためにdest+1またはdestにリセットされます。