如何优化保持奇偶顺序的数组重排算法至无额外空间？

Absolutely! We can achieve this reordering with O(1) extra space (no additional arrays or data structures) while preserving the original relative order of both odd and even numbers. The key is using an insertion-style shifting approach that maintains stability without needing extra storage.

Approach #

Here's the core idea:

• Track the position where the next odd number should be placed (lastOddPos), starting at -1 (meaning no odds have been placed yet).
• Iterate through the array. Whenever we find an odd number:
  1. Move lastOddPos forward to the next available spot for an odd.
  2. If the current odd is already in the correct position (i.e., no evens are between it and the last placed odd), do nothing.
  3. If there are evens in between, shift those even elements one position to the right, then place the odd number in its correct spot. This preserves the order of evens (since we're shifting them right without reordering) and odds (since we place each odd in the next available spot in the order we find them).

Java Implementation #

public static void reOrder(int[] arr) {
    int lastOddPos = -1; // Tracks the index where the next odd should be inserted
    
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] % 2 != 0) { // Found an odd number
            lastOddPos++;
            // Only shift if the odd isn't already in the correct position
            if (i != lastOddPos) {
                int temp = arr[i];
                // Shift all elements from lastOddPos to i-1 one position to the right
                for (int j = i; j > lastOddPos; j--) {
                    arr[j] = arr[j - 1];
                }
                arr[lastOddPos] = temp;
            }
        }
    }
}

Test with Your Input #

Let's walk through your example input {1, 4, 8, 3, 9, 12, 7}:

1. Start with lastOddPos = -1.
2. Index 0 (1, odd): lastOddPos becomes 0. No shift needed since i == lastOddPos.
3. Indices 1 and 2 (4, 8: evens): Skip.
4. Index3 (3, odd): lastOddPos becomes1. Shift elements 1-2 right, place 3 at index1. Array becomes [1,3,4,8,9,12,7].
5. Index4 (9, odd): lastOddPos becomes2. Shift elements2-3 right, place9 at index2. Array becomes [1,3,9,4,8,12,7].
6. Index5 (12, even): Skip.
7. Index6 (7, odd): lastOddPos becomes3. Shift elements3-5 right, place7 at index3. Final array is [1,3,9,7,4,8,12] — exactly your expected output.

Complexity Breakdown #

• Space Complexity: O(1) — we only use a handful of integer variables and a temporary storage for the odd element. No extra arrays are created.
• Time Complexity: O(n²) — in the worst case (e.g., all evens followed by all odds), we shift O(n) elements for each odd number. This is the trade-off for achieving in-place stability. If time is a higher priority than space, you could use an O(n) space approach (collect odds and evens in separate lists then merge), but this solution meets your no-extra-space requirement.

内容的提问来源于stack exchange，提问作者Manjeet Rulhania