使用递归实现整数数组奇偶分离：偶数在前、奇数在后

看起来你正在尝试用递归的方式实现数组中偶数在前、奇数在后的排序（不需要保证奇偶内部顺序），我来帮你完善代码并解释思路。

首先，递归的核心思路是逐步缩小问题规模：我们可以用双指针的思路，一个指针从数组头部找奇数，另一个从尾部找偶数，找到后交换两者位置，然后递归处理中间的子数组，直到指针相遇（问题规模缩小到0）。

下面是完善后的完整代码：

public class EBOMain {
    static int[] array = {1, 2, 3, 4, 5, 6};

    public static void main(String[] args) {
        System.out.print("Array before sort: ");
        printArray(array);
        
        // 调用递归方法，初始指针指向数组首尾
        rearrangeEvenOdd(array, 0, array.length - 1);
        
        System.out.print("\nArray after sort: ");
        printArray(array);
    }

    // 递归核心方法：将[left, right]范围内的数组调整为偶数在前，奇数在后
    private static void rearrangeEvenOdd(int[] arr, int left, int right) {
        // 递归终止条件：当左指针 >= 右指针时，子数组无需处理
        if (left >= right) {
            return;
        }

        // 从左往右找第一个奇数
        while (left < right && arr[left] % 2 == 0) {
            left++;
        }

        // 从右往左找第一个偶数
        while (left < right && arr[right] % 2 != 0) {
            right--;
        }

        // 交换找到的奇数和偶数位置
        if (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            
            // 递归处理剩下的子数组
            rearrangeEvenOdd(arr, left + 1, right - 1);
        }
    }

    // 辅助方法：打印数组
    private static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

代码解释： #

• 递归终止条件：当left >= right时，说明当前子数组已经处理完毕（只剩一个元素或无元素），直接返回。
• 双指针查找：
  • 左指针left从头部开始，找到第一个奇数（需要被换到后面的元素）。
  • 右指针right从尾部开始，找到第一个偶数（需要被换到前面的元素）。
• 交换与递归：找到符合条件的元素后交换位置，然后递归处理[left+1, right-1]的子数组，逐步缩小问题范围。
• 辅助打印方法：方便查看处理前后的数组状态。

测试结果： #

运行代码后会输出：

Array before sort: 1 2 3 4 5 6 
Array after sort: 6 2 4 3 5 1 

（注：奇偶内部顺序不固定，只要所有偶数在奇数前即可，这个结果符合要求）

如果你想尝试另一种递归思路（比如分治：将数组分成两部分分别处理后合并），可以随时提出来调整~

内容的提问来源于stack exchange，提问作者Joseph V