数组的重排、组合、排列

重排问题

给定含有n个元素的整型数组a，其中包括0元素和非0元素，对数组进行排序，要求：

1. 排序后所有0元素在前，所有非零元素在后，且非零元素排序前后相对位置不变

2. 不能使用额外存储空间，直接置为0，哪里要用额外的空间

例子如下

输入 0, 3, 0, 2, 1, 0, 0

输出 0, 0, 0, 0, 3, 2, 1

分析

此排序非传统意义上的排序，因为它要求排序前后非0元素的相对位置不变，或许叫做整理会更恰当一些。我们可以从后向前遍历整个数组，遇到某个位置i上的元素是非0元素时，如果a[k]为0，则将a[i]赋值给a[k]，a[k]赋值为0。实际上i是非0元素的下标，而k是0元素的下标

应该先从最后开始向前找到第一个0，然后再用Arrange做处理。 

#include
#define N 15
int B[N];
//应该先从最后开始向前找到第一个0用k指向，然后再用Arrange做处理。
void arrange(int a[],int n)
{
    int k=n-1;
    for(int i=n-1;i>=0;i--)
    {
        if(a[i]!=0)//前导为0不用管,k不用移,前导不为0,就要看下k是否为0,要接着移
        {
            if(a[k]==0)
            {
                a[k]=a[i];
                a[i]=0;//把[i]与a[k]交换0 5 6 0 1
                //k要继续指向另一个可能为0的数
            }
            k--;//a[k]不为0也要向前指，肯定能够指到为0;
        }
    }

}
int main()
{
    int i;
    for(i=0;i
    {
        scanf("%d",&B[i]);
    }
    arrange(B,N);
    for(i=0;i
    {
        printf("%d ",B[i]);
    }

    printf("\n");

    return 0;
}

/*
1 4 0 7 9 0 13 16 19 20 24 0 27 28 29
0 0 0 1 4 7 9 13 16 19 20 24 27 28 29
Press any key to continue

*/

组合问题

给定一个含有n个元素的整型数组a，从中任取m个元素，求所有组合。比如下面的例子

a = 1, 2, 3, 4, 5

m = 3

输出

1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 5

2 3 4, 2 3 5, 2 4 5
3 4 5

分析

典型的排列组合问题，首选回溯法，为了简化问题，我们将a中n个元素值分别设置为1-n

代码