一.什么是算法？

高德納在《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》里對算法的歸納：

1. 輸入： 一個(gè)算法必須有零個(gè)或以上的輸入量
2. 輸出： 一個(gè)算法應(yīng)該有一個(gè)或以上輸出量
3. 明確性：算法的描述必須無歧義，實(shí)際運(yùn)行結(jié)果是確定的
4. 有效性： 必須在有效步驟內(nèi)結(jié)束
5. 有效性：又稱可行性。能夠被執(zhí)行者實(shí)現(xiàn)

二.算法

1. 冒泡排序
   （1）原理： 它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。 走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。
   

   （2）效果演示:
   冒泡排序.gif
   
   （3）代碼：

function sort(array){
  var i, j;
  for(i=0; i<array.length; i++){
    for(j=0; j<array.length-1-i; j++){
      if(array[j]<=array[j+1]){
         }else{
         swap(array, j, j+1)
         }
    }
  }
  return array;
}

function swap(array, a, b){
  var temp = array[a]
  array[a] = array[b]
  array[b] = temp
}

console.log(sort([3,5,38,44,15,36,26,27,2,46,4,19,47,50,48]))  //  [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

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

   （2）效果演示：
   選擇排序.gif
   
   （3）代碼：

function sort(array){
  var i
  var j
  var indexOfMin
  for(i=0; i<array.length; i++){
    indexOfMin = i
    for(j=i+1; j<array.length; j++){
      if(array[j]<array[indexOfMin]){
        indexOfMin = j
      }
    }
    if(indexOfMin !==i){
      swap(array, i, indexOfMin)
    }
  }
  return array;
}

function swap(array, a, b){
  var temp = array[a]
  array[a] = array[b]
  array[b] = temp
}

console.log(sort([2,44,38,5,47,15,36,26,27,3,46,4,19,50,48])) //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

3. 插入排序
   （1）原理：提取第一個(gè)元素，后一個(gè)元素與前一個(gè)元素對比，如果前一個(gè)元素大于后一個(gè)元素則，后一個(gè)元素向前移動一格，移動后再與前一個(gè)元素對比，直到前一個(gè)元素小于后一個(gè)元素為止。
   

   （2）效果演示：
   插入排序.gif
   
   （3）代碼

function Sort(array) {
  function swap(array, i, j) {
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
  var length = array.length,
      i,
      j;
  for (i = 1; i < length; i++) {
    for (j = i; j > 0; j--) {
      if (array[j - 1] > array[j]) {
        swap(array, j - 1, j);
      } else {
        break;
      }
    }
  }
  return array;
}

console.log(Sort([5,8,20,20,31,44,21,37,50,28,45,28,38,32])) //[5, 8, 20, 20, 21, 28, 28, 31, 32, 37, 38, 44, 45, 50]

4. 歸并排序
   （1）原理：把原始數(shù)組分成若干子數(shù)組,對每一個(gè)子數(shù)組進(jìn)行排序,繼續(xù)把子數(shù)組與子數(shù)組合并,合并后仍然有序,直到全部合并完,形成有序的數(shù)組。
   

   （2）效果演示：
   歸并排序.gif
   
   （3）代碼：

function Sort(array) {  
    var len = array.length;
    if(len < 2) {
        return array;
    }
    var middle = Math.floor(len / 2),
        left = array.slice(0, middle),
        right = array.slice(middle);
    return merge(Sort(left), Sort(right));
}
function merge(left, right)
{
    var result = [];
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    while (left.length)
        result.push(left.shift());
    while (right.length)
        result.push(right.shift());
    return result;
}
console.log(Sort([14,44,27,10,11,5,45,25,48,23,22,14,19,17]))  //[5, 10, 11, 14, 14, 17, 19, 22, 23, 25, 27, 44, 45, 48]

5. 快速排序
   （1）原理： 將第一個(gè)元素a依次與其他元素向?qū)Ρ?，比a大的元素放在右邊，比a小的放在左邊。然后將左右兩邊分別選擇一個(gè)a重復(fù)執(zhí)行以上步驟，直到排完為止。
   

   （2）效果演示：
   快速排序.gif

6. 隨機(jī)快速排序
   （1）原理：該原理與快速排序相似，不同的是選擇a不一定必須是第一個(gè)元素，是可以隨機(jī)取到的。
   

   （2）效果演示：
   隨機(jī)快速排序.gif
   
   (3)代碼

function quickSort(array) {　　
    if (array.length <= 1) {
        return array;
    }　　
    var pivotIndex = Math.floor(array.length / 2);　　
    var pivot = array.splice(pivotIndex, 1)[0];　　
    var left = [];　　
    var right = [];　　
    for (var i = 0; i < array.length; i++) {　　　　
        if (array[i] < pivot) {　　　　　　
            left.push(array[i]);　　　　
        } else {　　　　　　
            right.push(array[i]);　　　　
        }　　
    }　　
    return quickSort(left).concat([pivot], quickSort(right));
}
console.log(quickSort([44,40,40,31,30,36,22,49,6,48,16,49,19]))  //[6, 16, 19, 22, 30, 31, 36, 40, 40, 44, 48, 49, 49]

三.參考文章

前端筆記
常見算法