什么是算法

高德納在《計算機(jī)程序設(shè)計藝術(shù)》里對算法的歸納：
書籍推薦：《數(shù)據(jù)結(jié)構(gòu)與算法分析》

1. 輸入：一個算法必須有零個或以上輸入量
2. 輸出：一個算法應(yīng)有一個或以上的輸出量
3. 明確性：算法的描述必須無歧義，實(shí)際運(yùn)行結(jié)果是確定的
4. 有限性：必須在有限個步驟內(nèi)結(jié)束
5. 有效性：又稱可行性。能過被執(zhí)行者實(shí)現(xiàn)

排序算法可視化網(wǎng)站推薦： https://visualgo.net/zh/sorting

問題

數(shù)組 array 含有 N 個正整數(shù),
輸入量為 array,
請將 array 中的數(shù)字從小到大排列，
輸出量為排好序的數(shù)組。

例如

var array = [5, 2, 4, 6, 8]
function sort(){
   // body
}
sort(array)  == [2, 4, 5, 6, 8]

冒泡排序(Bubble Sort)

第一個數(shù)字開始，每一個數(shù)字與自身相鄰的后一位數(shù)字比較，如果后一位數(shù)字較小，則互換位置，否則不換，第一次所有數(shù)字都比較完畢后（比較 n-1 次即可完成），最后一位數(shù)字是最大的，依此類推（第二次比較 n-2 次），直到完成排序（最后剩余2個數(shù)字比較1次即可）

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
排序步驟如下：
第i 9 次 5,2,6,8,3,1,4,0,7,9  // 第一輪比較結(jié)束后，較大的互換位置，9最大，在最后面，比較次數(shù)8次
第i 8 次 2,5,6,3,1,4,0,7,8,9  // 第二輪比較結(jié)束后8最大，較大的互換位置，在最后面，比較次數(shù)7次，依次類推
第i 7 次 2,5,3,1,4,0,6,7,8,9
第i 6 次 2,3,1,4,0,5,6,7,8,9
第i 5 次 2,1,3,0,4,5,6,7,8,9
第i 4 次 1,2,0,3,4,5,6,7,8,9
第i 3 次 1,0,2,3,4,5,6,7,8,9
第i 2 次 0,1,2,3,4,5,6,7,8,9
第i 1 次 0,1,2,3,4,5,6,7,8,9

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
console.log(bubbleSort(arr));

function bubbleSort(array){
    var temp;  // 獲取臨時參數(shù)
    // 最外層比較 i 次
    for(var i = array.length - 1; 0 < i; i--){
        // 確定內(nèi)層循環(huán)邊界
        for(var j = 0; j < i; j++){
            // 如果后一個數(shù)字較小，則調(diào)換位置
            if (array[j] > array[j+1]) {  
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            } 
        console.log('第j ' + i + '  ' + j + ' 次 ' + array)       
        }
    console.log('第i ' + i + ' 次 ' + array)
    }
    return array;
}

選擇排序(Select Sort)

第一個數(shù)字開始（開始時認(rèn)為第一個數(shù)字為最小數(shù)字），第一個數(shù)字與所有的數(shù)字比較，獲得數(shù)組中最小的數(shù)字，最小的數(shù)字與第一個數(shù)字互換位置，則最小的在第一個，然后第二個數(shù)字開始，重復(fù)第一次的流程，直到剩余最后一個數(shù)字，則剩余的數(shù)字為最大的數(shù)字而且出現(xiàn)在末尾，最小的數(shù)字在第一個，排序完成

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
排序步驟如下：
第i 0 次 8,5,2,6,9,3,1,4,0,7  // 第一輪比較結(jié)束后，0最小，與8互換位置
第i 1 次 0,5,2,6,9,3,1,4,8,7  // 第二輪比較結(jié)束后，1最小，與5互換位置
第i 2 次 0,1,2,6,9,3,5,4,8,7
第i 3 次 0,1,2,6,9,3,5,4,8,7
第i 4 次 0,1,2,3,9,6,5,4,8,7
第i 5 次 0,1,2,3,4,6,5,9,8,7
第i 6 次 0,1,2,3,4,5,6,9,8,7
第i 7 次 0,1,2,3,4,5,6,9,8,7
第i 8 次 0,1,2,3,4,5,6,7,8,9

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
console.log(selectSort(arr));

