Take a look at the master !!!!!!!!

gloomyelf

There is a one-dimensional integer array A of length n. An algorithm is designed to store all negative numbers in the array in the front of the array, and all positive numbers after the negative numbers.

stoneboy4000

The landlord did not say what to do with 0, it is temporarily positive

void f(int a[], int n){
  int i=0,j;/*i find positive numbers, j find negative numbers*/
  while(i<n&&a[i]<0)i++;/*First positive number*/
  for(j=i+1;j<n;j++)
    if(a[j]<0){
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
      i++; /* Both i and j are positive numbers, i is the first positive number */
    }
}

wljohn

The algorithm upstairs is slow
Quick sort is faster
A pointer from front to back
Another back to front
Can reduce poverty as much as possible

powerwang

Insert O(N) directly

四处转转

agree
Is indeed o(n)

tiansheng

Count sorting, the count range is 2 (just distinguish between positive and negative values), O(n) complexity