摘要：前言排序是計(jì)算機(jī)中對(duì)存儲(chǔ)的數(shù)據(jù)執(zhí)行最常見的操作之一。在排序算法中繞不開的是循環(huán)，只有在深入學(xué)習(xí)排序算法時(shí)，才發(fā)現(xiàn)平時(shí)不起眼的循環(huán)語(yǔ)句不可小覷。在排序算法中，還有一點(diǎn)需要注意的，那就是數(shù)組。

排序是計(jì)算機(jī)中對(duì)存儲(chǔ)的數(shù)據(jù)執(zhí)行最常見的操作之一。語(yǔ)法簡(jiǎn)單，卻很精妙。在排序算法中繞不開的是循環(huán)，只有在深入學(xué)習(xí)排序算法時(shí)，才發(fā)現(xiàn)平時(shí)不起眼的循環(huán)語(yǔ)句不可小覷。

拿最簡(jiǎn)單的冒泡排序來(lái)說(shuō)，道理我都懂，可為什么會(huì)想到兩層嵌套的循環(huán)語(yǔ)句？為什么兩層循環(huán)語(yǔ)句的條件會(huì)有所不同？?jī)蓪友h(huán)的關(guān)聯(lián)邏輯是什么？循環(huán)在冒泡中扮演著什么角色？循環(huán)是通過(guò)怎樣的邏輯完成冒泡的？等等。這些問(wèn)題的背后，都值得我們?nèi)ヌ骄俊?/p> 循環(huán)

在說(shuō)正題之前，需要說(shuō)一個(gè)小插曲。由于互聯(lián)網(wǎng)寒冬，程序員們都有一種危機(jī)感。在這場(chǎng)危機(jī)中，程序員的篩選條件也變得更加苛刻。無(wú)論是前端還是后端，都最好能夠熟悉掌握一些基礎(chǔ)算法。所以說(shuō)，刷算法題，也在程序員間流行起來(lái)了。我旁邊的一同事，就刷到了一個(gè)有趣的算法，說(shuō)是挺有意思的，就讓我也嘗試一下。講真，作為一個(gè)前端，除了簡(jiǎn)單處理一下接口數(shù)據(jù)，還真沒有訓(xùn)練過(guò)應(yīng)試般的算法。

題目大致是這樣的，在 n*n 的平面中，以一半的空間螺旋有序排滿以1起始若干數(shù)字。
畫圖如下：

隨著思考的深入，突然發(fā)現(xiàn)，這tm不就是一道數(shù)學(xué)題么？（原諒我說(shuō)粗話了）
找出已知，列出未知，關(guān)聯(lián)已知未知，就差列 x、y 了。

以下以 5*5 為例：

var arr = Array.from({length: 5}).map(item => ([]));
var i = 1;
function Sort(init, length){
    let m = init, n= init;
    while(m < length){
        arr[m++][init] = i++;
    }
    --m;
    while(n < length -1) {
        arr[--m][++n] = i++;
    }
    --n;
    while(n > init) {
        arr[m][n--] = i++;
    }
    if (length <= 3) return arr;
    Sort(n+1, length - 2);
}

console.log(Sort(0, 5), arr)

變動(dòng)的就是未知，找出循環(huán)條件，關(guān)聯(lián)已知，這樣等式就算列出來(lái)了。在這里我把平面想像成平面坐標(biāo)，m、n 當(dāng)作 x、y 軸，數(shù)組就是坐標(biāo)點(diǎn)的集合，數(shù)字螺旋折轉(zhuǎn)的條件作為循環(huán)遞歸條件，就這樣，一個(gè)粗糙的算法算是完成了。

雖然這和本次主題的關(guān)系不是很大，但是很受啟發(fā)，讓我覺得程序和數(shù)學(xué)果然存在著緊密的關(guān)系。回到這一小節(jié)，以最簡(jiǎn)單的 for 循環(huán)為例。

let arr = [1, 2, 3];
for(let i = 0;i < arr.length; i++){}

以上就是最簡(jiǎn)單的 for 循環(huán)寫法，從這個(gè)簡(jiǎn)單的 for 語(yǔ)句，我們能夠知道的是，第幾次循環(huán)i（即當(dāng)前），循環(huán)的次數(shù)arr.length及循環(huán)的驅(qū)動(dòng)i++。很重要的一點(diǎn)就是，i 是隨著循環(huán)遞增的。循環(huán)就是這么簡(jiǎn)單，也沒有什么其他魔力。

在排序算法中，還有一點(diǎn)需要注意的，那就是數(shù)組。在 JavaScript 中，數(shù)組元素在內(nèi)存中并不是連續(xù)的。我們可以通過(guò)索引來(lái)引用相應(yīng)位置的元素。更重要的是，我們通常操作數(shù)組元素的時(shí)候，并不是操作數(shù)組元素本身，而是該位置上的變量。我們可以想象成，每一個(gè)索引位置都是一個(gè)變量，然后通過(guò)給變量賦值數(shù)組元素。

