在什麼樣的測試案例中插入排序比選擇排序更好？清楚地描述測試用例。什麼類型的輸入區分選擇排序中的插入排序？
爲什麼選擇排序在該測試用例中執行比插入排序更差？
我回答這樣的第一個問題：
爲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