[演算法(Algorithm)] 搖晃排序法(Shaker Sort)

• 搖晃排序法又叫雙向氣泡排序法(Bidirectional Bubble Sort)、雞尾酒排序法(Cocktail Sort)、波浪排序法(Ripple Sort)、搖曳排序法(Shuffle Sort)、飛梭排序法(Shuttle Sort)、歡樂時光排序法(Happy Hour Sort)
• 搖晃排序法為氣泡排序法的改良
• 將資料分成未排序及已排序兩部份
  • 利用left、right來識別已排序和未排序的資料
• 搖晃排序作法：
  • 每回合會利用氣泡排序法
    • 將未排序資料中最大值，移到未排序資料的最右邊
    • 將未排序資料中最小值，移到未排序資料的最左邊
• 時間複雜度(Time Complexity)
  • Best Case：Ο(n)
  • Worst Case：Ο(n²)
  • Average Case：Ο(n²)
• 空間複雜度(Space Complexity)：θ(1)
• 穩定性(Stable/Unstable)：穩定(Stable)
• Demo:
• 演算法
  • JS

  var swap = function(data, i, j){ 
      var tmp = data[i];
      data[i] = data[j];
      data[j] = tmp;
  };
  
  var shakerSort = function(data){
      var left = 0;
      var right = data.length -1;
      var shift = 0;
          
      while( left < right){
          for(var i = left; i < right; i++) {
              if(data[i] > data[i+1]){  //將最大值往右排
                  swap(data, i, i+1);
                  shift = i;
              }
          }
          right = shift;
          for(var i = right; i > left; i--){
              if(data[i] < data[i-1]){  //將最小值往左排
                  swap(data, i, i - 1);
                  shift = i;
              }           
          }
          left = shift;
      }   
  };