为什么采用XOR交换的Java选择排序实现无法正常运行？

代码存在的核心问题 #

1. 设计缺陷：不合理的静态成员变量 #

• 类中定义了public static int[] array静态成员，多线程同时调用sort()方法时会出现数组引用互相覆盖的线程安全问题
• swap方法明明接收了数组参数x，但实现中完全没有使用该参数，直接操作静态成员array，属于明显的逻辑设计错误，仅在单线程场景下能暂时正常运行，无任何扩展性

2. 算法边界错误：XOR交换的隐含前提未处理 #

XOR交换算法有强制前提：两个交换的索引不能相等。当遍历到当前i已经是未排序区间的最小值索引时，min = i，此时调用swap传入两个相同的索引，三次异或操作会直接把该位置的数值置为0，导致排序结果完全错误。
例：待排序数组为[1,3,2]时，第一次遍历i=0时min=0，调用swap(array,0,0)后数组第一位会变成0，最终排序结果为[0,2,3]，和预期不符。

3. 测试用例错误 #

测试类中testHighLow321用例对排序后的[3,2,1]断言期望结果仍为[3,2,1]，属于测试逻辑错误，该用例必然执行失败。

修复后代码 #

SelectionSort.java #

public final class SelectionSort {
    
    /**
     * 选择排序算法实现
     * 
     * @param x 待原地排序的整数数组
     */
    public static void sort(int[] x) {
        // 移除静态成员变量，直接使用参数x操作
        for (int i = 0; i < x.length - 1; ++i) {
            // 假设i是未排序区间的最小值索引
            int min = i;
            
            // 遍历未排序区间找到最小值索引
            for (int j = i + 1; j < x.length; ++j) {
                if (x[j] < x[min]) {
                    min = j;
                }
            }
            
            // 仅当最小值索引不等于当前i时才执行交换，规避同索引异或问题
            if (i != min) {
                swap(x, i, min);
            }
        }
    }
    
    /**
     * 用XOR算法原地交换数组两个位置的元素
     * 
     * @param x 目标数组
     * @param a 第一个元素的索引
     * @param b 第二个元素的索引
     */
    private static void swap(int[] x, int a, int b) {
        // 直接使用传入的数组参数，不依赖外部变量
        x[a] ^= x[b];
        x[b] ^= x[a];
        x[a] ^= x[b];
    }
}

SelectionSortTest.java #

import static org.junit.jupiter.api.Assertions.*;
import org.junit.jupiter.api.Test;

class SelectionSortTest {

    @Test
    void testAlreadySorted() {
        int[] x = new int[] {1, 2, 3};
        SelectionSort.sort(x);
        assertArrayEquals(new int[] {1, 2, 3}, x);
    }
    
    @Test
    void testReverseSorted() {
        int[] x = new int[] {3, 2, 1};
        SelectionSort.sort(x);
        assertArrayEquals(new int[] {1, 2, 3}, x);
    }
    
    @Test
    void testRandomOrder() {
        int[] x = new int[] {2, 1, 3};
        SelectionSort.sort(x);
        assertArrayEquals(new int[] {1, 2, 3}, x);
    }

    // 新增同索引交换场景测试，覆盖XOR边界场景
    @Test
    void testSameIndexSwap() {
        int[] x = new int[] {1, 3, 2};
        SelectionSort.sort(x);
        assertArrayEquals(new int[] {1, 2, 3}, x);
    }
    
}

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