一：冒泡排序

冒泡排序（Bubble Sort）也是一種簡單直觀的排序算法卑硫。它重復(fù)地走訪過要排序的數(shù)列基括，一次比較兩個(gè)元素匠璧，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換酿雪，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

算法步驟：

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

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

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

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

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len - 1; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        // 相鄰元素兩兩對比
                var temp = arr[j+1];        // 元素交換
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

二：選擇排序

算法步驟：

首先在未排序序列中找到最小（大）元素则果，存放到排序序列的起始位置

再從剩余未排序元素中繼續(xù)尋找最锌钋唷（大）元素燎含，然后放到已排序序列的末尾屏箍。

重復(fù)第二步鹦付，直到所有元素均排序完畢秉继。

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 尋找最小的數(shù)
                minIndex = j;                 // 將最小數(shù)的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

三：插入排序

算法步驟：

將第一待排序序列第一個(gè)元素看做一個(gè)有序序列辑鲤，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列宁赤。

從頭到尾依次掃描未排序序列佛猛，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置。（如果待插入的元素與有序序列中的某個(gè)元素相等漩勤，則將待插入元素插入到相等元素的后面。）

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}

四：希爾排序

希爾排序，也稱遞減增量排序算法半哟，是插入排序的一種更高效的改進(jìn)版本体捏。但希爾排序是非穩(wěn)定排序算法。

希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：

插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)韵洋，效率高搪缨，即可以達(dá)到線性排序的效率呻待；
但插入排序一般來說是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位瑞妇；
希爾排序的基本思想是：先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序默勾，待整個(gè)序列中的記錄“基本有序”時(shí)碉渡，再對全體記錄進(jìn)行依次直接插入排序。

算法步驟：

選擇一個(gè)增量序列 t1母剥，t2滞诺，……，tk环疼，其中 ti > tj, tk = 1习霹；

按增量序列個(gè)數(shù) k，對序列進(jìn)行 k 趟排序炫隶；

每趟排序淋叶，根據(jù)對應(yīng)的增量 ti，將待排序列分割成若干長度為 m 的子序列伪阶，分別對各子表進(jìn)行直接插入排序煞檩。僅增量因子為 1 時(shí)处嫌，整個(gè)序列作為一個(gè)表來處理，表長度即為整個(gè)序列的長度斟湃。

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) {          //動(dòng)態(tài)定義間隔序列
        gap =gap*3+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;
}

五：歸并排序

歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法锰霜。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。

作為一種典型的分而治之思想的算法應(yīng)用桐早，歸并排序的實(shí)現(xiàn)由兩種方法：

自上而下的遞歸（所有遞歸的方法都可以用迭代重寫癣缅，所以就有了第 2 種方法）；
自下而上的迭代哄酝；
算法步驟：

申請空間友存，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列陶衅；

設(shè)定兩個(gè)指針屡立，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置；

比較兩個(gè)指針?biāo)赶虻脑夭缶x擇相對小的元素放入到合并空間膨俐，并移動(dòng)指針到下一位置；

重復(fù)步驟 3 直到某一指針達(dá)到序列尾罩句；

將另一序列剩下的所有元素直接復(fù)制到合并序列尾焚刺。

function mergeSort(arr) {  // 采用自上而下的遞歸方法
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(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;
}

六：快速排序

快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下门烂，排序 n 個(gè)項(xiàng)目要 Ο(nlogn) 次比較乳愉。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見屯远。事實(shí)上蔓姚，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來慨丐。

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

快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用。本質(zhì)上來看房揭，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法备闲。

算法步驟：

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

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

遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序；

function quickSort(array, left, right) {
  var partitionIndex,
      left = typeof left == 'number' ? left : 0,
      right = typeof right == 'number' ? right : array.length-1;
  if (left < right) {
    partitionIndex = partition(array, left, right);//切分的基準(zhǔn)值
    quickSort(array, left, partitionIndex-1);
    quickSort(array, partitionIndex+1, right);
  }
  return array;
}
function partition(array, left ,right) {   //分區(qū)操作
  for (var i = left+1, j = left; i <= right; i++) {//j是較小值存儲(chǔ)位置的游標(biāo)
    array[i] < array[left] && swap(i, ++j, array);//以第一個(gè)元素為基準(zhǔn)
  }
  swap(left, j, array);            //將第一個(gè)元素移至中間
  return j;
}

七：堆排序

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法瞪讼。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)钧椰，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。堆排序可以說是一種利用堆的概念來排序的選擇排序符欠。分為兩種方法：

大頂堆：每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值嫡霞，在堆排序算法中用于升序排列；
小頂堆：每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值希柿，在堆排序算法中用于降序排列诊沪；
堆排序的平均時(shí)間復(fù)雜度為 Ο(nlogn)。

算法步驟：

