对数组中的偶数和奇数进行排序，同时保持顺序

Question

http://www.geeksforgeeks.org/segregate-even-and-odd-numbers/我在查找面试问题时发现了这个有趣的问题。该算法看起来很简单，但我想知道是否可以在不使用任何额外空间的情况下保持偶数和奇数的顺序，同时仍然保持 O(n) 的时间复杂度。

例如

输入：{12, 34, 45, 9, 8, 90, 3}

输出：{12,34,8,90,45,9,3}

编辑：如果没有额外的空间就不可能，它可以仅在适当位置重新排列整数吗？因为交换只能发生在数组中

Answer 1

我认为这是不可能的，因为没有额外的空间（取决于

n

），你将不得不交换元素，从而使它们混乱（或者你可以移动数组中的块，但这可能需要非线性的总时间；使用据我所知，问题中不允许使用其他数据结构，例如链表）。

这个问题可以被视为稳定的就地非比较排序，其中所有偶数元素都映射到零，所有奇数元素都映射到1进行比较，并且似乎没有匹配这些标准的算法（稳定，时间

O(n) 

，额外内存

O(1)

）（参见“非比较排序”表 https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms）。

Answer 2

是的，这是可能的。想法是计算偶数总数，然后将奇数一一移动到正确的位置。

    public void segregateEvenOddWithOrder(int[] arr) {
    int countEven = 0;
    int length = arr.length;
    for (int i = 0; i < length; i++) {
        if (arr[i]%2 == 0){
            countEven++;
        }
    }
    int i = 0;
    int j = i+1;
    while (i != countEven){
        if (arr[i]%2 == 0){
            i++;
            j = i + 1;
        }else if (arr[i]%2 == 1 && j < length){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            j++;
        }
    }
}

Answer 3

这是我的解决方案：

---

public static void segregateEvenOdd_Sorted_Optimized(int[] arr, int n) {

    List<Integer> evenNums = new ArrayList<>();
    List<Integer> oddNums = new ArrayList<>();

    for (int i = 0; i < n; i++) {

        if (arr[i] % 2 == 0) {
            evenNums.add(arr[i]);
        }
        if (arr[i] % 2 == 1) {
            oddNums.add(arr[i]);
        }

    }

    Collections.sort(evenNums);
    Collections.sort(oddNums);

    for (int i = 0; i < evenNums.size() + oddNums.size(); i++) {
        if (i < evenNums.size()) {
            arr[i] = evenNums.get(i);
        } else {
            arr[i] = oddNums.get(i - evenNums.size());
        }

    }

    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ");
    }

}

---

Answer 4

当使用 JDK >= 8 时，可以通过更简单的方式解决这个问题。代码片段在这里：

 public static int[] customSort(int[] arr) {
    return Arrays.stream(arr)
            .boxed() // Convert int to Integer
            .sorted(Comparator.comparingInt(num -> num % 2 == 0 ? 0 : 1)) // Sort even before odd
            .mapToInt(Integer::intValue) // Convert Integer back to int
            .toArray(); // Convert Stream to array
}

结果：

int[] arr = {3, 1, 4, 2, 5, 6, 7, 8};
Output: 4 2 6 8 3 1 5 7

您可以从这里参考。