BJFU_数据结构习题_297数组的正负排序

今天药忘吃喽~ 2023-06-19 06:46 12阅读 0赞

欢迎登录北京林业大学OJ系统  
[http://www.bjfuacm.com][http_www.bjfuacm.com]

### 297数组的正负排序 ###

**描述**  
对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：  
①采用顺序存储结构，至多使用一个记录的辅助存储空间;  
②算法的时间复杂度为O(n)。  
**输入**  
多组数据，每组数据两行。第一行为序列的长度n，第二行为序列的n个元素（元素之间用空格分隔，元素都为整数）。当n等于0时，输入结束。  
**输出**  
每组数据输出一行，为排序后的序列。每两个元素之间用空格隔开。  
**输入样例 1**  
6  
1 2 3 4 -1 2  
5  
\-1 2 3 -2 4  
**输出样例 1**  
\-1 2 3 4 1 2  
\-1 -2 3 2 4

#include<iostream>
    using namespace std;
    void Exchange(int &x,int &y)	//注意引用符号&：形参变化，改变实参
    {
        
        int z;
        z=x;
        x=y;
        y=z;
    }
    void Divide(int a[],int n)	//遍历一次，时间复杂度O(n)
    {
        
        int i,j=0;
        while(a[j]<0)
            j++;        		//指针j指向左边第一个整数
        for(i=1;i<n;i++)		//a[0]不论正负都不用操作
            if(a[i]<0&&a[i-1]>=0)	//若从a[1]开始还是连续负数，那也不用操作
                Exchange(a[i],a[j]);
    }
    int main()
    {
        
        int n;
        while(cin>>n&&n!=0)
        {
        
            int i,R[100];
            for(i=0;i<n;i++)
                cin>>R[i];
            Divide(R,n);
            for(i=0;i<n-1;i++)
                cout<<R[i]<<" ";
            cout<<R[n-1]<<endl;
        }
        return 0;
    }

[http_www.bjfuacm.com]: http://www.bjfuacm.com