上一次說完了冒泡排序，那么繼續(xù)往下走，本次我們來理解選擇排序算法

廢話少說，進入正題

如有誤，辛苦指正

背景介紹

（Selection sort）是一種簡單直觀的排序算法。它的工作原理是：

第一次從待排序的數(shù)據(jù)元素中的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中，然后放到已排序的序列的末尾。以此類推，。選擇排序是不穩(wěn)定的排序方法。

——選擇排序算法

核心特點

1. 循環(huán)遍歷隊列，先找出發(fā)第一次遍歷整個數(shù)組后最小/最大的值
2. 如果有更小/大的值。
3. 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

舉個例子

[ 1, 5, 4, 3, 6, 2, 7 ]

1、先將 1 和 后面的所有數(shù)字進行比較，得到1是最小的，將最小的放到數(shù)組第一個的位置，此時的數(shù)組呈現(xiàn)為（暫無變化）

[ 1, 5, 4, 3, 6, 2, 7 ]

2、緊接著開始用5來和后面的所有進行比較，因為1已經(jīng)是最小了 所以每次只需要從當(dāng)前數(shù)的后面開始比較即可，一個一個比較結(jié)束后發(fā)現(xiàn)2是最小的，那么將2和數(shù)組的第二個元素交換，此時數(shù)組前兩位已經(jīng)是 按照升序排序后的最終位置。

[ 1, 2, 4, 3, 6, 5, 7 ]

3、繼續(xù)重復(fù)步驟二，直到最后兩個元素比較完畢之后，最終的得到排序后的數(shù)組

[ 1, 2, 3, 4, 5, 6, 7 ]

...
此時，我們已經(jīng)通過每次循環(huán)“選擇”一個最小的數(shù)從數(shù)組的開頭依次排放，直到最后兩個元素比較完畢。

以上就是選擇排序的大概算法流程，老規(guī)矩，不上代碼的都是流氓

代碼示例

1、我們創(chuàng)建一個排序方法，并接受一個參數(shù)，就是我們需要排序的數(shù)組

function selectionSort( _array ){
    
}

2、創(chuàng)建完畢后我們先來做第一步，聲明兩個變量，用來存放當(dāng)前最小值的下標(biāo)以及交換位置時使用的臨時變量

function selectionSort( _array ){
    //minIndex用來存放當(dāng)前最小值在數(shù)組中的下標(biāo)
    var minIndex = 0;
    //用來作為交換位置的臨時變量
    var _cache;
}

3、接著我們就要開始準(zhǔn)備循環(huán)了，用第一個元素依次和后面的元素相比較，得到最小的一個值

function selectionSort( _array ){
    //minIndex用來存放當(dāng)前最小值在數(shù)組中的下標(biāo)
    var minIndex = 0;
    //用來作為交換位置的臨時變量
    var _cache;
    //因為minIndex的下標(biāo)已經(jīng)是0了，所以從1開始比較即可
    for( let j = 1; j < _array.length; j++ ){
        //如果后面比較的數(shù)比當(dāng)前更小，那么將minIndex的值指向這個新的數(shù)的下標(biāo)
        if( _array[minIndex] > _array[j] ) {
                minIndex = j;
        }
    }
    //此時循環(huán)完畢后當(dāng)前的minIndex的值就是最小數(shù)的下標(biāo)
    //_array[minIndex]的值就是最小的數(shù)
    //然后我們將這個值和我們初始下標(biāo)0的元素 交換一下值
    _cache = _array[0];
    _array[0] = _array[minIndex];
    _array[minIndex] = _cache;
}

4、至此我們完成了第一輪循環(huán)，實現(xiàn)了找到第一個最小的數(shù)，并將它存放到數(shù)組開頭的位置，剩下的操作就是不斷地重復(fù)執(zhí)行此步驟，直到數(shù)組排序完畢。
既然重復(fù)此步驟，那么新增的循環(huán)必然是在當(dāng)前代碼塊的最外層

function selectionSort( _array ){
    //minIndex用來存放當(dāng)前最小值在數(shù)組中的下標(biāo)
    var minIndex;
    //用來作為交換位置的臨時變量
    var _cache;

    //我們開始循環(huán)，正好從零開始，我們就把minIndex每次的初始值設(shè)置為i的值
    //同時我們只要循環(huán)到最后一個元素前面一個元素即可，因為內(nèi)部循環(huán)會把當(dāng)前的和最后的作比較
    for( let i = 0; i < _array.length - 1; i++ ){
        minIndex = i;
        //這里因為每次是從當(dāng)前值的后面開始,所以J的開始要改為i+1
        for( let j = i + 1; j < _array.length; j++ ){
            //如果后面比較的數(shù)比當(dāng)前更小，那么將minIndex的值指向這個新的數(shù)的下標(biāo)
            if( _array[minIndex] > _array[j] ) {
                    minIndex = j;
            }
        }

        //當(dāng)內(nèi)部循環(huán)完畢后 此時已經(jīng)得到了每一次循環(huán)下的最小值，這里進行交換
        //此時循環(huán)完畢后當(dāng)前的minIndex的值就是最小數(shù)的下標(biāo)

        //這里可以加個判斷，如果相等，那說明當(dāng)前數(shù)就是最小的數(shù)，所以沒必要再去交換了
        if( i !== minIndex ){
            _cache = _array[i];
            _array[i] = _array[minIndex];
            _array[minIndex] = _cache;
        }

    }

    //至此所有循環(huán)結(jié)束后 當(dāng)前的_array就已經(jīng)是排序過后的數(shù)組了
    return _array;
}

至此我們就完成了選擇排序的思路實現(xiàn)。

同上篇，排序方式帶來的性能問題，及優(yōu)化方案我們會在系列完結(jié)之后在視情況重新梳理，本次旨在便于大家理解。