一扣墩、 冒泡排序

冒泡排序（Bubble Sort）续誉，是一種計(jì)算機(jī)科學(xué)領(lǐng)域的較簡(jiǎn)單的排序算法莱没。它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素酷鸦，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)饰躲。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成臼隔。這個(gè)算法的名字由來(lái)是因?yàn)樵酱蟮脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端嘹裂。

平均復(fù)雜度：o(n^2) 空間復(fù)雜度：o(1) 穩(wěn)定性：穩(wěn)定

步驟：
1、比較相鄰的元素摔握。如果第一個(gè)比第二個(gè)大寄狼，就交換他們兩個(gè)；
2氨淌、對(duì)每一對(duì)相鄰元素作同樣的工作泊愧，從開始第一對(duì)到結(jié)尾的最后一對(duì)，這樣宁舰，最后的元素會(huì)是最大的數(shù)拼卵；
3奢浑、針對(duì)所有的元素重復(fù)以上的步驟蛮艰，除了最后一個(gè)；
4雀彼、持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟壤蚜，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

代碼：

    // 冒泡排序 每次將最大的數(shù)值冒泡到最右面徊哑，并且執(zhí)行下次外部循環(huán)時(shí)將右部最大數(shù)剔除袜刷，
    // 外部循環(huán)執(zhí)行次數(shù)為: 數(shù)組長(zhǎng)度-1（即假設(shè)最壞情況每個(gè)數(shù)都需要位移需要位移數(shù)組長(zhǎng)度-1個(gè)數(shù)）
    // 內(nèi)部循環(huán)次數(shù)為: 數(shù)組長(zhǎng)度 - 當(dāng)前已經(jīng)選出右部最大數(shù)個(gè)數(shù)(i) - 1 （位移數(shù)比數(shù)組長(zhǎng)度少一）
let a = [1, 3, 6, 2, 7];

for (let i = 0; i < a.length - 1; i++) {
        for (let j = 0; j < a.length - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                let c = a[j];
                a[j] = a[j + 1];
                a[j + 1] = c;
                // [a[j], a[j + 1]] = [a[j + 1], a[j]]
            }
        }
    }

for (let i = a.length; i > 0; i--) {
        for (let j = 0; j < i - 1; j++) {
            if (a[j] > a[j + 1]) {
                [a[j], a[j + 1]] = [a[j + 1], a[j]]
            }
        }
    }

二、選擇排序

選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法莺丑。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最兄贰（或最大）的一個(gè)元素，存放在序列的起始位置梢莽，直到全部待排序的數(shù)據(jù)元素排完萧豆。 選擇排序是不穩(wěn)定的排序方法。

每一次從待排序的數(shù)據(jù)元素中選出最谢杳（或最大）的一個(gè)元素涮雷，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完轻局。
平均復(fù)雜度：o(n^2) 空間復(fù)雜度：o(1) 穩(wěn)定性：不穩(wěn)定

步驟：

1洪鸭、每一次循環(huán)样刷，找到最小的那個(gè)數(shù)，并用變量記住它的索引
2览爵、然后將最小值放在它該在的位置上
3置鼻、持續(xù)對(duì)越來(lái)越少的元素重復(fù)上面的步驟

代碼：

// 第一次循環(huán)找到數(shù)組中最小的數(shù)，并將其放在左面
// 之后的循環(huán)在數(shù)組剩余數(shù)中找到第二小的以此類推
for (let i = 0; i < a.length - 1; i++) {
        for (let j = i + 1; j < a.length; j++) {
            if (a[i] > a[j]) {
                let c = a[j];
                a[j] = a[i];
                a[i] = c;
                // [a[j], a[i]] = [a[i], a[j]]
            }
        }
    }

待確認(rèn)(兩種循環(huán)執(zhí)行次數(shù)相同蜓竹，但比選擇排序交換次數(shù)要多)

