[演算法(Algorithm)] 選擇排序法(Selection Sort)

• 選擇排序作法：
  • 將資料分成已排序、未排序兩部份
  • 依序由未排序中找最小值(or 最大值)，加入到已排序部份的末端
• 時間複雜度(Time Complexity)
  • Best Case：Ο(n²)
  • Worst Case：Ο(n²)
  • Average Case：Ο(n²)
  • 說明：
    • 無論資料順序如何，都會執行兩個迴圈
• 空間複雜度(Space Complexity)：θ(1)
• 穩定性(Stable/Unstable)：不穩定(Unstable)
• Demo:
• 演算法
  • JS

  var swap = function(data, i, j){ 
      var tmp = data[i];
      data[i] = data[j];
      data[j] = tmp;
  };
      
  var selectionSort = function(data){
      for(var i = 0; i < data.length; i ++){
          var min = i;
          for(var j = i + 1; j < data.length; j++){
              if(data[j] < data[min])
                  min = j;
          }
          if( i != min)
              swap(data, i, min);
                   
      }
  };