java 中的选择排序不一致

Question

我一直在尝试在 Java 中编写一个选择排序程序，并认为（在浏览其他论坛之后）我的代码是正确的。目前是

public class SelectionSort {
    
    public static int[] selectionSort(int[] numbers) {
        
        for (int i = 0; i < numbers.length; i++) {
            int currentMin = i;
            for(int k = i+1; k < numbers.length; k++) {
                if (numbers[k] < numbers[currentMin]) {
                    currentMin = k;
                
                    if(currentMin != i) {
                        int placeholder = numbers[i];
                        numbers[i] = numbers[currentMin];
                        numbers[currentMin] = placeholder;
                    }
                }
            }
        }
        return numbers;
    }

}

当我运行通过 3 个示例数组时，其中一些有效，而另一些则无效。我在下面包含了之前和之后的数组：

[5, 2, 7, 6, 8, 1, 5]

[1, 2, 5, 5, 6, 7, 8] (correct order)

[5, 2, 4, 0, 8, 7, 6, 3, 0, 7, 8, 5, 4, 6, 3, 0, 8, 2, 7, 6, 3, 9, 0]

[3, 0, 3, 0, 2, 3, 0, 0, 4, 4, 2, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9] (wrong order)

[8, 5, 7, 6, 2, 7, 6, 1, 2, 5, 4, 9]

[2, 1, 5, 4, 2, 6, 7, 7, 6, 5, 8, 9] (wrong order)

当我移动牙套时，它们就像这样：

public class SelectionSort {

public static int[] selectionSort(int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            int currentMin = i;
            for(int k = i+1; k < numbers.length; k++) {
                if (numbers[k] < numbers[currentMin]) {
                    currentMin = k;
                    }
                
                    if(currentMin != i) {
                        int placeholder = numbers[i];
                        numbers[i] = numbers[currentMin];
                        numbers[currentMin] = placeholder;
                    }
                }
            }
        
        return numbers;
    }

}

我得到这些结果

[5, 2, 7, 6, 8, 1, 5]

[5, 2, 5, 1, 6, 7, 8] (wrong)

[5, 2, 4, 0, 8, 7, 6, 3, 0, 7, 8, 5, 4, 6, 3, 0, 8, 2, 7, 6, 3, 9, 0]

[0, 0, 0, 0, 2, 2, 3, 3, 3, 4, 4, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9] (right)

[8, 5, 7, 6, 2, 7, 6, 1, 2, 5, 4, 9]

[1, 2, 5, 5, 2, 6, 6, 7, 7, 8, 4, 9] (wrong)

基本上，我如何获得它以便所有数组都以正确的方式排序？我真的不确定错误在哪里，因为将它与其他代码片段进行比较来做类似的事情，它似乎是一致的。谢谢

Answer 1

这个元素交换：

if(currentMin != i) {
    int placeholder = numbers[i];
    numbers[i] = numbers[currentMin];
    numbers[currentMin] = placeholder;
}

应该在整个内循环之外。

选择排序是在数组的剩余部分（内循环）中寻找最小值的元素，并将这个最小值与当前位置的元素交换。因此，在每次外循环迭代中最多有一次交换。

Answer 2

您的内部循环正在交换 i 而不是 currentMin

你可以这样修改（也可能不需要if(currentMin != i) {）

int placeholder  = numbers[currentMin];  
numbers[currentMin] = numbers[i];
numbers[i] = placeholder;

java 中的选择排序不一致

selection sort inconsistency in java

java

arrays

sorting

selection