Description
设任意n个整数存放于数组A[1…n]中，试编写算法，将所有正数排在所有负数前面（要求：正（负）数序列中数的相对顺序不变，算法时间复杂度为O(n)）。
Input
多组数据，每组数据有两行，第一行为数组中存放的数的个数n，第二行为n个整数。当n=0时输入结束。
Output
对于每组数据分别输出一行，为分割排序后的数组。
Sample Input
4
12-1 2
5
-1-2 1 2 3
0
Sample Output
122 -1
123 -1 -2
参考程序
#include <stdio.h>
#define LEN 100000
void PNChangeSort(int a[],int n)
{
int i,j,cnt=0,temp;
for(i=n-1;i>=0;i--)
{
if(a[i]<0)
{
cnt++;
for(j=i;j<=n-cnt-1;j++)
{
temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;
}
}
}
}
int main()
{
int a[LEN],i,n;
while(1)
{
scanf("%d",&n);
if(n==0)
{
break;
}
else
{
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
PNChangeSort(a,n);
for(i=0;i<n-1;i++)
{
printf("%d ",a[i]);
}
printf("%d\n",a[i]);
}
}
return 0;
}
分析：
以上程序是基于交换的，基本思路是：从后向前扫描数组，直到找到负数，并记录这是第cnt个负数，然后将此元素与后面的元素（正数）依次交换（依次交换可以保证正数、负数之间的相对顺序不变），最终达到下标为n-cnt的位置上。我个人认为此算法的时间复杂度为O(n^2)，但是可以提交通过。下面的程序是我第一遍写的，借助了辅助空间，但时间复杂度是O(n)，测试数据可以验证通过，但在线提交不能通过，出现“Wrong Answer”的提示。
待修改的代码：（数组的0号单元存储数组元素的个数）
#include <stdio.h>
#define LEN 100000
int n,Positive[LEN],Negative[LEN];
void AddElement(int a[],int x)
{
a[++a[0]]=x;
}
void PNDividSort(int a[],int n)
{
int i;
for(i=1;i<=n;i++)
{
if(a[i]<0)
{
AddElement(Negative,a[i]);
}
else
{
AddElement(Positive,a[i]);
}
}
}
int main()
{
int a[LEN],i;
while(1)
{
scanf("%d",&n);
if(n==0)
{
break;
}
else
{
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
Positive[0]=0,Negative[0]=0;
PNDividSort(a,n);
for(i=1;i<=Positive[0];i++)
{
printf("%d ",Positive[i]);
}
for(i=1;i<=Negative[0]-1;i++)
{
printf("%d ",Negative[i]);
}
printf("%d\n",Negative[i]);
}
}
return 0;
}
期待各位能纠正我的错误，欢迎大家批评指正！感谢！
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: