冒泡排序

我們先來(lái)了解一下冒泡排序算法砌们，它是最慢的排序算法之一，但也是一種最容易實(shí)現(xiàn)的排
序算法瘟判。
之所以叫冒泡排序是因?yàn)槭褂眠@種排序算法排序時(shí)怨绣，數(shù)據(jù)值會(huì)像氣泡一樣從數(shù)組的一端漂浮到另一端。假設(shè)正在將一組數(shù)字按照升序排列拷获，較大的值會(huì)浮動(dòng)到數(shù)組的右側(cè)篮撑，而較小的值則會(huì)浮動(dòng)到數(shù)組的左側(cè)。之所以會(huì)產(chǎn)生這種現(xiàn)象是因?yàn)樗惴〞?huì)多次在數(shù)組中移動(dòng)匆瓜，比較相鄰的數(shù)據(jù)赢笨，當(dāng)左側(cè)值大于右側(cè)值時(shí)將它們進(jìn)行互換未蝌。

代碼實(shí)現(xiàn)

function swap(i,j,array){
  let temp = array[j];
  array[j] = array[i];
  array[i] = temp;
}

function bubbleSort(data) {
  let length = data.length, isSwap;
  for (var i = 0; i < length; i++) {            //正序
    isSwap = false;
    for (var j = 0; j < length - 1 - i; j++) {     //正序
      array[j] > array[j+1] && (isSwap = true) && swap(j,j+1,array);
    }
    if(!isSwap)
      break;
  }
  return data;
}

選擇排序

我們接下來(lái)要看的是選擇排序算法。選擇排序從數(shù)組的開(kāi)頭開(kāi)始茧妒，將第一個(gè)元素和其他元素進(jìn)行比較萧吠。檢查完所有元素后，最小的元素會(huì)被放到數(shù)組的第一個(gè)位置桐筏，然后算法會(huì)從第二個(gè)位置繼續(xù)纸型。這個(gè)過(guò)程一直進(jìn)行，當(dāng)進(jìn)行到數(shù)組的倒數(shù)第二個(gè)位置時(shí)梅忌，所有的數(shù)據(jù)便完成了排序狰腌。
選擇排序會(huì)用到嵌套循環(huán)。外循環(huán)從數(shù)組的第一個(gè)元素移動(dòng)到倒數(shù)第二個(gè)元素牧氮；內(nèi)循環(huán)從第二個(gè)數(shù)組元素移動(dòng)到最后一個(gè)元素琼腔，查找比當(dāng)前外循環(huán)所指向的元素小的元素。每次內(nèi)循環(huán)迭代后踱葛，數(shù)組中最小的值都會(huì)被賦值到合適的位置

代碼實(shí)現(xiàn)

function selectSort(data) {
    let length = data.length;
    let min = 0;
    for(let i = 0; i < length; i++){
        min = i;
        for(let j = i +1; j < length; j++){
            if(data[min] > data[j]){
                swap(min,j,data)
            }
        }
    }
  return data
}

插入排序

插入排序類似于人類按數(shù)字或字母順序?qū)?shù)據(jù)進(jìn)行排序丹莲。例如，讓班里的每個(gè)學(xué)生上交一張寫有他的名字尸诽、學(xué)生證號(hào)以及個(gè)人簡(jiǎn)介的索引卡片甥材。學(xué)生交上來(lái)的卡片是沒(méi)有順序的，但是我想讓這些卡片按字母順序排好逊谋，這樣就可以很容易地與班級(jí)花名冊(cè)進(jìn)行對(duì)照了擂达。我將卡片帶回辦公室，清理好書(shū)桌胶滋，然后拿起第一張卡片”螅卡片上的姓氏是 Smith 究恤。我把它放到桌子的左上角，然后再拿起第二張卡片后德。這張卡片上的姓氏是 Brown 部宿。我把 Smith移右，把 Brown 放到 Smith 的前面瓢湃。下一張卡片是 Williams 理张，可把它放到桌面最右邊，而不用移動(dòng)其他任何卡片绵患。下一張卡片是 Acklin 雾叭。這張卡片必須放在這些卡片的最前面，因此其他所有卡片必須向右移動(dòng)一個(gè)位置來(lái)為 Acklin 這張卡片騰出位置落蝙。這就是插入排序的排序原理织狐。

代碼實(shí)現(xiàn)

function insertSort(data) {
    let length = data.length;
    let index,current;
    for(let i = 0; i<length; i++){
        index = i;
        current = data[i];
        while(index>=0 && (data[index+1] < data[index])){
            swap(index, index+1, data);
            index--;
        }
    }
  return data
}

希爾排序

