学步园

给定含有n个元素的整型数组a，其中包括0元素和非0元素，对数组进行排序，要求：
1. 排序后所有0元素在前，所有非零元素在后，且非零元素排序前后相对位置不变
2. 不能使用额外存储空间
例子如下：
输入 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