# 前言

很多同學(xué)在前端面試中剩晴，手寫代碼已經(jīng)是家常便飯萤晴。要求寫一些常見的排序算法也是常常遇到互艾，接下來(lái)將把幾種常見的算法用 JavaScript 的方法實(shí)現(xiàn)载碌。

# 快速排序

分治法的思想猜嘱，尋找中間點(diǎn)，并對(duì)其左右的序列遞歸進(jìn)行排序嫁艇，直到左右都排序完成朗伶。

function quickSort(arr){
    if(arr.length == 0) return arr;

    let pirotIndex = Math.floor(arr.length/2),
        pirot = arr.splice(pirotIndex, 1)[0],
        left= [], right = [];

    for(let i = 0; i < arr.length; i++){
        arr[i] > pirot ? right.push(arr[i]) : left.push(arr[i]);
    }

    return quickSort(left).concat(pirot, quickSort(right))
}

# 插入排序

將數(shù)組分為 無(wú)序區(qū) 和 有序區(qū) 兩個(gè)區(qū)，然后不斷 將無(wú)序區(qū) 的第一個(gè)元素按大小順序插入到 有序區(qū) 中去步咪，最終將所有 無(wú)序區(qū) 元素都移動(dòng)到 有序區(qū)完 成排序

function insertionSort(arr) {
    var preIndex, current;
    for (let i = 1; i < arr.length; 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;
}

# 冒泡排序

比較相鄰的元素论皆。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)猾漫。對(duì)每一對(duì)相鄰元素做同樣的工作点晴，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)悯周，最后的元素應(yīng)該會(huì)是最大的數(shù)粒督。

function bubbleSort(arr){
    if(arr.length==0)  return arr
  
    for(let i = 0; i < arr.length; i++){
        for(let j = 0; j < arr.length-1; j++){
            if(arr[j] > arr[j+1]){
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]] //ES6解構(gòu)
            }
        }
    }
    return arr
}

# 選擇排序

第一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素禽翼，存放在序列的起始位置屠橄，然后再?gòu)氖Ｓ嗟奈磁判蛟刂袑ふ业阶钚族跛。ù螅┰兀缓蠓诺揭雅判虻男蛄械哪┪踩袂健Ｒ源祟愅平负澹钡饺看判虻臄?shù)據(jù)元素的個(gè)數(shù)為零。

function selectionSort(arr) {
    if (arr.length == 0) return arr
    let minIndex;
    for (let i = 0; i < arr.length; i++) {
        minIndex = i;
        for (let j = i; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
    }
    return arr
}

# 歸并排序

把數(shù)組分半溪北，不斷遞歸排序桐绒，最后進(jìn)行已排序的數(shù)字進(jìn)行合并。

function mergeSort(arr) {
    if (arr.length < 2) return arr
    let middle = Math.floor(arr.length / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right))
}

function merge(left, right) {
    let 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
}