希爾排序是以它的創(chuàng)造者（Donald Shell）命名的暂幼。這個(gè)算法在插入排序的基礎(chǔ)上做了很大的改善。希爾排序的核心理念與插入排序不同移迫，它會(huì)首先比較距離較遠(yuǎn)的元素旺嬉，而非相鄰的元素。和簡(jiǎn)單地比較相鄰元素相比厨埋，使用這種方案可以使離正確位置很遠(yuǎn)的元素更快地回到合適的位置邪媳。當(dāng)開(kāi)始用這個(gè)算法遍歷數(shù)據(jù)集時(shí)，所有元素之間的距離會(huì)不斷減小荡陷，直到處理到數(shù)據(jù)集的末尾雨效，時(shí)算法比較的就是相鄰元素了。
希爾排序的工作原理是亲善，通過(guò)定義一個(gè)間隔序列來(lái)表示在排序過(guò)程中進(jìn)行比較的元素之間有多遠(yuǎn)的間隔设易。我們可以動(dòng)態(tài)定義間隔序列，不過(guò)對(duì)于大部分的實(shí)際應(yīng)用場(chǎng)景蛹头，算法要用到的間隔序列可以提前定義好顿肺。有一些公開(kāi)定義的間隔序列，使用它們會(huì)得到不同的結(jié)果渣蜗。在這里我們用到了 Marcin Ciura 在他 2001 年發(fā)表的論文“Best Increments for theAverage Case of Shell Sort”（http:bit.ly/1b04YFv,2001）中定義的間隔序列屠尊。這個(gè)間隔序列是： 701, 301, 132, 57, 23, 10, 4, 1 。

代碼實(shí)現(xiàn)

function shellsort(data) {
    let gap = Math.floor(data.length/2);
    while(gap>=1){
        for(let i = gap; i<data.length; i++){
            if(data[i]<data[i-gap]){
                swap(i-gap, i, data);
                shellTime += 1;
            }
        }
        gap = gap/2;
    }
  return data
}

歸并排序

歸并排序的命名來(lái)自它的實(shí)現(xiàn)原理：把一系列排好序的子序列合并成一個(gè)大的完整有序序列耕拷。從理論上講讼昆，這個(gè)算法很容易實(shí)現(xiàn)。我們需要兩個(gè)排好序的子數(shù)組骚烧，然后通過(guò)比較數(shù)據(jù)大小浸赫，先從最小的數(shù)據(jù)開(kāi)始插入，最后合并得到第三個(gè)數(shù)組赃绊。然而既峡，在實(shí)際情況中，歸并排序還有一些問(wèn)題碧查，當(dāng)我們用這個(gè)算法對(duì)一個(gè)很大的數(shù)據(jù)集進(jìn)行排序時(shí)运敢，我們需要相當(dāng)大的空間來(lái)合并存儲(chǔ)兩個(gè)子數(shù)組。就現(xiàn)在來(lái)講忠售，內(nèi)存不那么昂貴传惠，空間不是問(wèn)題，因此值得我們?nèi)?shí)現(xiàn)一下歸并排序稻扬，比較它和其他排序算法的執(zhí)行效率卦方。

代碼實(shí)現(xiàn)

function mergeSort(data) {
    if(data.length < 2){
        return data
    }else{
        let mid = Math.floor(data.length/2);
        let left = data.slice(0, mid);
        let right = data.slice(mid);
        return merge(mergeSort(left), mergeSort(right));
    }
}
function merge(left, right) {
    let arr = [];
    while(left.length > 0 && right.length > 0){
        if(left[0] > right[0]) {
            arr.push(right.shift())
        }else{
            arr.push(left.shift())
        }
    }
    return arr.concat(left, right);
}

快速排序

快速排序是處理大數(shù)據(jù)集最快的排序算法之一。它是一種分而治之的算法腐螟，通過(guò)遞歸的方式將數(shù)據(jù)依次分解為包含較小元素和較大元素的不同子序列愿汰。該算法不斷重復(fù)這個(gè)步驟直到所有數(shù)據(jù)都是有序的困后。
這個(gè)算法首先要在列表中選擇一個(gè)元素作為基準(zhǔn)值（pivot）。數(shù)據(jù)排序圍繞基準(zhǔn)值進(jìn)行衬廷，將列表中小于基準(zhǔn)值的元素移到數(shù)組的底部摇予，將大于基準(zhǔn)值的元素移到數(shù)組的頂部。

代碼實(shí)現(xiàn)

function quickSort(data) {
    if(data.length === 0){
        return []
    }
    let lesser = [];
    let greater = [];
    let pivot = data[0];
    for(let i = 1; i<data.length; i++){
        if(data[i] < pivot){
            lesser.push(data[i]);
        }else{
            greater.push(data[i]);
        }
    }
    return quickSort(lesser).concat(pivot,quickSort(greater))
}