前言

作為前端開發(fā)者而言，算法雖然是一種只需要涉獵的領(lǐng)域，但它對(duì)于我而言，確是一道不得不踏過(guò)的檻。原因有倆，其一，前端在遇到復(fù)雜的邏輯問(wèn)題時(shí)可以有更好地去理解與分析；其二，個(gè)人的競(jìng)爭(zhēng)力也會(huì)比較突出（大廠面經(jīng)必備）

友情提示 5道基礎(chǔ)算法題，閱讀時(shí)間為5-10分鐘
下面來(lái)看下有哪些排序算法

冒泡排序

主要思路：比較相鄰兩個(gè)項(xiàng)，如果第一個(gè)比第二個(gè)大，就交換位置。

var bubbleSort = function (array) {
    var len = array.length;
    //循環(huán)length不減一，用于獲取數(shù)組循環(huán)輪數(shù)，以便于相鄰數(shù)值的比較
    for(var i =0; i < len; i++){
        for(var j =0; j < len - 1; j++){
           if(array[j] > array[j+1]){
               var firstVal = array[j];
               array[j] = array[j+1];
               array[j+1] = firstVal; 
           }
        }
    }
}

選擇排序

選擇排序，也稱為原址比較算法。主要思路是，找到數(shù)據(jù)結(jié)構(gòu)中的最小值并將其放置在第一位，接著找到第二小值放到第二位。以此類推。

var selectionSort = function (array) {
    var indexMin;
    for (var i = 0; i < array.length-1; i++) {
        indexMin = i;

        //循環(huán)length不減一，用于獲取數(shù)組最后一個(gè)元素與前一個(gè)元素進(jìn)行比較
        for (var j = i; j < array.length; j++) {
            if (array[indexMin] > array[j]) {
                indexMin = j;
            }
        }
        if (i !== indexMin) {
            var ux = array[i];
            array[i] = array[indexMin];
            array[indexMin] = ux;
        }
    }
}

插入排序

插入排序，相較前兩種算法性能是有所提高，思路是將第一項(xiàng)與第二項(xiàng)比較，得出正確排序；接著與第三項(xiàng)比較，得出1，2，3項(xiàng)的正確排序，以此類推

var insertionSort = function (array) {
    for (var i = 0; i < array.length; i++) {
        var j = i;
        var temp = array[i];
        while(j > 0 && array[j-1] > temp) {
            array[j] = array[j-1];
            j--;
        }
        array[j] = temp;
    }
}

歸并排序

歸并排序,是一個(gè)比較優(yōu)化的算法,思路是將其遞歸分解數(shù)列,再合并數(shù)列

var mergeSort = function (array) {
    var len = array.length;
    if (len <= 1) {
        return array;
    }
    var mid = Math.floor(len / 2);
    var left = array.slice(0, mid);
    var right = array.slice(mid, len);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    var i = 0, j = 0, result = [];
    while(i < left.length && j < right.length) {
        if (left[i] > right[j]) {
            result.push(right[j++]);
        } else {
            result.push(left[i++]);
        }
    }
    while (i < left.length) {
        result.push(left[i++]);
    }
    while (j < left.length) {
        result.push(left[j++]);
    }

    return result;
}

快速排序

快速排序，常用的一種排序方法。主要思路是取一個(gè)基準(zhǔn)點(diǎn)，以基準(zhǔn)點(diǎn)為中心，分割成小于基準(zhǔn)點(diǎn)或者大于基準(zhǔn)點(diǎn)的兩個(gè)數(shù)組，按順序遞歸排列

var quickSort = function (array) {
    if (array.length <= 1) {
        return array;
    }
    var mid = Math.floor(array.length / 2);
    var temp = array.splice(mid, 1)[0];
    var left = [];
    var right = [];

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

    return quickSort(left).concat(temp, quickSort(right));
}

思考

這幾種算法有哪些優(yōu)缺點(diǎn)？
首先，選擇排序跟冒泡排序是比較簡(jiǎn)單的算法，然而這兩種排序算法在運(yùn)行性能上都是比較差的。只考慮用于學(xué)習(xí)；
其次，插入排序跟前兩者一樣，都是通過(guò)比較來(lái)進(jìn)行排序，在小型數(shù)組方面性能相對(duì)較好，但還是不支持用于實(shí)戰(zhàn)；
對(duì)于歸并排序與快速排序而言，兩者的相同點(diǎn)在于采用分治的思想，只不過(guò)快排沒(méi)有將數(shù)組切割。而在實(shí)用性方面，歸并與快排都是能進(jìn)行實(shí)用的算法，但快排應(yīng)該是最常用的一種。
其他排序算法呢？
其實(shí)排序算法還有堆排序、希爾排序、計(jì)數(shù)排序、桶排序、基數(shù)排序等，只不過(guò)對(duì)這幾種掌握不深，不敢班門弄斧。后面對(duì)算法更熟悉些，會(huì)進(jìn)行這幾種算法的學(xué)習(xí)并且與前幾種算法的優(yōu)勢(shì)比較