博客

任务描述

本关任务：在数组中存放了n个整数，编写算法将所有正数排在负数前面（要求算法的时间复杂度为



O(n)



）。

#include<iostream>
using namespace std;

void Partition(int A[], int n)
{
   int i=0;
   int N=n;
   int temp;
   int num;
   for(int i=0;i<n;i++)
   {
       if(A[i]>0)
       {
           num++;
       } 
   }
   while(i<num)
   {
       int boolean=0;
       temp=A[i];
       while(A[i]<0)
       {
          
          if(A[n-1]>0)
          {
              
              A[i]=A[n-1];
          }
          else 
          {
              n--;
              A[i]=A[n-1];     
          }
          boolean++;
       }
       if(boolean)
       {
            A[n-1]=temp;
            n--;
       }
       i++;
   }
}

void Print(int A[], int length)
{//输出处理后的数组
    cout << A[0];
    for (int i = 1; i < length; i++)
    {
        cout << "-->" << A[i];
    }
    cout << endl;
}

int main()
{
    int n;
    cin>>n;
    int *arr = new int[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    Partition(arr, n);
    Print(arr,n);
    delete[] arr;
    return 0;
}