排序算法

時(shí)間復(fù)雜度

??討論算法時(shí)需先了解時(shí)間復(fù)雜度，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定性描述該算法的運(yùn)行時(shí)間。
??可以參考其對(duì)時(shí)間復(fù)雜度的解釋簡(jiǎn)書
??簡(jiǎn)單來(lái)說(shuō)，就是如果將程序中程序段的運(yùn)行時(shí)間用數(shù)學(xué)表達(dá)式T(n)表示時(shí)，當(dāng)其中循環(huán)次數(shù)n越來(lái)越大，趨近于無(wú)窮時(shí)，則可忽略部分函數(shù)元素，比如只保留最高次項(xiàng)、忽略最高次項(xiàng)的系數(shù)，當(dāng)T(n) 不等于一個(gè)常數(shù)項(xiàng)時(shí)，可直接將常數(shù)項(xiàng)省略。此時(shí)得到的函數(shù)為f(n),因此可得算法的時(shí)間復(fù)雜度為O(f(n))。
??關(guān)于大O符號(hào)，可以查看百度百科：大O符號(hào)。
??值得注意的是：函數(shù)運(yùn)行中，各個(gè)循環(huán)之間如果是嵌套關(guān)系，則O(a x b x c x...),當(dāng)順序執(zhí)行時(shí)，雖是相加，但保留最高次項(xiàng)。時(shí)間復(fù)雜度函數(shù)是不固定，通常取當(dāng)n數(shù)值越大時(shí)，影響函數(shù)最大的因素。

空間復(fù)雜度

??空間復(fù)雜度是定義了該算法在運(yùn)算過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度。一個(gè)算法的優(yōu)劣主要從算法的執(zhí)行時(shí)間和所需要占用的存儲(chǔ)空間兩個(gè)方面衡量。(來(lái)自：百度百科)
??一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間，包括存儲(chǔ)算法本身所占用的存儲(chǔ)空間，算法的輸入輸出數(shù)據(jù)所占用的存儲(chǔ)空間和算法在運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間這三個(gè)方面。算法的輸入輸出數(shù)據(jù)所占用的存儲(chǔ)空間是由要解決的問(wèn)題決定的，是通過(guò)參數(shù)表由調(diào)用函數(shù)傳遞而來(lái)的，它不隨本算法的不同而改變。存儲(chǔ)算法本身所占用的存儲(chǔ)空間與算法書寫的長(zhǎng)短成正比，要壓縮這方面的存儲(chǔ)空間，就必須編寫出較短的算法。算法在運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間隨算法的不同而異，有的算法只需要占用少量的臨時(shí)工作單元，而且不隨問(wèn)題規(guī)模的大小而改變，節(jié)省存儲(chǔ)；而有的算法需要占用的臨時(shí)工作單元數(shù)與解決問(wèn)題的規(guī)模n有關(guān)，它隨著n的增大而增大，當(dāng)n較大時(shí)，將占用較多的存儲(chǔ)單元。(以上來(lái)自：百度百科)

具體排序算法

??穩(wěn)定性是指：假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過(guò)排序，這些記錄的相對(duì)次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。
??【注意】：排序算法的穩(wěn)定性是由具體的算法決定，不穩(wěn)定的算法在某種條件下可以變?yōu)榉€(wěn)定的算法，而穩(wěn)定的算法在某種情況下也可以變?yōu)椴环€(wěn)定的算法。（來(lái)自：百度百科）

冒泡排序