// 其實(shí)就是先選取前兩個(gè)數(shù)對(duì)比沃疮，大數(shù)放后面。第二次加入第三個(gè)數(shù)逐項(xiàng)對(duì)比梅肤，如果第三個(gè)數(shù)大于第一個(gè)數(shù)就和第一個(gè)數(shù)交換司蔬，之后第二個(gè)數(shù)和交換后的第三個(gè)數(shù)對(duì)比交換。即一個(gè)逐漸增加的數(shù)組進(jìn)行排序姨蝴，2個(gè)數(shù)據(jù)排序俊啼，3個(gè)數(shù)據(jù)排序，新加入的數(shù)據(jù)每個(gè)對(duì)比左医，符合條件交換（這步比插入排序多了授帕，因?yàn)閷⒁呀?jīng)排好的數(shù)組又便利一遍排序）
// 首先外部循環(huán)確定當(dāng)前要比對(duì)的值a[i]
// 然后內(nèi)部循環(huán)逐項(xiàng)對(duì)比數(shù)組a[i]之前的數(shù)a[j]與a[i]做比對(duì),前一項(xiàng)大于后一項(xiàng)時(shí)交換位置。
for (let i = 1; i < a.length; i++) {
        for (let j = 0; j < i; j++) {
            if (a[i] < a[j]) {
                [a[j], a[i]] = [a[i], a[j]]
            }
        }
    }

三浮梢、插入排序

插入排序基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中跛十，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)秕硝，算法適用于少量數(shù)據(jù)的排序芥映，時(shí)間復(fù)雜度為O(n^2)。是穩(wěn)定的排序方法远豺。插入排序的基本思想是：每步將一個(gè)待排序的紀(jì)錄奈偏，按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當(dāng)位置上，直到全部插入完為止躯护。

// 先確定第一個(gè)基準(zhǔn)數(shù)據(jù)惊来，由于需要對(duì)比所以第一個(gè)基準(zhǔn)數(shù)據(jù)為a[1], i為1。 (這里基準(zhǔn)數(shù)據(jù)為currentValue)
// 拿到基準(zhǔn)數(shù)據(jù)后再確定基準(zhǔn)數(shù)據(jù)的前一項(xiàng)(這里為a[flag])進(jìn)行對(duì)比如果前一項(xiàng)大于基準(zhǔn)數(shù)據(jù)則前一項(xiàng)向后移一位（a[flag + 1] = a[flag]）
// 移動(dòng)完畢因?yàn)榍懊孢€有其他更多的數(shù)（前一項(xiàng)的前一項(xiàng)的前一項(xiàng)...）都需要和基準(zhǔn)數(shù)比如果比基準(zhǔn)數(shù)大則向后移一位
// 直到基準(zhǔn)數(shù)大于（該前一項(xiàng)）將基準(zhǔn)數(shù)插入到（該前一項(xiàng)的后面）（ a[flag + 1] = currentValue;）
// while循環(huán)停止的判斷標(biāo)準(zhǔn)是執(zhí)行到基準(zhǔn)數(shù)大于等于（前一項(xiàng)）（a[flag] <= currentValue）
// 或者（前一項(xiàng)）不存在即數(shù)組的-1項(xiàng)時(shí)跳出循環(huán) （flag < 0）
// 由于數(shù)組的-1項(xiàng)為undefined undefined和數(shù)字對(duì)比一定為false所以一定跳出while循環(huán)所以flag >= 0判斷條件可以不寫
for (let i = 1; i < a.length; i++) {
        flag = i - 1;
        currentValue = a[i];
        // flag >= 0  可以不寫因?yàn)閍[flag]為undefined undefined和任何數(shù)對(duì)比都為false可以終止while循環(huán)
        while (flag >= 0 && a[flag] > currentValue) {
            a[flag + 1] = a[flag]
            flag--;
        }
        a[flag + 1] = currentValue;
    }

四棺滞、快速排序

快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)裁蚁。它的基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小继准，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序枉证，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列锰瘸。

