排序【数组】

排序【数组】

时间： 1ms        内存：128M

描述：

已知数组A[1..n]的元素类型为整型，设计算法调整A，使其左边的所有元素小于零，右边的所有元素大于等于零。（要求算法的时间复杂度和空间复杂度均为0（n））

输入：

数组大小

数组中个元素

输出：

排列后的数组元素

示例输入：

5
5 6 -1 5 1
5
3 3 -1 -1 2

示例输出：

-1 5 6 5 1
-1 -1 3 3 2

提示：

参考答案（内存最优[1120]）：

#include<stdio.h>
void work(int *a, int n)
{    int i, j, t;    for(i = 0, j = n - 1; i < j;)   
 {        if(a[i] < 0){ i++; continue;}        if(a[j] >= 0){ j--; continue;} 
       t = a[i];        a[i] = a[j];        a[j] = t;    }}
int main()
{    int a[1000], n, i;    while(scanf("%d", &n) != EOF)    
{        for(i = 0; i < n; i++) scanf("%d", &a[i]);        work(a, n);   
     for(i = 0; i < n; i++) printf("%d ", a[i]);        printf("\n");    }   
 return 0;}

参考答案（时间最优[0]）：

#include <iostream>
using namespace std;
void sort(int a[],int n)
{
    int i,b[100],k=0;
    for (i=0;i<n;i++)
    {
        if (a[i]<0)
            b[k++]=a[i];
    }
    for (i=0;i<n;i++)
    {
        if (a[i]>=0)
            b[k++]=a[i];
    }
    for (i=0;i<n;i++)
    {
        a[i]=b[i];
    }
}


int main()
{
    int n,a[100],i=0;
    while (cin>>n)
    {
        for (i=0;i<n;i++)
            cin>>a[i];
    sort(a,n);
    for (i=0;i<n-1;i++)
        cout<<a[i]<<" ";
    cout<<a[i]<<endl;
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。