摘要：插入排序插入排序應(yīng)該算是最簡(jiǎn)單和容易理解的排序算法。平均來說插入排序算法復(fù)雜度為。在最好的情況，冒泡排序需要次交換，而插入排序只要最多交換。因此很多現(xiàn)代的算法教科書避免使用冒泡排序，而用插入排序替換之?？焖倥判蛞彩且环N分治的遞歸算法。

計(jì)算的 時(shí)間復(fù)雜度（最差、平均、和最好性能），依據(jù)列表（list）的大小(n)。一般而言，好的性能是O(n log n)，且壞的性能是O(n^2)。對(duì)于一個(gè)排序理想的性能是O(n)。僅使用一個(gè)抽象關(guān)鍵比較運(yùn)算的排序算法總平均上總是至少需要O(n log n)。

插入排序應(yīng)該算是最簡(jiǎn)單和容易理解的排序算法。它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。具有n個(gè)元素時(shí)它需要經(jīng)過n-1趟排序。對(duì)于p = 1到p = n-1趟，插入排序保證從位置0到位置p上的元素為已排序狀態(tài)。它就是基于這個(gè)事實(shí)來排序的。

function sort(arr) {
  if(arr.length <= 1) {
    return arr
  }

  for(var i=0; i=0; j--) {
      if(arr[j+1] < arr[j]) {
        var temp = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = temp
      }
    }
  }

  return arr
}

如果目標(biāo)是把n個(gè)元素的序列升序排列，那么采用插入排序存在最好情況和最壞情況。最好情況就是，序列已經(jīng)是升序排列了，在這種情況下，需要進(jìn)行的比較操作需(n-1)次即可。最壞情況就是，序列是降序排列，那么此時(shí)需要進(jìn)行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數(shù)減去(n-1)次。平均來說插入排序算法復(fù)雜度為O(n^2)。因而，插入排序不適合對(duì)于數(shù)據(jù)量比較大的排序應(yīng)用。但是，如果需要排序的數(shù)據(jù)量很小，例如，量級(jí)小于千，那么插入排序還是一個(gè)不錯(cuò)的選擇。 插入排序在工業(yè)級(jí)庫中也有著廣泛的應(yīng)用，在STL的sort算法和stdlib的qsort算法中，都將插入排序作為快速排序的補(bǔ)充，用于少量元素的排序（通常為8個(gè)或以下）

冒泡排序是與插入排序擁有相等的運(yùn)行時(shí)間，但是兩種算法在需要的交換次數(shù)卻很大地不同。在最好的情況，冒泡排序需要O(n^2)次交換，而插入排序只要最多O(n)交換。冒泡排序的實(shí)現(xiàn)（類似下面）通常會(huì)對(duì)已經(jīng)排序好的數(shù)列拙劣地運(yùn)行O(n^2)，而插入排序在這個(gè)例子只需要O(n)個(gè)運(yùn)算。因此很多現(xiàn)代的算法教科書避免使用冒泡排序，而用插入排序替換之。冒泡排序如果能在內(nèi)部循環(huán)第一次運(yùn)行時(shí)，使用一個(gè)旗標(biāo)來表示有無需要交換的可能，也可以把最好的復(fù)雜度降低到O(n)。在這個(gè)情況，已經(jīng)排序好的數(shù)列就無交換的需要。若在每次走訪數(shù)列時(shí)，把走訪順序反過來，也可以稍微地改進(jìn)效率。有時(shí)候稱為雞尾酒排序，因?yàn)樗惴〞?huì)從數(shù)列的一端到另一端之間穿梭往返。

冒泡排序算法的運(yùn)作如下：

比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。

對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。

針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

由于它的簡(jiǎn)潔，冒泡排序通常被用來對(duì)于程序設(shè)計(jì)入門的學(xué)生介紹算法的概念。

function bubbleSort(arr) {
  if(arr.length <= 1) {
    return arr;
  }
  for(var j=0; j arr[i+1]) {
        var tmp = arr[i];
        arr[i] = arr[i+1];
        arr[i+1] = tmp;
      }
    }
  }

  return arr;
}

