使用Bubble Sort算法对数组奇偶元素分组并排序的问题排查

需求：实现数组处理逻辑，让奇数通过冒泡排序后位于数组左侧，偶数排序后位于数组右侧。

预期输出示例：

int[] a = {1,2,3,4,5,6,7,8,9,10}
output: 1 3 5 7 9 2 4 6 8 10

现状：目前奇偶元素的分组功能和奇数排序功能正常，但偶数未实现排序，不清楚原因。

我的代码如下：

public class ObligOppgave4 {

    public static void main(String[] args) {
        int[] a = {1,2,3,4,5,6,7,8,9,10};
       
        sortEvenAndOdd(a);
        bubbleSortOdd(a);
        bubbleSortEven(a);

        print(a);
    }

    public static void sortEvenAndOdd(int[] a) {

        int l = a.length;
        int v = 0, h = l - 1;

        if (a.length == 0) return;

        while (v <= h) {
            if (((a[v] % 2) == 0) && !((a[h] % 2) == 0)) {
                change(a, v++, h--);
            } else if ((a[v] % 2) == 0) {
                h--;
            } else if (!((a[h] % 2) == 0)) {
                v++;
            } else if (!((a[v] % 2) == 0) && ((a[h] % 2) == 0)) {
                v++;
                h--;
            }
        }
    }

    public static void bubbleSortOdd(int[] a) {
        for (int n = 0; n < a.length; n++) {
            for (int i = 1; i < n && a[i] % 2 != 0; i++) {
                if (a[i - 1] > a[i]) {
                    change(a, i - 1, i);
                }
            }
        }
    }

    public static void bubbleSortEven(int[] a){
        for (int n = 0; n < a.length; n++) {
            for (int i = 1; i < n && a[i] % 2 == 0; i++) {
                if (a[i - 1] > a[i]) {
                    change(a, i ,i);
                }
            }
        }
    }

    public static void change(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void print(int[] a) {
        for(int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");

        System.out.println();
    }
}

问题分析与修复 #

你的bubbleSortEven方法存在两个关键错误：

1. 交换逻辑无效：调用change(a, i, i)是将元素与自身交换，完全无法实现排序，应该改为change(a, i-1, i)。
2. 循环范围与逻辑错误：
   • 冒泡排序的外层和内层循环方向不符合常规逻辑，导致无法正确遍历偶数区域。
   • 没有限定排序范围，分组后偶数集中在数组右侧，应该先找到奇偶分界点，只对分界点后的偶数区域排序，避免无效遍历。

修正后的bubbleSortEven方法：

public static void bubbleSortEven(int[] a){
    // 找到第一个偶数的位置，确定奇偶分界点
    int splitIndex = a.length;
    for(int i = 0; i < a.length; i++){
        if(a[i] % 2 == 0){
            splitIndex = i;
            break;
        }
    }
    // 对偶数区域执行冒泡排序
    for (int n = a.length - 1; n > splitIndex; n--) {
        for (int i = splitIndex; i < n; i++) {
            if (a[i] > a[i+1]) {
                change(a, i, i+1);
            }
        }
    }
}

同时可以优化bubbleSortOdd方法，只对分界点前的奇数区域排序，提升效率：

public static void bubbleSortOdd(int[] a) {
    int splitIndex = a.length;
    for(int i = 0; i < a.length; i++){
        if(a[i] % 2 == 0){
            splitIndex = i;
            break;
        }
    }
    // 只对奇数区域冒泡排序
    for (int n = splitIndex - 1; n > 0; n--) {
        for (int i = 0; i < n; i++) {
            if (a[i] > a[i+1]) {
                change(a, i, i+1);
            }
        }
    }
}

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