function selectSort(array){
    var temp,
        minIndex,
        minValue;
    for(var i = 0; i < array.length - 1; i++){
        minIndex = i;
        minValue = array[minIndex];
        for(var j = i + 1; j < length; j++){
            // 如果當(dāng)前最小值大于數(shù)組中的數(shù)字，則數(shù)組中的數(shù)字為最小，獲取其下標(biāo)和值
            if(minValue > array[j]){
                minIndex = j;
                minValue = array[minIndex];
            }
            // console.log('第j ' + j + ' 次 ' + array);
        }
        console.log('第i ' + i + ' 次 ' + array);
        // 將最小值和當(dāng)前開始比較多數(shù)字位置互換
        temp = array[i];
        array[i] = minValue;
        array[minIndex] = temp;
    }
    return array;
}    

插入排序(Insertion Sort)

類似于撲克牌摸牌，得到一個數(shù)字，大于此數(shù)字放在右側(cè)，小于此數(shù)字放在左側(cè)，如果左側(cè)或者右側(cè)有多個數(shù)字，則依次進(jìn)行比較，直到找到合適位置，依次類推，以下面示例代碼中數(shù)組為例：

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
排序步驟如下
[ 5, 8, 2, 6, 9, 3, 1, 4, 0, 7 ]  // 第一輪比較結(jié)束后，5和8互換位置
[ 2, 5, 8, 6, 9, 3, 1, 4, 0, 7 ]  // 第二輪比較結(jié)束后，2小于5、8，所以與5、8分別互換位置
[ 2, 5, 6, 8, 9, 3, 1, 4, 0, 7 ]  // 第三輪比較結(jié)束后，6大于5，小于8，所以與8互換位置，依次類推
[ 2, 5, 6, 8, 9, 3, 1, 4, 0, 7 ]
[ 2, 3, 5, 6, 8, 9, 1, 4, 0, 7 ]
[ 1, 2, 3, 5, 6, 8, 9, 4, 0, 7 ]
[ 1, 2, 3, 4, 5, 6, 8, 9, 0, 7 ]
[ 0, 1, 2, 3, 4, 5, 6, 8, 9, 7 ]
[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
console.log(inserterSort(arr));

function inserterSort(array) {
    // 
    var temp;
    for (var i = 1; i < array.length; i++) {
        for (var j = i; j > 0; j--) {
            // 如果前一個比當(dāng)前數(shù)字大，則交換位置
           if (array[j-1] > array[j]) {
            temp = array[j-1];
            array[j-1] = array[j];
            array[j] = temp;
            // 如果前一個比當(dāng)前數(shù)字小，不做變動，退出循環(huán)
           } else {
            break;
           }
        }
    }
    return array
}

歸并排序(Merge Sort)

領(lǐng)導(dǎo)算法，得到一個數(shù)組時，將數(shù)組一分為二（一直分半，直到剩余1個或者2個數(shù)字），對其分別排序，然后再放到一起排序，直到完成，以下面示例代碼中的數(shù)組為例：

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
排序步驟如下
第一次劃分：[8, 5, 2, 6, 9]; [3, 1, 4, 0, 7]
第二次劃分：[8, 5, 2]; [6, 9]; [3, 1,4]; [0, 7]
第三次劃分：[8, 5]; [2]; [6, 9]; [3, 1]; [4]; [0, 7]
第一次排序：[5, 8]; [2]; [6, 9]; [1, 3]; [4]; [0, 7]
第二次排序：[2, 5, 8]; [6, 9]; [1, 3, 4]; [0, 7]
第三次排序：[2, 5, 6, 8, 9]; [0, 1, 3, 4, 7]
第三次排序：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
console.log(mergeSort(arr));

function mergeSort(arr){
    if(arr.length <= 1){
        return arr;
    }
    var pivot = Math.floor(arr.length / 2);  // 每次獲取中間位置為基準(zhǔn)位置
    var left = arr.slice(0, pivot);  // 將原有數(shù)組一分為二
    var right = arr.slice(pivot);

    function merge(left, right){
        var result = [];
        while (left.length > 0 && right.length > 0) {
            // 重復(fù)對比，小的放到數(shù)組前面
            if(left[0] < right[0]){
                result.push(left.shift());
            } else {
                result.push(right.shift());
            }
        }
        console.log('result ' + result);
        // 將結(jié)果合并返回
        return result.concat(left, right);
    }
    console.log(arr);
    // 重復(fù)一分為二
    return merge(mergeSort(left), mergeSort(right));
}

快速排序(Quick Sort)

得到一個數(shù)組，獲取中間位置的數(shù)字作為基準(zhǔn)，比基準(zhǔn)位置數(shù)字小的都到放到其前面，比基準(zhǔn)數(shù)字大的都放到其后面，然后左右兩邊再分別找到基準(zhǔn)位置，分別排序，直到完成。

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
排序步驟如下:
第一次劃分：[2, 1, 0]; [8, 5, 6, 9, 4, 7]
第二次劃分：[0]; [2]; [5, 4]; [8, 9, 7]
第三次劃分：[0]; [2]; [5, 4]; [8, 7]
第一次排序：[0, 1, 2]; [4, 5]; [7, 8, 9]
第二次排序：[0, 1, 2, 3]; [4, 5, 6, 7, 8, 9]
第三次排序：[0, 1, 2, 3，4, 5, 6, 7, 8, 9]
此處寫的較為模糊，以下面代碼為基準(zhǔn)寫的排序步驟，建議參考文章開頭的可視化網(wǎng)站理解

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
console.log(quickSort(arr));

function quickSort(arr){
    if(arr.length <= 1){
        return arr;
    }
    var pivotInedx = Math.floor(arr.length / 2);  // 每次選擇中間位置作為基準(zhǔn)位置
    var pivot = arr.splice(pivotInedx, 1)[0];  // 選擇基準(zhǔn)位置上的數(shù)字
    console.log(pivot);
    var left = [];
    var right = [];
    for (var i = 0; i < arr.length; i++) {
        // 將數(shù)據(jù)一分為二，小于基準(zhǔn)數(shù)字的數(shù)據(jù)放在左邊數(shù)組中，大于或等于放在右邊數(shù)組中
        if(arr[i] < pivot){
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
        console.log(arr)
    }
    // 重復(fù)調(diào)用，并將得到的數(shù)組拼接在一起，完成為止
    return quickSort(left).concat([pivot],quickSort(right));
}

隨機(jī)快速排序(Random Quick Sort)

原理同快速排序，只是基準(zhǔn)位置為數(shù)組中隨機(jī)數(shù)字，某些情況下排序的速度快于快速排序

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
console.log(quickSort(arr));
function quickSort(arr){
    if(arr.length <= 1){
        return arr;
    }
    var pivotInedx = Math.floor(Math.random() * arr.length);  // 隨機(jī)選擇基準(zhǔn)位置
    var pivot = arr.splice(pivotInedx, 1)[0];  // 選擇基準(zhǔn)位置上的數(shù)字
    console.log(pivot);
    var left = [];
    var right = [];
    for (var i = 0; i < arr.length; i++) {
        // 將數(shù)據(jù)一分為二，小于基準(zhǔn)數(shù)字的數(shù)據(jù)放在左邊數(shù)組中，大于或等于放在右邊數(shù)組中
        if(arr[i] < pivot){
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
        console.log(arr)
    }
    // 重復(fù)調(diào)用，并將得到的數(shù)組拼接在一起，完成為止
    return quickSort(left).concat([pivot],quickSort(right));
}