我最近在課堂上學習了基本排序（氣泡排序，插入排序和選擇排序），並且與運行時間有點混淆。小學排序運行時間比較
在老師給我們的作業上，一個問題問： 「3個基本排序中哪一個對所有鍵完全相同的文件運行速度最快？對於具有相反數據的文件，怎麼辦？
對於問題的第一部分，我不完全確定他們是什麼意思的「鑰匙」。那麼，這是否意味着有一個包含多個數據的大小爲1的數組？我不認爲「鍵」與「數據」是一樣的。我知道如果所有的數據都是有序的，那麼插入排序會是最快的，但我不確定這會對問題產生什麼影響。
對於問題的第二部分，我認爲這將是選擇排序，因爲無論數據中的反轉次數如何，都需要進行不斷的比較。插入排序和冒泡排序會導致交換過多。
我大多隻是對問題的第一部分感到困惑。
通常根據我的經驗，在對文件進行排序時，可以說文件由「記錄」組成，並且您正在移動每條記錄，以使其出現在它應該在之前的所有記錄之前。 「關鍵」是您正在使用的記錄的任何部分，以確定一條記錄應該在另一條記錄之前還是之後。如果您只是對數字或字符串進行排序，那麼「鍵」就是整個記錄。在其他情況下，每條記錄可能是某人的學校成績單，出於某種原因，您希望按照學生的姓名對這些記錄進行排序，因此記錄中的大部分數據都不是關鍵的一部分。如果您的老師已經說過他或她認爲是交換過程中移動的數據單元，那將會有所幫助。
我認爲你正在考慮關於記錄已經排序的情況，所有相同的密鑰就是這種情況。
對於記錄順序完全相反的情況，問題並不在於選擇排序的比較次數受數據初始順序影響的程度;相反，問題（關於比較）是，任何算法能否比其他算法執行更少。通常我們說插入排序的比較比選擇少，但在這種情況下，您可能會顯示其他內容。當然，你也需要看看泡沫排序實際需要多少次比較。
你的老師的問題是：
其中的3種基本的運行速度最快的文件具有相同的所有鍵？
換句話說，問題是：
其中3個基本各種各樣的具有最小時間複雜度爲最佳的案例？
時間複雜度：一個漸近數學符號，表示運行時間與輸入大小相關的增長率。
最佳案例：該列表已經排序，這包括相同條目的情況。
3個基本類別是什麼？
插入排序與O(n)的最佳案例。
選擇種類與O(n^2)最佳案例。
料斗分類與O(n+k)對最佳案例。
所以在最好的情況下最好的基本排序算法是與O(n)插入排序。
你在正確的軌道上。當被排序的集合中的所有內容都是相同的[['a'，'a'，'a'，'a'，..]'，即不交換時，哪個算法是最快的。當設置爲倒序時，哪個算法最快，即。許多掉期。 – deanosaur
因此插入排序爲第一個，並選擇第二個？ – user3421510
我認爲你是正確的插入排序會很好，當幾乎沒有掉期，也就是說，當集合已經大多數排序。當有大量掉期交易時，您的選擇排序可能會更好。但是，除非您使用小數據集，否則這兩個算法都不會執行mergesort。 – deanosaur