如何从数组中分离负数和正数？

Question

我想分隔数组中的负数和正数。

例如，如果我的数组有 10 个值，它们是 {-8,7,3,-1,0,2,-2,4,-6,7}，我希望新修改的数组为 {-6,-2,-1,-8,7,3,0,2,4,7}。

我想在 O(n^2) 中执行此操作，并且我也编写了代码。但我没有得到正确的输出。我的代码哪里错了？

import java.util.Random;
public class Apples {

    public static void main(String[] args) {
        Random randomInteger=new Random();
        int[] a=new int[100];
        for(int i=0;i<a.length;i++)
        {
            a[i]=randomInteger.nextInt((int)System.currentTimeMillis())%20 - 10;
        }
        for(int i=0;i<a.length;i++)
        {
            if(a[i]<0)
            {
                int temp=a[i];
                for(int j=i;j>0;j--)
                {
                    a[j]=a[j-1];
                    j--;
                }
                a[0]=temp;
            }
        }
        for(int i=0;i<a.length;i++)
        {
            System.out.print(a[i]+" ");
        }

    }
}

Answer 1

你有两个 j-- 而你只需要一个，所以删除其中一个。

for(int j=i;j>0;j--)
 {
     a[j]=a[j-1];
     // remove j--; from here
 }

Answer 2

您可以考虑将以下内容作为对 negatives/positives 进行分区的替代方法。这是基于 K&R 的快速排序，但只对数组进行一次传递：

import java.util.Random;

public class Sweeper {   
   public static void printArray(int[] a) {
      for (int elt : a) {
         System.out.print(elt + " ");
      }
      System.out.println();
   }

   public static void swap(int[] a, int i, int j) {
      int tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
   }

   public static void partition(int[] a, int target) {
      int last = 0;
      for (int i = 0; i < a.length; ++i) {
         if (a[i] < target && i != last) swap(a, i, last++);
      }
   }

   public static void main(String[] args) {
      Random rng = new Random();
      int[] a = new int[20];
      for (int i = 0; i < a.length; i++) {
         a[i] = rng.nextInt(20) - 10;
      }
      printArray(a);
      partition(a, 0);
      printArray(a);
   }
}

如何从数组中分离负数和正数？

How to separate negative numbers and positive numbers from an array?

java

arrays

algorithm

big-o