// 先選取一個(gè)基準(zhǔn)數(shù)據(jù)（例如a[0]）刽严，定義為flag用來(lái)和這個(gè)基準(zhǔn)數(shù)據(jù)做對(duì)比，并且從數(shù)組中刪除該基準(zhǔn)數(shù)。
// 然后定義空數(shù)組left和right, 將數(shù)組每項(xiàng)和基準(zhǔn)數(shù)做對(duì)比舞萄，如果小于基準(zhǔn)數(shù)放在left數(shù)組中眨补，大于的話放在right數(shù)組中
// 分別遞歸調(diào)用處理left和right數(shù)組，將處理好的left數(shù)組倒脓、中間選取的基準(zhǔn)數(shù)據(jù)和right數(shù)組合并
// 因?yàn)槊看芜f歸調(diào)用都要?jiǎng)h除一個(gè)基準(zhǔn)數(shù)據(jù)所以到最后這個(gè)數(shù)組長(zhǎng)度為1時(shí)就直接返回?cái)?shù)組
var a = [2, 8, 7, 5, 1, 9]

    function quickSort(arr) {
        if (arr.length <= 1) {
            return arr
        }
        let flag = arr[0];
        let left = [];
        let right = [];
        arr.splice(0, 1);
        for (let i = 0; i < arr.length; i++) {
            if (arr[i] < flag) {
                left.push(arr[i])
            } else {
                right.push(arr[i])
            }
        }
        return quickSort(left).concat(flag, quickSort(right))
    }

    console.log(quickSort(a))

五撑螺、歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并崎弃，得到完全有序的序列甘晤；即先使每個(gè)子序列有序，再使子序列段間有序饲做。若將兩個(gè)有序表合并成一個(gè)有序表线婚，稱為二路歸并。
(1） 把長(zhǎng)度為n的輸入序列分成兩個(gè)長(zhǎng)度為n/2的子序列盆均；
（2）對(duì)這兩個(gè)子序列分別采用歸并排序塞弊；
（3） 將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。

download.png

// 將數(shù)組從中間分開為兩個(gè)數(shù)組left和right泪姨，遞歸調(diào)用將分開的兩個(gè)數(shù)組再次分別分為兩個(gè)數(shù)組游沿，直到該數(shù)組長(zhǎng)度為1時(shí)
// 遞歸調(diào)用的同時(shí)將left和right第一項(xiàng)做對(duì)比小的放入到空數(shù)組中并刪除最小項(xiàng)，并且將剩余的數(shù)組left和right數(shù)組合并（因?yàn)椴荒艽_定到底最后剩余的數(shù)組中l(wèi)eft和right哪個(gè)大）肮砾，其實(shí)每次對(duì)比的時(shí)候左右數(shù)組都是已經(jīng)排序好的數(shù)組所以只需每次循環(huán)取出兩數(shù)組中最小項(xiàng)即可排序诀黍，剩余的最大數(shù)還留在left或者right數(shù)組中需要通過(guò)concat合并過(guò)來(lái)
function mergeSort(arr) { //采用自上而下的遞歸方法
        var len = arr.length;
        if (len < 2) {
            return arr;
        }
        var middle = Math.floor(len / 2),
            left = arr.slice(0, middle),
            right = arr.slice(middle);
        return merge(mergeSort(left), mergeSort(right));
    }

    function merge(left, right) {
        var result = [];
        while (left.length && right.length) {
            // 不斷比較left和right數(shù)組的第一項(xiàng)，小的取出存入res
            left[0] < right[0] ? result.push(left.shift()) : result.push(right.shift());
        }
        return result.concat(left, right);
    }

    console.log(mergeSort(a))

六仗处、希爾排序

希爾排序(Shell Sort)是插入排序的一種眯勾。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本疆柔。希爾排序是非穩(wěn)定排序算法咒精。希爾排序是把記錄按下標(biāo)的一定增量分組镶柱，對(duì)每組使用直接插入排序算法排序旷档；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多歇拆，當(dāng)增量減至1時(shí)鞋屈，整個(gè)文件恰被分成一組，算法便終止故觅。

function shellSort(arr) {
        for (let i = Math.floor(arr.length); i > 0; i = Math.floor(i / 2)) {
            for (let j = i; j < arr.length; j++) {
                let k = j;
                let currentValue = arr[j];
                while (k - i >= 0 && arr[k - i] > currentValue) {
                    arr[k] = arr[k - i];
                    k = k - i;
                }
                arr[k] = currentValue
            }
        }
    }

    var arr = [3, 5, 7, 1, 4, 56, 12, 78, 25, 0, 9, 8, 42, 37];
    shellSort(arr)
    console.log(arr)