问题描述：一个已知数组由整数组成，编程将数组中的所有整数按对正整数k求余得到的余数分组。
若 k = 2,余数为0,1，故分成两组；k =3, 余数为0,1,2，故分成三组；以此类推。
两个子问题:
(1) 已知一个数组由整数构成,编程将数组中所有奇数移动到所有偶数之前。
(2) 已知一个数组由整数构成,编程将数组中所有3的倍数放到数组前面,所有对3求余为2的数放在数组后部,其余放在数组中间。
对于子问题(1):
输入: 0,1,2,3,4,5,6,7,8,9
输出: 9,1,7,3,5,4,6,2,8,0,
请按任意键继续. . .
Process returned 0 (0x0) execution time : 7.128 s
Press any key to continue.
对于子问题(2)：
输入: 1,2,3,4,5,6,7,8,9,10,11,12
输出: 12,3,6,9,10,1,7,8,4,11,5,2,
请按任意键继续. . .
Process returned 0 (0x0) execution time : 5.243 s
Press any key to continue.
解题思想:
分成k组就用k个变量标记这些分组的边界，其中k-1个变量标识后边界，一个变量标识后边界；分别考察数组中每一个整数的整除性。
下面是子问题(1)的完整代码:
/*问题:已知一个数组由整数构成,编程将数组中所有奇数
移动到所有偶数之前
Written by : Jimmy Tung
Date : 2020.03.26
*/
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10 //数组大小
void Initialize(int [], int); //数组初始化
void Transpositon(int [], int); //奇偶互换
void Output(int [], int); //输出结果
int main(void)
{
int Integer[MAXSIZE];
//初始化
Initialize( Integer, sizeof Integer / sizeof Integer[0]);
//奇偶互换
Transpositon( Integer, sizeof Integer / sizeof Integer[0]);
//输出
Output( Integer, sizeof Integer / sizeof Integer[0]);
system("PAUSE");
return 0;
}
//数组初始化
void Initialize(int a[], int n)
{
int i = 0;
for( ; i < n ; i++)
{
a[i] = i;
}
}
//将数组中所有奇数移动到所有偶数之前
void Transpositon(int a[], int n)
{
int i, j, temp;
i = 0, j = n-1;
while(i < j)
{
if( a[i]%2 != 0)
{
i++;
continue;
}
if( a[i]%2 == 0 && a[j]%2 == 0)
{
j--;
continue;
}
else
{
temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
}
//结果输出
void Output(int a[], int n)
{
int i;
for( i = 0; i < n ; i++)
{
printf("%d,", a[i]);
}
putchar('\n');
}
子问题(2)的完整代码:
/*问题:已知一个数组由整数构成,编程将数组中所有3的倍数放到数组前面,
所有对3求余为2的数放在数组后部,其余放在数组中间。
Written by : Jimmy Tung
Date : 2020.03.26
*/
//输入:一组数据
//输出:要求的顺序
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 12 //数组大小
void Initialize(int [], int); //数组初始化
void Transpositon(int [], int); //计算
void Output(int [], int); //输出结果
int main(void)
{
int Integer[MAXSIZE];
//初始化
Initialize( Integer, sizeof Integer / sizeof Integer[0]);
//计算
Transpositon( Integer, sizeof Integer / sizeof Integer[0]);
//输出
Output( Integer, sizeof Integer / sizeof Integer[0]);
system("PAUSE");
return 0;
}
//数组初始化
void Initialize(int a[], int n)
{
int i = 0;
for( ; i < n ; i++)
{
a[i] = i + 1;
}
}
//计算
void Transpositon(int a[], int n)
{
//
int i, j, k; //标记三类数据的起点或结束点
int temp;
i = 0; j = 0; k = n-1;
while( j <= k)
{
if( a[j]%3 == 0)
{
temp = a[j];
a[j] = a[i];
a[i] = temp;
i++, j++;
}
if( a[j]%3 == 1)
{
j++;
}
if( a[j]%3 == 2)
{
temp = a[k];
a[k] = a[j];
a[j] = temp;
k--;
}
}
}
//输出
void Output(int a[], int n)
{
int i;
for( i = 0; i < n ; i++)
{
printf("%d,", a[i]);
}
putchar('\n');
}
时空复杂度分析:
（1）时间复杂度
初始化数组的时间是O(n);计算过程是O(n)；输出过程也是O(n)。所以总时间复杂度为O（n）.
（2）空间复杂度
原地操作，故空间复杂度为O(1)。
刚刚自学完数组一章，写出的代码没有经过优化，主要目的是熟悉一维和二维数组这些构造性的数据类型。后面再来思考和优化这些代码。
说明:
1.执行结果的显示的执行时间不是实际执行时间。
2.这个问题的一般性代码没有给出，有待进一步思考。
问题延伸:
1.给题目在增加一些限制条件，比如要求不要改变每组数据原来的前后关系。
