java - 奇怪的选择排序行为

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 ;
}

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