为什么我的选择排序程序不起作用？

Question

我正在尝试创建自己的程序来对整数数组进行选择排序。我提出了以下程序，它适用于某些数组，但不适用于其他数组，例如这个。我一直在尝试追踪问题，我认为这可能与我放置 min = num [x]; 行的位置有关。但是，我不确定应该将它移到哪里才能解决问题。有没有人有什么建议？谢谢。

p.s。我在底部提供了一些我的测试用例及其结果。

        int [] num = {4, 9, 7, 6, 0, 1, 3, 5, 8, 2};

        int min = num [0];
        int temp;
        int index = 0;

        for (int x = 0; x < num.length; x ++)
        {
            min = num [x];
            temp = num [x];
            for (int y = x + 1; y < num.length; y ++)
            {
                if (num [y] < min)
                {
                    min = num [y];
                    index = y;
                }
            }
            num [x] = min;
            num [index] = temp;
            min = num [x];
        }

输出测试用例：

array: {4, 9, 7, 6, 0, 1, 3, 5, 8, 2}
result: [0, 1, 2, 3, 4, 4, 5, 7, 8, 8]

array: {7, 5, 8, 9, 1, 6, 3, 0, 2, 4}
result: [0, 1, 2, 3, 4, 5, 6, 7, 7, 8]

array: {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
result: [0, 1, 2, 3, 4, 9, 6, 7, 8, 9]

Answer 1

一个大问题，多个小问题，见评论：

int [] num = {4, 9, 7, 6, 0, 1, 3, 5, 8, 2};

int min = num [0]; // you don't need this variable and assignment here, you can declare it inside loop
int temp; // the same for this variable
int index = 0; // the same here

for (int x = 0; x < num.length; x ++)
{
    min = num [x];
    temp = num [x];
    // here you need to re-initialize index variable to some value, otherwise it could be some garbage from previous iterations
    for (int y = x + 1; y < num.length; y ++)
    {
        if (num [y] < min)
        {
            min = num [y];
            index = y;
        }
    }
    num [x] = min;
    num [index] = temp;
    min = num [x]; // this assignment does not make sense as you're overwriting it next iteration
}

你可以稍微简化一下代码：

for (int x = 0; x < num.length; x++) {
    int index = x;
    for (int y = x + 1; y < num.length; y++)
        if (num[y] < num[index])
            index = y;
    int temp = num[x];
    num[x] = num[index];
    num[index] = temp;
}

Answer 2

您编写的代码存在一些问题：

最外层循环，索引为 x 的循环应该从 0 迭代到 num.length - 1，因为最内层循环从 x+1 开始。如果您迭代到包含 num.length - 1，那么，在最外层循环的最后一次迭代期间，y 将对应于 num.length，这不是实际元素，实际上最内层循环不会甚至开始。这将是无用的迭代。
最内层循环的if语句只需要保存剩余待排序元素中新的最小元素的索引（从x到num.length-1).您不需要也保存该值。
您的交换部分有一个没有任何用处的最终额外分配。此外，最好将所有赋值保留在代码的一个特定点，以提高可读性。此外，拥有三个临时变量（min、temp 和 index）比您实际需要的要多。您只需要 2 个临时变量（minIndex 和 temp），其中第一个存储找到的新最小值的索引，而第二个在 x-th 元素之间的值交换期间使用和位置 minIndex.

这是固定代码，其中包含对您的错误的解释和算法逻辑。

public static void main(String[] args) {
    int[] num = {4, 9, 7, 6, 0, 1, 3, 5, 8, 2};

    int minIndex, temp;

    //Your outermost loop should iterate till num.length - 1, since the innermost loop looks for any smaller element after x.
    //The outermost loop is used to guarantee that at each iteration, the x-th element contains the smallest value among the ones left to sort.
    for (int x = 0; x < num.length - 1; x++) {

        //Assuming the x-th element is the smallest among the ones left to sort (from x to num.lenght-1)
        minIndex = x;

        //Looking for a smaller element than the x-th after the x position
        for (int y = x + 1; y < num.length; y++) {

            //You only need to save the index of the new smallest element in minIndex.
            //Once you've completed the innermost loop, then you'll swap the x-th element with the element in position minIndex
            if (num[y] < num[minIndex]) {
                minIndex = y;
            }
        }

        //Swapping the x-th element with the minIndex-th element after the innermost loop has completed
        temp = num[x];
        num[x] = num[minIndex];
        num[minIndex] = temp;
    }

    System.out.println(Arrays.toString(num));
}

为什么我的选择排序程序不起作用？

Why isn't my selection sort program working?

java

arrays

sorting

selection-sort

输出测试用例：