寫了兩個鏈表的排序，亂數測到50000個的時候，插入排序開始比選擇排序要慢了..
按理說選擇排序不是會有更多的順序訪問嗎，對鏈表不是應該更加不利嗎
uj5u.com熱心網友回復：
鏈表只有比較和賦值，無需考慮交換：選擇排序是每次遍歷未排序的數，從中選擇一個最小的（比較n*(n-1)/2次，每次賦值（1~n次+賦值next（n次）），插入鏈表（n次）
插入排序每次從未排序的數中取一個（n次）,插入鏈表中(比較(1~n)次，賦值next（n次）)
比較 + 插入 + 賦值 + 設定next
選擇排序最好：n*(n-1)/2 + n + n+ n*(n-1)/2; 最壞：n*(n-1)/2 + n + n*(n-1);
插入排序最好：n + n + 0;最壞：n*(n-1)/2 + n + n*(n-1)/2;
隨機資料越多，越接近亂序，最壞情況。
針對鏈表來說，插入是要優于選擇的。
具體問題還要看你的代碼。
如果是陣列排序的話，可以參考關于插入排序和選擇排序的比較
uj5u.com熱心網友回復：
單鏈表插入排序，，，真的有意義嗎？陣列插入排序是向前查找，可是單鏈表根本不滿足向前查找的條件。
雙向鏈表還可以搞一搞。
uj5u.com熱心網友回復：
單鏈表倒是也能從前向后掃描.轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/46614.html
標籤：數據結構與算法