java - 奇怪的选择排序行为

我试图尝试实现自己的选择排序代码。到目前为止，代码sorta起作用了……它的行为很奇怪。

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

最佳答案

由于这几乎可以肯定是您的教育过程（实际代码只会调用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;
}

现在这是一个很好的方法，稍后将这两个信息用于交换过程（1）：

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

（1）顺便说一句，当最小的剩余值已经在正确的位置时，则不需要交换，尽管这没有害处。如果要避免不必要的交换，可以使用：

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

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