选择排序

Question

我刚刚开始学习sorting，我的class目前正在进行选择。在我的任务中，我必须按增加的顺序对number list进行排序，并使用array外观和当前的比较#显示，我们必须在纸上这样做。

这些数字是：

90, 8, 7, 56, 123, 235, 9, 1, 653.

到目前为止，这就是我所拥有的(排序列表以粗体表示)：

90|8|7|56|123|235|9|1|653



 # of comparisons: 0

---

**1**|8|7|56|123|235|9|90|653 

 # of comparisons: 1

---

**1**|**7**|8|56|123|235|9|90|653 

 # of comparisons: 2

这基本上就是我要问的问题。因为8已经在正确的位置，还会进行比较吗？还是会直接转到下一个值？那么，会不会是：

---

**1**|**7**|**8**|56|123|235|9|90|653 

 # of comparisons: 3

---

or would it be: 

---

**1**|**7**|**8**|**9**|123|235|56|90|653 

 # of comparisons: 3

---

我相信前者是正确的，但我只想要求你们确保我对此有正确的理解。

Answer 1

如果您了解如何选择列表中最小的元素，则会有所帮助。一种有效的方法是首先假设第一个未排序元素是最小的，然后迭代剩余的未排序元素，测试这个假设。

90, 8, 7, 56, 123, 235, 9, 1, 653

如果这是您的列表，那么首先假设90是最小的。然后，你比较90到8.8是小于90，所以你更新你的假设是8是最小的。这是一个比较。你把8比7.7比较小，所以现在你的假设是7是最小的。2比较。你把7比56。7比较小，所以你的假设没有改变。3比较。需要8个比较才能完成列表，并确定1是最小的。

既然您知道1是最小的，那么就用列表中的第一个元素交换它。

1, 8, 7, 56, 123, 235, 9, 90, 653

现在，1在正确的位置，你不必再担心它了。现在，您需要对以下列表进行排序。

8, 7, 56, 123, 235, 9, 90, 653

7比较之后，确定7是列表中最小的元素。用第一个元素交换它。

7, 8, 56, 123, 235, 9, 90, 653

现在，您需要对以下列表进行排序。

8, 56, 123, 235, 9, 90, 653

请记住，即使8已经位于正确的排序位置，但在您将其与未排序列表中的所有其他项进行比较之前，不知道8是列表中最小的元素。因此，您仍然必须进行6次比较，以确定8是最小的元素。但是，由于8是列表中的第一个元素，所以不需要交换它。你可以把它留在原处。

8, 56, 123, 235, 9, 90, 653

现在，您需要对以下列表进行排序。

56, 123, 235, 9, 90, 653

以此类推。

Answer 2

您应该分别计算比较的数量和掉期的数量。如果数组的未排序部分中有n元素，那么需要n-1比较来发现哪一个最小。一旦你知道哪一个是最小的，那么你可能需要或不需要交换。因此，我认为所取得的进展如下：

90-8

1|8|7|56|123|235|9|90|653# of comparisons: 8 # of swaps: 1

1|7|8|56|123|235|9|90|653# of comparisons: 15 # of swaps: 2

1|7|8|56|123|235|9|90|653# of comparisons: 21 # of swaps: 2

1|7|8|9|123|235|56|90|653# of comparisons: 26 # of swaps: 3

等。

Answer 3

如果你所说的“比较”是指一次通过，那么前者是正确的。虽然你可以盯着数字，并知道8在正确的位置，但算法并不那么聪明，而且还必须检查列表中未排序部分的其余数字，以确定。

你可能会问：“但7岁之后就有8岁了，那么怎么可能有更小的东西呢？”未排序列表中可能有重复(另7个)。

维基百科例子