如何改善選擇排序？

Question

這是更多的學術/家庭作業問題？

它會更好改變

if (index_outer !== index_min) { 
    $P.swap(arr, index_outer, index_min); 
} 

到

$P.swap(arr, index_outer, index_min); 

，總是掉，因爲這是當index_outer確實有最小值的特殊情況？這將是一個無所作爲的交換，但同時它不會破壞任何東西。因爲這不會經常發生，所以我會減少使用if檢查的次數。

$P.swap = function (arr, i, j) { 
    var temp = arr[i]; 
    arr[i] = arr[j]; 
    arr[j] = temp; 
}; 

$P.selectionSort = function (arr) { 
    var index_outer, 
     index_inner, 
     index_min, 
     length = arr.length; 
    for (index_outer = 0; index_outer < length; index_outer++) { 
     index_min = index_outer; 
     for (index_inner = index_outer + 1; index_inner < length; index_inner++) { 
      if (arr[index_inner] < arr[index_min]) { 
       index_min = index_inner; 
      } 
     } 
     if (index_outer !== index_min) { 
      $P.swap(arr, index_outer, index_min); 
     } 
    } 
    return arr; 
}; 

Answer 1

我不認爲這總是一個好主意。如果數組被部分/完全排序，你會浪費對$ P.swap（）的調用。

作爲用於改善選擇排序嘗試從兩個分揀陣列通過取index_min和index_max結束同時。雖然比較次數保持不變，但通過次數會減少，從而減少總運行時間。