<1>.將初始待排序關(guān)鍵字序列(R1,R2....Rn)構(gòu)建成大頂堆曾撤，此堆為初始的無序區(qū)端姚；
<2>.將堆頂元素R[1]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無序區(qū)(R1,R2,......Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2...n-1]<=R[n]挤悉；
<3>.由于交換后新的堆頂R[1]可能違反堆的性質(zhì)渐裸，因此需要對當(dāng)前無序區(qū)(R1,R2,......Rn-1)調(diào)整為新堆，然后再次將R[1]與無序區(qū)最后一個(gè)元素交換装悲，得到新的無序區(qū)(R1,R2....Rn-2)和新的有序區(qū)(Rn-1,Rn)昏鹃。不斷重復(fù)此過程直到有序區(qū)的元素個(gè)數(shù)為n-1，則整個(gè)排序過程完成诀诊。

/*方法說明：堆排序
@param  array 待排序數(shù)組*/
function heapSort(array) {
    console.time('堆排序耗時(shí)');
    if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
        //建堆
        var heapSize = array.length, temp;
        for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
            heapify(array, i, heapSize);
        }

        //堆排序
        for (var j = heapSize - 1; j >= 1; j--) {
            temp = array[0];
            array[0] = array[j];
            array[j] = temp;
            heapify(array, 0, --heapSize);
        }
        console.timeEnd('堆排序耗時(shí)');
        return array;
    } else {
        return 'array is not an Array!';
    }
}
/*方法說明：維護(hù)堆的性質(zhì)
@param  arr 數(shù)組
@param  x   數(shù)組下標(biāo)
@param  len 堆大小*/
function heapify(arr, x, len) {
    if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array' && typeof x === 'number') {
        var l = 2 * x + 1, r = 2 * x + 2, largest = x, temp;
        if (l < len && arr[l] > arr[largest]) {
            largest = l;
        }
        if (r < len && arr[r] > arr[largest]) {
            largest = r;
        }
        if (largest != x) {
            temp = arr[x];
            arr[x] = arr[largest];
            arr[largest] = temp;
            heapify(arr, largest, len);
        }
    } else {
        return 'arr is not an Array or x is not a number!';
    }
}
var arr=[91,60,96,13,35,65,46,65,10,30,20,31,77,81,22];
console.log(heapSort(arr));//[10, 13, 20, 22, 30, 31, 35, 46, 60, 65, 65, 77, 81, 91, 96]

八：計(jì)數(shù)排序

計(jì)數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開辟的數(shù)組空間中洞渤。作為一種線性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)畏梆。

算法步驟：

<1>. 找出待排序的數(shù)組中最大和最小的元素您宪；
<2>. 統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)奈懒，存入數(shù)組C的第i項(xiàng)奠涌；
<3>. 對所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加）磷杏；
<4>. 反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)溜畅，每放一個(gè)元素就將C(i)減去

function countingSort(arr, maxValue) {
    var bucket = new Array(maxValue+1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1;

    for (var i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }

    for (var j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }

    return arr;
}

九：桶排序

桶排序是計(jì)數(shù)排序的升級版。它利用了函數(shù)的映射關(guān)系极祸，高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定慈格。為了使桶排序更加高效，我們需要做到這兩點(diǎn)：

在額外空間充足的情況下遥金，盡量增大桶的數(shù)量
使用的映射函數(shù)能夠?qū)⑤斎氲?N 個(gè)數(shù)據(jù)均勻的分配到 K 個(gè)桶中
算法步驟：

<1>.設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶浴捆；
<2>.遍歷輸入數(shù)據(jù)，并且把數(shù)據(jù)一個(gè)一個(gè)放到對應(yīng)的桶里去稿械；
<3>.對每個(gè)不是空的桶進(jìn)行排序选泻；
<4>.從不是空的桶里把排好序的數(shù)據(jù)拼接起來。

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }

    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];                // 輸入數(shù)據(jù)的最小值
      } else if (arr[i] > maxValue) {
          maxValue = arr[i];                // 輸入數(shù)據(jù)的最大值
      }
    }

    //桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;            // 設(shè)置桶的默認(rèn)數(shù)量為5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;   
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }

    //利用映射函數(shù)將數(shù)據(jù)分配到各個(gè)桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }

    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                      // 對每個(gè)桶進(jìn)行排序，這里使用了插入排序
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                      
        }
    }

    return arr;
}

十：基數(shù)排序

基數(shù)排序是按照低位先排序页眯，然后收集梯捕；再按照高位排序，然后再收集窝撵；依次類推傀顾，直到最高位。有時(shí)候有些屬性是有優(yōu)先級順序的碌奉，先按低優(yōu)先級排序短曾，再按高優(yōu)先級排序。最后的次序就是高優(yōu)先級高的在前赐劣，高優(yōu)先級相同的低優(yōu)先級高的在前错英。基數(shù)排序基于分別排序隆豹，分別收集椭岩，所以是穩(wěn)定的。
算法步驟：
<1>.取得數(shù)組中的最大數(shù)璃赡，并取得位數(shù)判哥；
<2>.arr為原始數(shù)組，從最低位開始取每個(gè)位組成radix數(shù)組碉考；
<3>.對radix進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）

var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) != null) {
                      arr[pos++] = value;
                }
          }
        }
    }
    return arr;
}