奇怪的选择排序行为

Question

我已经尝试实现我自己的选择排序代码。到目前为止，代码可以正常工作......它只是表现得很奇怪。

class HelloWorld {
 public static void main(String[] args) {
    long startTime = System.currentTimeMillis();

    int a[] = {
        3,7,8,4,22,13,9,5,10
    };

    int max_pos = a.length-1;
    int counter = 0;
    int min_sort = 0;
    int j = -1;
    int min_pos = 0;
    int i=0;

    while (j < max_pos) {
        i=j+1;
        min_sort = a[i];
        // traverse trough unsorted portion
        while (i < max_pos) {
            i++;
            if (min_sort > a[i]) {
                min_sort  = a[i]; // minimum unsorted
                min_pos = i;
            }
        }

        // sorted portion
        j++;
        a[min_pos] = a[j];
        a[j] = min_sort ;
        for(int x=0; x < a.length; x++) {
            System.out.print(a[x] + ", ");
        }
        System.out.print("\t\t");
        System.out.println("i: " + i + " j: " + j + " min pos: " + min_pos + " min val: "+ min_sort);
    }
  }
 }

我试过追踪它，输出是这样的：

3, 7, 8, 4, 22, 13, 9, 5, 10,           i: 8 j: 0 min pos: 0 min val: 3          
3, 4, 8, 7, 22, 13, 9, 5, 10,           i: 8 j: 1 min pos: 3 min val: 4          
3, 4, 5, 7, 22, 13, 9, 8, 10,           i: 8 j: 2 min pos: 7 min val: 5          
3, 4, 5, 7, 22, 13, 9, 7, 10,           i: 8 j: 3 min pos: 7 min val: 7          
3, 4, 5, 7, 7, 13, 9, 22, 10,           i: 8 j: 4 min pos: 7 min val: 7          
3, 4, 5, 7, 7, 9, 13, 22, 10,           i: 8 j: 5 min pos: 6 min val: 9          
3, 4, 5, 7, 7, 9, 10, 22, 13,           i: 8 j: 6 min pos: 8 min val: 10         
3, 4, 5, 7, 7, 9, 10, 13, 22,           i: 8 j: 7 min pos: 8 min val: 13         
3, 4, 5, 7, 7, 9, 10, 13, 22,           i: 8 j: 8 min pos: 8 min val: 22

Answer 1

因为这几乎可以肯定是您的教育过程（真正的代码只会调用 Arrays.sort()），所以我一开始不会直接给出答案。

相反，您应该注意到它是 j == 3 所在的行，也就是 8 似乎神奇地变成了 7。

所以你应该开始磨练你的调试技巧了。运行代码通过调试器直到上一行输出结束，然后单步执行每条指令。在某些时候，您会看到 7 变成了 8 而 那就是 您需要关注的代码。

一旦你完成了这些，你就有希望能够说出问题是什么。但是，如果您仍然遇到困难（确保先尝试，否则您将永远无法改进），请参阅下文。 t---

这是对你的问题的详细分析。您正在存储有关最小值的信息（值 min_sort 及其位置 min_pos） 每次您发现一个元素小于您在每次迭代中设置的第一个元素时外循环：

if (min_sort > a[i]) {
    min_sort  = a[i]; // minimum unsorted
    min_pos = i;
}

现在这是一个很好的方法，这两条信息稍后将用于交换过程⁽¹⁾:

j++;
a[min_pos] = a[j];
a[j] = min_sort;

然而，如果你没有找到一个小于第一个设置的元素的情况，例如下面的位置3值 7 以及超出该值的所有值都大于 7:

3, 4, 5, 7, 22, 13, 9, 8, 10
         ^

在这种情况下，if 语句的主体将永远不会是运行并且迭代开始时的初始条件仍然适用：

i=j+1;
min_sort = a[i];

注意到那里遗漏了什么吗？比如，让我们看看，位置被设置成什么？

宾果！如果在迭代中检查的第一个元素已经在其正确位置，则 min_pos 将保持设置为之前的任何设置，并且当您交换时，这不会很漂亮。您可以通过将外部 while 循环内的代码立即更改为：

来解决此问题

i = j + 1;
min_pos = i;          // add this line
min_sort = a[i];

你会看到大大改进（即正确）的输出：

3, 7, 8, 4, 22, 13, 9, 5, 10, i: 8 j: 0 min pos: 0 min val: 3
3, 4, 8, 7, 22, 13, 9, 5, 10, i: 8 j: 1 min pos: 3 min val: 4
3, 4, 5, 7, 22, 13, 9, 8, 10, i: 8 j: 2 min pos: 7 min val: 5
3, 4, 5, 7, 22, 13, 9, 8, 10, i: 8 j: 3 min pos: 3 min val: 7
3, 4, 5, 7, 8, 13, 9, 22, 10, i: 8 j: 4 min pos: 7 min val: 8
3, 4, 5, 7, 8, 9, 13, 22, 10, i: 8 j: 5 min pos: 6 min val: 9
3, 4, 5, 7, 8, 9, 10, 22, 13, i: 8 j: 6 min pos: 8 min val: 10
3, 4, 5, 7, 8, 9, 10, 13, 22, i: 8 j: 7 min pos: 8 min val: 13
3, 4, 5, 7, 8, 9, 10, 13, 22, i: 8 j: 8 min pos: 8 min val: 22

⁽¹⁾ 顺便说一句，当最小的剩余值已经在正确的位置时，交换是没有必要的，尽管它没有坏处。如果你想避免不必要的交换，你可以使用：

j++;
if (min_pos != j) {
    a[min_pos] = a[j];
    a[j] = min_sort ;
}

但是，如前所述，进行交换不是问题，所以这完全取决于您。

奇怪的选择排序行为

Strange selection sort behavior

java

sorting

selection