java - 选择排序 - 交换下一个最小的与最小的整体

Question

我有一个关于选择排序的问题。在下面的例子中 -

12 8 7 5 2

下一步是什么

8 12 7 5 2

或

2 8 7 5 12

?

原因是从伪代码来看，我们似乎只是在寻找first元素，其值小于现有的first，而不是最小的整体。所以按照这个逻辑，要与 12 交换的元素应该是 8 而不是 2，对吧？

这是我正在使用的伪代码 -

static int[] selectionSort(int[] input) {
    if (input.length == 0) {
        return null;
    }
    else {
        int pos = -1;
        for (int i=0;i<input.length-1;i++) {
            pos = i;
            for (int j=i+1;j<input.length;j++) {
                if (input[j] < input[pos]) {
                    int temp = input[pos];
                    input[pos] = input[j];
                    input[j] = temp;
                }
            }
        }
    }
    return input;
}

我的理解有问题吗？ 2 个步骤中哪一个是正确的？代码应该理想地产生第一个选项，不是吗？

谢谢!

Answer 1

你开始于:

12 8 7 5 2

您从已排序部分中没有元素开始，然后遍历直到找到未排序部分中的最小元素。然后将其与未排序部分中的第一个元素交换。

sorted  |  unsorted
2          8 7 5 12

迭代直到找到最小的，并与未排序部分中的第一个交换:

sorted  |  unsorted
2 5         7 8 12

重复几次(不需要交换，因为元素已经按顺序排列):

sorted  |  unsorted
2 5 7       8 12

sorted  |  unsorted
2 5 7 8     12

sorted  
2 5 7 8 12

---

所以你的第二个例子是正确的第一步。