在什么样的测试案例中插入排序比选择排序更好？清楚地描述测试用例。什么类型的输入区分选择排序中的插入排序？
为什么选择排序在该测试用例中执行比插入排序更差？
我回答这样的第一个问题：
为O（n 2 ）。当插入排序给出一个列表时，它将获取当前元素并将其插入到列表的适当位置，每次插入时调整列表。这与在纸牌游戏中安排纸牌类似。
而第二个问题：
由于选择排序总是做N（N-1）/ 2比较，但在最坏的情况下，它仅会做N-1互换。
但我不确定我的答案，有什么建议吗？
对于插入排序比选择排序快的情况，请考虑如果输入数组已经排序会发生什么情况。在这种情况下，插入排序使得O（n）比较并且不交换。选择排序总是使Θ（n ）比较和O（n）交换，所以给定一个合理的大排序输入数组插入排序将优于选择排序。
对于选择排序优于插入排序的情况，我们需要有点棘手。插入排序的最坏情况是当输入数组被反向排序时。在这种情况下，它使Θ（n ）比较和Θ（n ）交换。将此与选择排序进行比较，该排序总是使Θ（n ）比较和O（n）交换。如果比较和掉期花费大致相同的时间，那么选择排序可能会比插入排序更快，但您必须实际对其进行配置才能找出。真的，它归结为实施。在这种情况下，插入排序的一个很好的实现可能实际上击败了选择排序的错误实现。
作为一个棘手的解决方案，尝试制作自定义数据类型，其中比较便宜，但交换需要花费很长时间才能完成。这应该适用于第二种情况。
您没有提供问题一的测试用例。 – Kevin
也许我不明白测试用例是什么，你可以向我解释一下吗？ – r4b
他们希望像“当输入列表已经按降序排序时，性能对选择排序更糟，例如'[4,3,2,1]'”。 （我不知道这是否真的，这只是答案格式的一个例子） – Kevin