選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
選擇排序的主要優(yōu)點(diǎn)與數(shù)據(jù)移動(dòng)有關(guān)。如果某個(gè)元素位于正確的最終位置上，則它不會(huì)被移動(dòng)。選擇排序每次交換一對(duì)元素，它們當(dāng)中至少有一個(gè)將被移到其最終位置上，因此對(duì)n個(gè)元素的表進(jìn)行排序總共進(jìn)行至多n-1次交換。在所有的完全依靠交換去移動(dòng)元素的排序方法中，選擇排序?qū)儆诜浅：玫囊环N。

選擇排序的交換操作介于 0 和(n-1)次之間。選擇排序的比較操作為n(n-1)/2次之間。選擇排序的賦值操作介于0和3(n-1)次之間。比較次數(shù)O(n^2)，比較次數(shù)與關(guān)鍵字的初始狀態(tài)無關(guān)，總的比較次數(shù) N=(n-1)+(n-2)+...+1=n(n-1)/2。交換次數(shù)O(n),最好情況是，已經(jīng)有序，交換0次；最壞情況是，逆序，交換n-1次。交換次數(shù)比冒泡排序較少，由于交換所需CPU時(shí)間比比較所需的CPU時(shí)間多, n值較小時(shí)，選擇排序比冒泡排序快。
原地操作幾乎是選擇排序的唯一優(yōu)點(diǎn)，當(dāng)空間復(fù)雜度要求較高時(shí)，可以考慮選擇排序；實(shí)際適用的場(chǎng)合非常罕見。

function selectionSort(arr) {
    if(arr.length <= 1) {
        return arr
    }
    var i, j, min;
    var temp;
    for (i = 0; i < arr.length - 1; i++) {
        min = i;
        for (j = i + 1; j < arr.length; j++) {
            if (arr[min] > arr[j])
                min = j;
                temp = arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
        }
    }
    return arr
}

快速排序使用分治法（Divide and conquer）策略來把一個(gè)序列（list）分為兩個(gè)子序列（sub-lists）。

步驟為：

從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"（pivot），

重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。

遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個(gè)算法總會(huì)結(jié)束，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。

正如它的名字，快速排序是在時(shí)間中最快的已知排序算法，它的平均運(yùn)行時(shí)間是O(NlogN)?？焖倥判蛞彩且环N分治的遞歸算法。將數(shù)組S排序的基本算法由下列簡(jiǎn)單的四步組成：

如果S中元素個(gè)數(shù)是0或1，則返回

取S中任一元素v，稱之為樞紐元

將S - {v}分成兩個(gè)不相交的集合：S1 = {x∈S - {v} | x ≤ v}和S2 = {x∈S - {v} | x ≥ v}

返回{quicksort(S1)}，繼續(xù)v，繼而quicksort(S2)
由于對(duì)樞紐元的處理會(huì)導(dǎo)致第三步中的分割不唯一，因此，我們希望把等于樞紐元的大約一半的關(guān)鍵字分到S1中，而另外一半分到S2中，那怎么去選擇一個(gè)好的樞紐元呢？

選取樞紐元
一種錯(cuò)誤的方法
通常的，沒有經(jīng)過充分考慮的選擇是將第一個(gè)元素用作樞紐元。如果輸入是隨機(jī)的，那么這是可以接受的，但是如果輸入是預(yù)排序或是反序的，那么這樣的樞紐元就會(huì)產(chǎn)生一個(gè)劣質(zhì)的分割，因?yàn)樗械脑夭皇嵌急粍澣隨1就是被劃入S2。
一種安全的作法
一種安全的方針是隨機(jī)選取樞紐元。但是另一方面，隨機(jī)數(shù)的生成一般是昂貴的，根本減少不了算法奇遇部分的平均運(yùn)行時(shí)間。
三數(shù)中值分割法
一組N個(gè)數(shù)的中值是第Math.ceil(N/2)個(gè)最大的數(shù)。樞紐元的最好的選擇是數(shù)組的中值。不幸的是，這很難算出，且會(huì)減慢快速排序的速度。因此一般的做法是使用左端、右端和中心位置上的三個(gè)元素的中值作為樞紐元。例如，輸入為8, 1, 4, 9, 6, 3, 5, 2, 7, 0，它的左邊元素是8，右邊元素是0，中心位置為Math.floor((left + right) / 2)上的元素是6，于是樞紐元v=6。

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr.slice(0);
  }

  var left = [];
  var right = [];
  var mid = [arr[0]]; //first number as a pivot

  for (var i = 1; i < arr.length; i++) {
    if (arr[i] < mid[0]) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return quickSort(left).concat(mid.concat(quickSort(right)));
}