Java 将偶数元素移动到数组的前面，同时保持相对顺序

您可以按以下方式更改条件和回归:

if (a[i] % 2 != 0 && a[i + 1] % 2 == 0) {
    // swap and recurse starting from the beginning
}

// don't swap and recurse

换句话说:如果下一个元素是偶数，那么继续进行交换，将奇数元素向右移动;否则，不要交换这些元素.即使元素都是奇数，您现有的方法也会交换元素，这会扰乱奇数子array.

此外，每当发生交换时重新启动整个过程，可以处理由于两个奇数元素相邻而未执行交换的情况.

public class Main {
    public static void moveEvenToFront(int[] a) {
        moveEvenToFrontRec(a, 0);
    }

    private static void moveEvenToFrontRec(int[] a, int i) {
        if (i == a.length - 1) {
            return;
        }
        else if (a[i] % 2 != 0 && a[i+1] % 2 == 0) {
            int temp = a[i];
            a[i] = a[i+1];
            a[i+1] = temp;
            moveEvenToFrontRec(a, 0);
            return;
        }

        moveEvenToFrontRec(a, i + 1);
    }

    public static void main(String[] args) {
        int[] a = {-1, 0, -7, 3, 10, 4, 0, 2, -1, -5, 6};
        moveEvenToFront(a);

        for (int n : a) {
            System.out.print(n + " ");
        }
    }
}

我认为moveEvenToFrontRec(a, Math.max(i - 1, 0));也可以，而不是从前面一路重新启动，但我还没有彻底判断过这一点.

也就是说，我不会为此使用回归.编码更难，管理更多，并且如果列表超过几千个项目，就会 destruct 堆栈.回归适合二分法搜索和平衡树穿越等对分而治之的问题.

您的迭代算法的时间复杂度是二次的.更有效的算法是使用一点额外的空间并在数组上循环多次:

class Main {
    public static void moveEvenToFront(int[] a) {
        int[] cpy = a.clone();
        int i = 0;

        for (int n : cpy) {
            if (n % 2 == 0) {
                a[i++] = n;
            }
        }

        for (int n : cpy) {
            if (n % 2 != 0) {
                a[i++] = n;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {-1, -2, 1, 0, 2, 3, 4, 5};
        moveEvenToFront(a);

        for (int n : a) {
            System.out.print(n + " "); // => -2 0 2 4 -1 1 3 5
        }
    }
}

这可以进一步优化，并且分配成本可能会使其在非常小的数组上的效率低于无分配二次方法.

这是一个二次迭代版本，非最优，但为了与OP的回归进行比较而共享:

public static void moveEvenToFront(int[] a) {
    for (boolean swapped = true; swapped; ) {
        swapped = false;

        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] % 2 != 0 && a[i + 1] % 2 == 0) {
                int temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
                swapped = true;
            }
        }
    }
}

this answer中提到的合并排序似乎也不错，线性且空间不变.直觉是，1的基本情况元素已经正确排序，那么当合并两个子数组时，相对顺序会保持，并且很容易首先附加偶数元素子array.