有没有办法更优雅地将数组分类为偶数和赔率

Question

我正在尝试对整数数组进行排序，以便所有偶数都位于奇数之前，而无需使用任何外部库。您可以从以下方面认识到这一点： http://codingbat.com/prob/p105771

" 返回一个数组，该数组包含与给定数组完全相同的数字，但重新排列，以便所有偶数都位于所有奇数之前。除此之外，数字可以按任何顺序排列。您可以修改并返回给定的数组，也可以创建一个新数组。"我有实现此目标的代码：

    public int[] evenOdd(int[] nums) {
    int c=0;
    int c2=0;
    int [] nums2=new int[nums.length];
    for(int i=0;i<nums.length;i++)
    {
        if(nums[i]%2==0)
        {
            nums2[c]=nums[i];
            c++;
        }
        else
        {
            nums2[nums.length-c2-1]=nums[i];
            c2++;
        }
    }
    return nums2;
}

我还通过调用array.sort()然后按索引插入数字，递增 2，然后插入余数来解决这个问题。这也行得通。

那么，长篇短文短文——将来有没有更优雅的方式来实现这一目标呢？谢谢！

Answer 1

只是对我的评论的跟进。以下是在没有额外空间的情况下在O(n)中执行此操作的方法：

public class Main {
    public static void main(String[] args) {
        evenOdd(new int[]{1, 2, 3, 4, 5, 6, 7});
        evenOdd(new int[]{2, 3, 4, 5, 6, 7});
        evenOdd(new int[]{1, 1, 1, 1, 1});
        evenOdd(new int[]{2, 2, 2, 2});
    }
    public static void evenOdd(int[] a) {
        int firstOdd = 0;
        for (int i = 0; i < a.length; ++i) {
            if (a[i] % 2 == 0) {
                int t = a[firstOdd];
                a[firstOdd] = a[i];
                a[i] = t;
                firstOdd++;
//            } else {
//                else is redundant, just leave odd in-place
            }
        }
        System.out.println(Arrays.toString(a));
    }
}

Answer 2

创建一个包含 int 的包装器对象，将其命名为 SortingWrapper。此对象应实现 Comparable，以便其自然排序顺序基于 value%2 的排序顺序。然后只需使用 Arrays.sort（） 对数组进行排序。基于 compareTo（） 实现，偶数自然会（即，根据它们的自然排序顺序）以一种方式冒泡，所有赔率都会以另一种方式冒泡。

或者，你可以只使用整数作为你的包装器，并将一个做同样事情的比较器传递给 Arrays.sort（）。

编辑 - 这是一般想法。您可能不得不使用排序顺序，但我认为这几乎有效。我怀疑这个数组将被视为"大部分排序"，这将使性能更倾向于 O（n） 而不是 log（n），基于 Arrays.sort（） 的 javadoc。

public void sortOddsAndEvents(Integer[] input)
{
    Arrays.sort(input, new Comparator<Integer>()
    {
        @Override
        public int compare(Integer arg0, Integer arg1)
        {
            if (arg0.equals(arg1)) return 0;
            else return Integer.compare(arg0.intValue()%2, arg1.intValue()%2);
        }
    });
}

Answer 3

public int[] evenOdd(int[] nums) {
  int evenCounter = -1, oddCounter = nums.length;
  int[] ordered = new int[nums.length];
  for (int i = 0; i < nums.length; i++) {
      int current = (nums[i] % 2 == 0) ? ++evenCounter : --oddCounter;
      ordered[current] = nums[i];
  }
  return ordered;
}