在什么样的测试用例中插入排序比选择排序更好？清楚地描述测试用例 . 为什么选择排序比该测试用例中的插入排序更差？
我回答了第一个问题：
O（n2） . 当插入排序给出一个列表时，它接受当前元素并将其插入列表的适当位置，每次插入时调整列表 . 它类似于在纸牌游戏中安排卡片 .
第二个问题：
因为Selection Sort总是进行n（n-1）/ 2次比较，但在最坏的情况下，它只会进行n-1次交换 .
但我不确定我的答案，有什么建议吗？
对于插入排序比选择排序更快的情况，请考虑如果输入数组已经排序会发生什么 . 在这种情况下，插入排序进行O（n）比较而不进行交换 . 选择排序总是进行Θ（n2）比较和O（n）交换，因此给定一个相当大的排序输入数组插入排序将优于选择排序 .
对于选择排序优于插入排序的情况，我们需要有点棘手 . 插入排序的最坏情况是输入数组被反向排序 . 在这种情况下，它进行Θ（n2）比较和Θ（n2）交换 . 将此与选择排序进行比较，选择排序总是进行Θ（n2）比较和O（n）交换 . 如果比较和交换花费的时间大致相同，那么选择排序可能比插入排序更快，但您必须实际对其进行分析才能找到答案 . 真的，它归结为实施 . 在这种情况下，插入排序的良好实现实际上可能击败了选择排序的错误实现 .
作为一个棘手的解决方案，尝试制作一个自定义数据类型，其中比较便宜，但交换需要非常非常长的时间才能完成 . 这应该适用于你的第二个案例 .
1 回答
对于插入排序比选择排序更快的情况，请考虑如果输入数组已经排序会发生什么 . 在这种情况下，插入排序进行O（n）比较而不进行交换 . 选择排序总是进行Θ（n2）比较和O（n）交换，因此给定一个相当大的排序输入数组插入排序将优于选择排序 .
对于选择排序优于插入排序的情况，我们需要有点棘手 . 插入排序的最坏情况是输入数组被反向排序 . 在这种情况下，它进行Θ（n2）比较和Θ（n2）交换 . 将此与选择排序进行比较，选择排序总是进行Θ（n2）比较和O（n）交换 . 如果比较和交换花费的时间大致相同，那么选择排序可能比插入排序更快，但您必须实际对其进行分析才能找到答案 . 真的，它归结为实施 . 在这种情况下，插入排序的良好实现实际上可能击败了选择排序的错误实现 .
作为一个棘手的解决方案，尝试制作一个自定义数据类型，其中比较便宜，但交换需要非常非常长的时间才能完成 . 这应该适用于你的第二个案例 .