??冒泡排序思想：從第0個(gè)元素到第n-1個(gè)元素遍歷，若前面一個(gè)元素大于后面一個(gè)元素，則交換兩個(gè)元素，這樣可將整個(gè)序列中最大的元素冒泡到最后，然后再?gòu)牡?個(gè)到第n-2遍歷，如此往復(fù)，直到只剩一個(gè)元素。

    function bubbleSort() {
    for (var i = 0; i < arr.length - 1; i++) {
        for (var j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {  //比較相鄰數(shù)值大小，若前面的大于后面的，則互相替換
                var temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}
var arr = [1, 2, 5, 2, 5, 1, 7, 4, 1, 19, 33, 2];
console.log(bubbleSort(arr)); //[1, 1, 1, 2, 2, 2, 4, 5, 5, 7, 19, 33]

??冒泡循環(huán)是穩(wěn)定的，但如果將arr[j] > arr[j + 1]改為arr[j] >= arr[j + 1],則相同的兩個(gè)元素也會(huì)發(fā)生交換，相同元素相對(duì)位置發(fā)生變化，因此變成了不穩(wěn)定算法。

插入排序

??插入排序思想：每次將一個(gè)待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置，使數(shù)列依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。

function insertionSort(arr) {
    for (var i = 1; i < arr.length; i++) {
        var temp = arr[i]; //存儲(chǔ)用于比較的初值
        for (var j = i - 1; j >= 0; j--) {
            if (arr[j] > temp) {
                arr[j + 1] = arr[j]; //插入，替換
            } else {
                break;
            }
        }
        arr[j + 1] = temp; //若arr[j + 1]已被替換，則arr[(j - 1) + 1]此時(shí)為空，此時(shí)賦值
    }
    return arr;
}
var arr = [1, 2, 5, 2, 5, 1, 7, 4, 1, 19, 33, 2];
console.log(insertionSort(arr)); //[1, 1, 1, 2, 2, 2, 4, 5, 5, 7, 19, 33]

選擇排序

??選擇排序思想：從原始數(shù)據(jù)中找到最小元素，并放在數(shù)組的最前面。然后再?gòu)南旅娴脑刂姓业阶钚≡?，放在之前最小元素的后面，直到排序完成?/p>

function selectionSort() {
    for (var i = 0; i < arr.length - 1; i++) {
        var min = arr[i];
        var minIndex = i; //變量初始化
        for (var j = i + 1; j < arr.length; j++) { //將i與i之后的數(shù)進(jìn)行比較
            if (min > arr[j]) {
                min = arr[j];
                minIndex = j; //找到此次循環(huán)最小的數(shù)值，及其下標(biāo)
            }
        }
        arr[minIndex] = arr[i];
        arr[i] = min; //將此時(shí)的最小值與比較值替換
    }
    return arr;
}
var arr = [5, 99, 2, 9, 1, 5, 67, 7, 10, 23];
console.log(selectionSort(arr)); //[1, 2, 5, 5, 7, 9, 10, 23, 67, 99]

快速排序

??快速排序思想：選取第一個(gè)數(shù)為基準(zhǔn)，通過(guò)一次遍歷將小于它的元素放到它的左側(cè)，將大于它的元素放到它的右側(cè)，然后對(duì)它的左右兩個(gè)子序列分別再執(zhí)行同樣的操作。

function quickSort(arr) { //利用遞歸實(shí)現(xiàn)
    if (arr.length <= 1) {
        return arr;
    } //用于遞歸使用，也是判斷當(dāng)數(shù)組中元素唯一時(shí)的判斷條件。
    var pivotIndex = Math.floor(arr.length / 2);
    // console.log(pivotIndex);
    var pivot = arr.splice(pivotIndex, 1)[0]; //從原數(shù)組中取其中間值，成為一個(gè)只含有一個(gè)數(shù)的數(shù)組，取出這個(gè)數(shù)，并以此為基準(zhǔn) 
    // console.log(pivot);
    var left = [];
    var right = []; //左右區(qū)間，用于存放排序后的數(shù)
    for (var i = 0; i < arr.length; i++) {
        //小于基準(zhǔn)，放于左區(qū)間，大于基準(zhǔn)，放于右區(qū)間
        if (arr[i] <= pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat([pivot], quickSort(right)); //這里使用concat操作符，將左區(qū)間，基準(zhǔn)，右區(qū)間拼接為一個(gè)新數(shù)組
}
    var arr = [5, 99, 2, 9, 1, 5, 67, 7, 10, 23];
    console.log(quickSort(arr)); //[1, 2, 5, 5, 7, 9, 10, 23, 67, 99]

遞歸有一定的局限性，因此還有以下方式實(shí)現(xiàn)快速排序。↓↓↓↓↓

 function quickSort(arr, i, j) { //常規(guī) 
            if (i < j) {
                let left = i; //left當(dāng)前區(qū)間內(nèi)左極限
                let right = j; //right為當(dāng)前區(qū)間內(nèi)右極限
                let pivot = arr[left]; //令當(dāng)前區(qū)間左極限為基數(shù) 
                while (i < j) {
                    while (arr[j] >= pivot && i < j) { // 從后往前找比基準(zhǔn)小的數(shù)
                        j--;
                    }
                    arr[i] = arr[j]; //找到后，賦值
                    while (arr[i] <= pivot && i < j) { // 從前往后找比基準(zhǔn)大的數(shù)
                        i++;
                    }
                    arr[j] = arr[i]; //找到后，賦值
                }
                arr[i] = pivot; //此時(shí) i=j將基數(shù)放置中間位置
                quickSort(arr, left, i - 1); //左邊重復(fù)上述操作
                quickSort(arr, i + 1, right); //右邊重復(fù)上述操作
                return arr;
            }
        }
        let arr = [5, 99, 2, 9, 1, 5, 67, 7, 10, 23];
        console.log(quickSort(arr, 0, arr.length - 1)); //[1, 2, 5, 5, 7, 9, 10, 23, 67, 99]

歸并排序

??歸并排序思想：利用二分的特性，將序列分成兩個(gè)子序列進(jìn)行排序，將排序后的兩個(gè)子序列歸并（合并），當(dāng)序列的長(zhǎng)度為2時(shí)，它的兩個(gè)子序列長(zhǎng)度為1，即視為有序，可直接合并，即達(dá)到歸并排序的最小子狀態(tài)。

function　 merge(left, right) { //此函數(shù)遞歸方法
    var　 result = []; //建立一個(gè)新數(shù)組
    while (left.length > 0 && right.length > 0) { //循環(huán)，用于保證當(dāng)數(shù)組中存在可比較的值
        if (left[0] < right[0]) { //兩組數(shù)組第一個(gè)元素相互比較，小的排在前面。(left數(shù)組與right數(shù)組本身已經(jīng)完成從小到大的排序，所以其本身的第一個(gè)元素一定是當(dāng)前數(shù)組中的最小值)
            /*shift()方法用于把數(shù)組的第一個(gè)元素從其中刪除，并返回第一個(gè)元素的值。*/
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    return　 result.concat(left).concat(right); //合并數(shù)組為一個(gè)數(shù)組
}
function　 mergeSort(items) {
    if (items.length == 1) { //判斷原數(shù)組長(zhǎng)度，為1時(shí)，直接輸出結(jié)果。
        return　 items;
    }
    var　 middle = Math.floor(items.length / 2), //將原數(shù)組分為左右兩段，(遞歸思想，無(wú)限分兩段，直到每段只有一個(gè)數(shù)，然后反推比較大小排序)
        left = items.slice(0, middle),
        right = items.slice(middle);
    return　 merge(mergeSort(left), mergeSort(right)); //輸出最終結(jié)果
}
var arr = [1, 3, 5, 2, 7, 32, 8, 4, 6, 33];
console.log(mergeSort(arr)); //[1, 2, 3, 4, 5, 6, 7, 8, 32, 33]

堆排序

??歸并排序思想：利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。
??大堆頂：每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值。
??小堆頂：每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值。
這里需要知道二叉樹基本的性質(zhì)：
??·若二叉樹的層次從0開始，則在二叉樹的第i層至多有2^i個(gè)結(jié)點(diǎn)(i>=0)。
??·高度為k的二叉樹最多有2^(k) - 1個(gè)結(jié)點(diǎn)(k>=1)。 (設(shè)空樹的高度為0)
??·對(duì)任何一棵二叉樹，如果其葉子結(jié)點(diǎn)(度為0)數(shù)為m, 度為2的結(jié)點(diǎn)數(shù)為n, 則m = n + 1。
??完美二叉樹：一個(gè)深度為k(>=-1)且有2^(k+1) - 1個(gè)結(jié)點(diǎn)的二叉樹稱為完美二叉樹。除了葉子結(jié)點(diǎn)之外的每一個(gè)結(jié)點(diǎn)都有兩個(gè)孩子，每一層(當(dāng)然包含最后一層)都被完全填充。
??完全二叉樹：完全二叉樹從根結(jié)點(diǎn)到倒數(shù)第二層滿足完美二叉樹，最后一層可以不完全填充，其葉子結(jié)點(diǎn)都靠左對(duì)齊。
??完滿二叉樹：所有非葉子結(jié)點(diǎn)的度都是2。（只要你有孩子，你就必然是有兩個(gè)孩子。）

由完全二叉樹性質(zhì)可知：左邊子節(jié)點(diǎn)位置 = 當(dāng)前父節(jié)點(diǎn)的兩倍==>left = 2 * i +1；右邊子節(jié)點(diǎn)位置 = 當(dāng)前父節(jié)點(diǎn)的兩倍 + 2 ==> right = 2 * ( i + 1 )
注意：i = 0 時(shí) 是根節(jié)點(diǎn)
所以：Floor( (子– 1 ) /2)= 父節(jié)點(diǎn)的下標(biāo)

var len;      // 因?yàn)槁暶鞯亩鄠€(gè)函數(shù)都需要數(shù)據(jù)長(zhǎng)度，所以把len設(shè)置成為全局變量
    function buildMaxHeap(arr) {     // 建立大頂堆
        len = arr.length;   //取數(shù)組長(zhǎng)度
        for (var i = Math.floor(len/2-1); i >= 0; i--) {    //此時(shí)的 i 是當(dāng)前最大子節(jié)點(diǎn)的父節(jié)點(diǎn)的下標(biāo)，必須自底向上，不能自頂向下
            heapify(arr, i);
        }
    }
    function heapify(arr, i) {     // 堆調(diào)整
        var left = 2 * i + 1,     
            right = 2 * (i + 1),    //取當(dāng)前最大子節(jié)點(diǎn)，左右兄弟節(jié)點(diǎn)
            largest = i;    //此時(shí)的最大子節(jié)點(diǎn)的父節(jié)點(diǎn)下標(biāo)
        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < len && arr[right] > arr[largest]) {  //若子節(jié)點(diǎn)超過(guò)范圍 ，則為false
            largest = right;
        }                                 //保證右邊大于左邊
        if (largest != i) {             
            swap(arr, i, largest);    //兩個(gè)數(shù)互換
            heapify(arr, largest);    //直到最大值為父節(jié)點(diǎn)
        }
    }
    function swap(arr, i, j) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    function heapSort(arr) {
        buildMaxHeap(arr);
        for (var i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);                          //此時(shí) 根節(jié)點(diǎn)為最大值，將最大值放在最后一個(gè)子節(jié)點(diǎn)
            len--;                                    //數(shù)組長(zhǎng)度減一，成為新數(shù)組，再進(jìn)行堆調(diào)整
            heapify(arr, 0);    //再進(jìn)行堆調(diào)整
        }
        return arr;
    }
    var arr = [100, 99, 2, 9, 1, 6, 67, 7, 10, 23,3];
    console.log(heapSort(arr));//[1, 2, 3, 6, 7, 9, 10, 23, 67, 99, 100]

未完待續(xù)。。。

水平有限，若有錯(cuò)誤，煩請(qǐng)指出

參考地址：
1.https://www.cnblogs.com/angelye/p/7508292.html
2.http://www.itdecent.cn/p/916b15eae350
3.各個(gè)排序算法的百度百科
4.http://www.itdecent.cn/p/33cffa1ce613
5.https://segmentfault.com/a/1190000015488549?utm_source=tag-newest