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

Question

public static void teePaarisPaaritud(int[] a){
    teePaarisPaaritudRek(a, 0);
}

private static void teePaarisPaaritudRek(int[] a, int i) {
    if(i == a.length-1) return;

    if(a[i] % 2 != 0){
        int temp = a[i];
        a[i] = a[i+1];
        a[i+1] = temp;
        teePaarisPaaritudRek(a, i+1);
    }
    teePaarisPaaritudRek(a, i+1);
}

我写了这个递归方法。预期的功能是通过将偶数元素移到前面并将奇数元素移到后面来对 int[] 进行排序，同时保持偶数元素和奇数元素之间的原始顺序。例如，输入 int[] a = {-1,0,-7,3,10,4,0,2,-1,-5,6} 输出应为 [0,10,4,0 ,2,6,−1,−7,3,−1,−5]。然而我的代码有点偏离目标，我得到的输出是 [0, 10, 4, 0, 2, 6, -7, 3, -1, -5, -1] 。

正如你所看到的，第二个-1在后面，但它应该在-7之前。我尝试将基数设置为 if(i == a.length-2) return;但这没有用，因为这样最终 6 就会保留下来。仅当输入数组的长度为偶数时，才会出现此问题。

Answer 1

我知道你想使用递归，但我觉得你也应该使用 for 循环。

import java.util.*;

public class StackOverFlow {
    public static void teePaarisPaaritud(int[] a) {
        teePaarisPaaritudRek(a, 0);
    }

    private static void teePaarisPaaritudRek(int[] a, int i) {
        if (i == a.length - 1)
            return;

        if ((a[i] & 1) == 1) { // this is a small java bitwise trick to help faster code checks the same thing 
            for (int j = i + 1; j < a.length; j++) {
                if ((a[j] & 1) == 0) { 
                    int temp = a[j];
                   
                    for (int k = j; k > i; k--) {
                        a[k] = a[k - 1];
                    }
                    a[i] = temp;
                    break;
                }
            }
        }
        teePaarisPaaritudRek(a, i + 1);
    }
}

Answer 2

您可以按如下方式更改您的条件：

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

// don't swap and recurse

换句话说：如果下一个元素是偶数，则继续交换，将奇数元素向右移动；否则，不要交换元素。您现有的方法会交换元素，即使它们都是奇数，这会扰乱奇数子数组。

也就是说，我不会为此使用递归。它更难编码，有更多的开销，并且如果列表超过几千个项目，就会破坏堆栈。递归适用于对数分治问题，例如二分搜索和平衡树遍历。

递归算法的时间复杂度是二次的。更有效的算法是使用一点额外的空间并多次循环数组：

class Main {
    public static void moveOddToFront(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};
        moveOddToFront(a);

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

这可能可以优化，但它已经把递归方法从水里吹出来了。

Answer 3

if(a[i] % 2 != 0){

如果当前索引为奇数，则无论下一个索引是否为奇数，此行都会切换元素。修改条件时也需要考虑到这一点。