摘要：算法筆記版排序本文內容根據和的算法第四版整理，原代碼為語言，自己修改為版本，僅供參考。希爾排序的思想是使數組中任意間隔為的元素都是有序的。使用遞增序列，，，，，的希爾排序所需的比較次數不會超過的若干倍乘以遞增序列的長度。

function sort(arr){
  //此處添加不同的排序算法實現
}
//比較兩個數的大小
function less(a, b){
  return a < b
} 
//交換數組中兩個數的位置
function exch(arr, i, j){
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
//判斷數組是否是有序的
function isSorted(arr){
  var len = arr.length;
  for(var i = 1; i < len; i++){
    if(less(arr[i], arr[j])){
      return false;
    }
  }
  return true;
}

?

對于長度為N的數組，選擇排序需要大約(N^2/2)次比較和N次交換
運行時間和輸入無關（僅與輸入的長度有關）
數據移動是最少的

function selectionSort(arr){
  var len = arr.length;
  for(var i = 0; i < len; i++){
    var min = i;
    for(var j = i+1; j < len; j++){
      if(less(arr[j], arr[min])){
        min = j;
      }      
    }
    exch(arr, i, min)
  }
}

?

插入排序所需的時間依賴于輸入中元素的初始順序。
對于隨機排列的長度為N且主鍵不重復的數組，平局情況下插入排序需要~(N^2/4)次比較和~(N^2/4)次交換。最壞情況下需要~(N^2/2)次比較和~(N^2/4)次交換，最好情況下需要(N-1)次比較和0次交換。
插入排序對于部分有序的數組很有效，下面是幾種典型的部分有序的數組：

數組中每個元素距離它最終的位置都不遠。

一個有序的大數組接一個小數組。

數組中只有幾個元素的位置不正確。

function insertionSort(arr){
  var len = arr.length;
  for(var i = 1; i < len; i++){
    for(var j = i; j > 0; j--){
      if(less(arr[j], arr[j-1])){
        exch(arr, j, j-1)
      }
    }
  }
}

?

希爾排序是基于插入排序的快速排序算法。
希爾排序的思想是：使數組中任意間隔為h的元素都是有序的。這樣的數組被稱為h有序數組。在進行排序時，如果h很大，我們就能將元素移動到很遠的地方，為實現更小的h有序創造方便。
使用遞增序列1，4，13，40，121，364…的希爾排序所需的比較次數不會超過N的若干倍乘以遞增序列的長度。

function shellSort(arr){
  var len = arr.length,
      h = 1;
  while(h < len/3){
    h = 3*h+1;
  }
  while(h >=1){
    for(var i = h; i < len; i++){
      for(var j = i; j >= h; j-=h){
        if(less(arr[j], arr[j-h])){
          exch(arr, j, j-h)
        }
      }
    }
    h = (h-1)/3;
  }
}

?

要將一個數組排序，可以先（遞歸地）將它分成兩半分別排序，然后將結果歸并起來。
歸并排序最吸引人的性質是它能夠保證將任意長度為N的數組排序所需時間和NlogN成正比，主要缺點是它所需的額外空間和N成正比。

//原地歸并的抽象方法
function merge(arr, lo, mid, hi){
  var aux = [],
      i = lo,
      j = mid+1;
  for(var k = lo; k <= hi; k++){
    aux[k] = arr[k]
  }
  
  for(var m = lo; m <= hi; m++){
    if(i > mid){
      arr[m] = aux[j++];
    }else if(j > hi){
      arr[m] = aux[i++];
    }else if(less(aux[j], aux[i])){
      arr[m] = aux[j++];
    }else{
      arr[m] = aux[i++];
    }
  }  
}
//自頂向下的歸并排序
function mergeSort(arr, lo, hi){
  if(hi <= lo){
    return;
  }
  var mid = Math.floor(lo + (hi - lo)/2);
  mergeSort(arr, lo, mid);
  mergeSort(arr, mid+1, hi);
  merge(arr, lo, mid, hi);
}

對于長度為N的任意數組，自頂向下的歸并排序需要(1/2)NlgN至NlgN次比較。
對于長度為N的任意數組，自頂向下的歸并排序最多需要訪問數組6NlgN次。
通過一些細致的思想可以大幅度縮短歸并排序的運行時間：

對小規模子數組使用插入排序

測試數組是否已經有序

不將元素復制到輔助數組

//自底向上的歸并排序
function mergeSortBU(arr){
  var len = arr.length;
  for(var sz = 1; sz < len; sz = sz+sz){
    for(var lo = 0; lo < len-sz; lo += sz+sz){
      merge(arr, lo, lo+sz-1, Math.min(lo+sz+sz-1, len-1));
    }
  }
}

對于長度為N的任意數組，自底向上的歸并排序需要(1/2)NlgN至NlgN次比較，最多訪問數組6NlgN次。
當數組長度為2的冪時，自頂向下和自底向上的歸并排序所用的比較次數和數組訪問次數相同，其他時候兩種方法的比較和數組訪問次序會有所不同。
自底向上的歸并排序比較適合用鏈表組織的數據。

?

快速排序是一種分治的排序算法。
將長度為N的無重復數組排序，快速排序平均需要(~2NlnN)次比較（以及1/6的交換）
快速排序最多需要約(N^2/2)次比較，但隨機打亂數組能夠預防這種情況。

//快速排序
function quickSort(arr, lo, hi){
  if(hi <= lo){
    return;
  }
  var j = partition(arr, lo, hi);
  quickSort(arr, lo, j-1);
  quickSort(arr, j+1, hi);
}
//快速排序的切分
function partition(arr, lo, hi){
  var i = lo,
      j = hi + 1,
      v = arr[lo];
  while(true){
    while(less(arr[++i], v)){
      if(i === hi){
        break;
      }
    }
    while(less(v, arr[--j])){
      if(j === lo){
        break;
      }
    }
    if(i >= j){
      break;
    }
    exch(arr, i, j);
  }
  exch(arr, lo, j);
  return j;    
}

快速排序改進方法：


切換到插入排序
//快速排序
function quickSort(arr, lo, hi){
  //if(hi <= lo){
  //  return;
  //}
  if(hi <= lo + M){
  //轉換參數M的最佳值與系統相關
  //大多數情況下5~15之間的任意值都能令人滿意
    insertionSort(arr, lo, hi);
    return;
  }
  var j = partition(arr, lo, hi);
  quickSort(arr, lo, j-1);
  quickSort(arr, j+1, hi);
}

三取樣切分，使用子數組的一小部分元素的中位數來切分數組

熵最優的排序


對于存在大量重復元素的數組，三向切分的快速排序比標準的快速排序的效率高得多。
對于大小為N的數組，三向切分的快速排序需要~(2ln2)NH次比較，其中H為由主鍵值出現頻率定義的香農信息量。

//三向切分的快速排序
function quick3WaySort(arr, lo, hi){
  if(hi <= lo){
    return;
  }
  var lt = lo,
      i = lo + 1,
      gt = hi;
  var v = arr[lo];
  while(i <= gt){
    if(less(arr[i], v)){
      //arr[i]小于v時，交換arr[lt]和arr[i]，將lt和i加1
      exch(arr, lt++, i++);
    }else if(less(v, arr[i])){
      //arr[i]大于v時，交換arr[i]和arr[gt]，將gt減1
      exch(arr, i, gt--);
    }else{
      //arr[i]等于v時，將i加1
      i++;
    }
  }
  quick3WaySort(arr, lo, lt-1);
  quick3WaySort(arr, gt+1, hi);
}

?

?