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

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

?

對(duì)于長(zhǎng)度為N的數(shù)組，選擇排序需要大約(N^2/2)次比較和N次交換
運(yùn)行時(shí)間和輸入無(wú)關(guān)（僅與輸入的長(zhǎng)度有關(guān)）
數(shù)據(jù)移動(dòng)是最少的

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)
  }
}

?

插入排序所需的時(shí)間依賴于輸入中元素的初始順序。
對(duì)于隨機(jī)排列的長(zhǎng)度為N且主鍵不重復(fù)的數(shù)組，平局情況下插入排序需要~(N^2/4)次比較和~(N^2/4)次交換。最壞情況下需要~(N^2/2)次比較和~(N^2/4)次交換，最好情況下需要(N-1)次比較和0次交換。
插入排序?qū)τ诓糠钟行虻臄?shù)組很有效，下面是幾種典型的部分有序的數(shù)組：

數(shù)組中每個(gè)元素距離它最終的位置都不遠(yuǎn)。

一個(gè)有序的大數(shù)組接一個(gè)小數(shù)組。

數(shù)組中只有幾個(gè)元素的位置不正確。

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)
      }
    }
  }
}

?

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

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;
  }
}

?

要將一個(gè)數(shù)組排序，可以先（遞歸地）將它分成兩半分別排序，然后將結(jié)果歸并起來(lái)。
歸并排序最吸引人的性質(zhì)是它能夠保證將任意長(zhǎng)度為N的數(shù)組排序所需時(shí)間和NlogN成正比，主要缺點(diǎn)是它所需的額外空間和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);
}

對(duì)于長(zhǎng)度為N的任意數(shù)組，自頂向下的歸并排序需要(1/2)NlgN至NlgN次比較。
對(duì)于長(zhǎng)度為N的任意數(shù)組，自頂向下的歸并排序最多需要訪問(wèn)數(shù)組6NlgN次。
通過(guò)一些細(xì)致的思想可以大幅度縮短歸并排序的運(yùn)行時(shí)間：

對(duì)小規(guī)模子數(shù)組使用插入排序

測(cè)試數(shù)組是否已經(jīng)有序

不將元素復(fù)制到輔助數(shù)組

//自底向上的歸并排序
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));
    }
  }
}

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

?

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

//快速排序
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;    
}

快速排序改進(jìn)方法：


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

三取樣切分，使用子數(shù)組的一小部分元素的中位數(shù)來(lái)切分?jǐn)?shù)組

熵最優(yōu)的排序


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

//三向切分的快速排序
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時(shí)，交換arr[lt]和arr[i]，將lt和i加1
      exch(arr, lt++, i++);
    }else if(less(v, arr[i])){
      //arr[i]大于v時(shí)，交換arr[i]和arr[gt]，將gt減1
      exch(arr, i, gt--);
    }else{
      //arr[i]等于v時(shí)，將i加1
      i++;
    }
  }
  quick3WaySort(arr, lo, lt-1);
  quick3WaySort(arr, gt+1, hi);
}

?

?