循環(huán)和數(shù)組，如果多帶帶使用倒也沒什么。如果兩者結(jié)合，你就會(huì)發(fā)現(xiàn)，隨著循環(huán)的次數(shù)增加，數(shù)組索引也會(huì)遞增，再結(jié)合一些邏輯，就可以把某些元素移動(dòng)到制定的位置。

那么，都結(jié)合怎樣的邏輯呢？

冒泡排序邏輯，通過(guò)兩兩比較，把較大的元素賦值給當(dāng)前位置索引的后一索引位置，然后隨著循環(huán)增加，當(dāng)前索引也會(huì)遞增，最終會(huì)把最大值推到末尾。然后把這個(gè)過(guò)程循環(huán)多次，最終把倒數(shù)第二大、倒數(shù)第三大...移到指定位置。

function bubbleSort(arr){
    let len = arr.length;
    for(let i = 0; i < len - 1; i++){
        for(let j = 0; j < len - 1 - i; j++){    // 遞增更換當(dāng)前元素；
            if (arr[j] > arr[j+1]){    // 相鄰元素比較；
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];    // 位置互換；
            }
        }
    }
    return arr;
}

選擇排序邏輯，比較當(dāng)前數(shù)組元素，找出最小元素的索引，將該位置的元素移動(dòng)指定位置。然后多次循環(huán)遍歷，最終將剩下數(shù)組元素中第二小元素、第三小元素...移到指定位置。

function selectionSort(arr){
    let len = arr.length;
    for(let i = 0; i < len - 1; i++){
        let minIndex = i;
        for(let j = i + 1; j < len; j ++){    // 遞增替換當(dāng)前元素；
            if(arr[j] < arr[minIndex]){
                minIndex = j;    // 更新最小元素索引；
            }
        }
        [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];    // 與最小元素互換位置；
    }
    return arr;
}

插入排序邏輯，將當(dāng)前的數(shù)組元素與之前的數(shù)組元素比較，并將其插入到適當(dāng)位置。

function insertionSort(arr){
    let len = arr.length;
    for(let i = 1; i < len; i++){
        let temp = arr[i];
        let preIndex = i -1;
        while(preIndex >= 0 && arr[preIndex] > temp){
            arr[preIndex + 1] = arr[preIndex--];    // 該位置元素若小于當(dāng)前元素，則將其后移動(dòng)；
        }
        arr[preIndex+1] = temp;
    }
    return arr;
}

希爾排序算是插入排序的升級(jí)版本，插入排序是與之前的數(shù)組元素挨個(gè)進(jìn)行比較，而希爾排序是以特定間隔進(jìn)行多次分組比較，所以說(shuō)在代碼上很相似。

function shellSort(gap, arr){
    let len = arr.length;
    for(let i = 0; i < gap.length; i++){    // 以不同間隔分組比較；
        for(let j = gap[i]; j < len; j++){    // 以間隔的下一索引位置起始；
            let temp = arr[j];
            let preGapIndex = j - gap[i];
            while(preGapIndex >= 0 && arr[preGapIndex] > temp){    // 當(dāng)前元素與之前固定間隔索引位置元素進(jìn)行比較；
                arr[preGapIndex + gap[i]] = arr[preGapIndex];
                preGapIndex = preGapIndex - gap[i];
            }
            arr[preGapIndex + gap[i]] = temp;
        }
    }
    return arr;
}

歸并排序邏輯，使用遞歸的方式將數(shù)組劃分為更小的數(shù)組對(duì)，通過(guò)比較重新合成完整的數(shù)組。本文采用的是自頂向下的歸并排序，還可以使用自底向上的歸并排序。

function mergeSort(arr){
    let len = arr.length;
    if(len < 2) return arr;
    let middle = Math.floor(len/2);    // 分組；
    let left = arr.slice(0, middle);
    let right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right){
    let len = left.length + right.length;
    let result = [], m = 0, n = 0;
    left[left.length] = Infinity;
    right[right.length] = Infinity;
    for(let i = 0; i < len; i++){    // 循環(huán)的次數(shù)為新數(shù)組的長(zhǎng)度；
        if(left[m] <= right[n]){    // 比較左右數(shù)組元素重新排列組合成新的數(shù)組；
            result[i] = left[m];
            m++;
        }else{
            result[i] = right[n];
            n++;
        }
    }
    return result;
}

快速排序邏輯，從數(shù)組中選出基準(zhǔn)值，將大于基準(zhǔn)值的元素移到右側(cè)數(shù)組，將小于基準(zhǔn)值的元素移到左側(cè)數(shù)組，遞歸循環(huán)此操作直到數(shù)組為空。然后合并各組數(shù)組，最終得到排序后的新數(shù)組。

function quickSort(arr){
    if(arr.length < 1) return arr;
    let len = arr.length;
    let pivot = arr[0];    // 設(shè)置基準(zhǔn)值；
    let lesser = [], greater = [];
    for(let i = 1; i < len; i++){
        if(arr[i] < pivot){
            lesser.push(arr[i]);    // 將小于基準(zhǔn)值推至左側(cè)；
        } else {
            greater.push(arr[i]);    // 將大于基準(zhǔn)值推至右側(cè)；
        }
    }
    return quickSort(lesser).concat(pivot, quickSort(greater));
}

over！