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

Question

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

12 8 7 5 2

下一步会是

8 12 7 5 2

或

2 8 7 5 12

?

原因是，从伪代码来看，我们似乎只是简单地寻找first值小于现有first的元素，而不是smallest总体。所以按照这个逻辑，要与 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

在选择排序中，需要找出剩余数组中最小的元素，并将两者交换。

因此在您的示例中，下一步应该是 2 8 7 5 12。您的代码中唯一需要更改的是将交换推迟到最后，因此只会交换最小的元素。

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]) {
                    pos = j;
                }
            }
            int temp = input[pos];
            input[pos] = input[i];
            input[i] = temp;
        }       
    }
    return input;
}

Answer 2

您开始于：

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

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

Answer 3

它将是2, 8, 7, 5, 12。选择排序总是把最小的元素带到左边。将选择排序视为冒泡排序的对立面。其中冒泡排序冒泡右边最大的元素，选择排序则相反。希望对您有所帮助。

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

Selection sort - Swap with next smallest vs smallest overall

java

sorting

algorithm

selection-sort