整数配列処理アルゴリズム(7)再配置問題

n個の要素を含む整数配列aが与えられ、0要素と非0要素が含まれ、配列を並べ替え、要求:1.ソート後のすべての0要素は前にあり、すべてのゼロ以外の要素は後にあり、ゼロ以外の要素のソート前後の相対位置は変わらない.余分なストレージ領域を使用できない例は、0、3、0、2、1、0、0を入力します.
出力0,0,0,0,3,2,1
分析:
配列の最后から前へ遍歴して、0に出会ったら、0にならない要素を探して交换して、0にならない要素が見つからないならば、その前はすべて0で、戻ることができます.
次のようになります.

void Arrange(int* a, int n)
{
    int k = n -1 ;
    for (int i = n -1; i >=0; --i)
    {
        if (a[i] == 0)
        {
			for (int j= i-1; j>=0; j--)
			{
				if (a[j]!=0)
				{
					a[i]=a[j];
					a[j]=0;
					break;
				}
			}

			if (j==0)
			{
				return;//      0 
			}
        }
    }
}

テストコード:

int main()
{
	int* a= new int[6];
	int* b= new int[6];
	int i;
	
	a[0]=0;
	a[1]=3;
	a[2]=0;
	a[3]=6;
	a[4]=8;
	a[5]=0;
	
	b[0]=7;
	b[1]=0;
	b[2]=10;
	b[3]=0;
	b[4]=8;
	b[5]=9;
	

	Arrange(a, 6);

	for (i=0; i<6; i++)
	{
		cout << a[i] << "," ;
	}

	cout << endl;
	
	Arrange(b, 6);
	
	for (i=0; i<6; i++)
	{
		cout << b[i] << "," ;
	}
	
	cout << endl;

	delete[] a;
	a=NULL;
	delete[] b;
	b=NULL;

	
	cout << endl;
	
	return 0;
}

テスト結果:
0,0,0,3,6,8, 0,0,7,10,8,9,
興味のある方は、行ってみてもいいので、質問があればぜひフィードバックしてください.
転載はオリジナルリンクを明記してください:http://blog.csdn.net/wujunokay/article/details/12115253