自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

十五周算法訓(xùn)練營——數(shù)組排序

作者：前端點(diǎn)線面
開發(fā) 前端
Java數(shù)組排序方式一般有四種：冒泡排序法、快速排序法、選擇排序法、插入排序法。

冒泡

冒泡排序的思路：遍歷數(shù)組，然后將最大數(shù)沉到最底部。
「時間復(fù)雜度：O(N^2)；」
「空間復(fù)雜度：O(1)」

function swap(arr, i, j) {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

function bubbleSort(arr) {
    if (arr == null || arr.length <= 0) {
        return [];
    }

    const len = arr.length;
    for (let end = len - 1; end > 0; end--) {
        for (let i = 0; i < end; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
            }
        }

    }

    return arr;
}

選擇

選擇排序的實(shí)現(xiàn)思路：遍歷數(shù)組，把最小數(shù)放在頭部。
「時間復(fù)雜度：O(N^2)；」
「空間復(fù)雜度：O(1)」

function selectionSort(arr) {
    if (!Array.isArray(arr) || arr.length <= 0) {
        return [];
    }

    const swap = (arr, i, j) => {
        const temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    };

    for (let i = 0; i < arr.length - 1; i++) {
        let minIndex = i;

        for (let j = i + 1; j < arr.length; j++) {
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }

        swap(arr, i, minIndex);
    }

    return arr;
}

插入排序

插入排序?qū)崿F(xiàn)思路：將一個新的數(shù)，和前面的比較，只要當(dāng)前數(shù)小于前一個則和前一個交換位置，否則終止。
「時間復(fù)雜度：O(N^2)；」
「空間復(fù)雜度：O(1)」

function insertSort(arr) {
    if (!Array.isArray(arr) || arr.length <= 0) {
        return [];
    }

    const swap = (arr, i, j) => {
        const temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    };

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

    return arr;
}

歸并排序

歸并排序的思路：
1.先左側(cè)部分排好序。
2.再右側(cè)部分排好序。
3.再準(zhǔn)備一個輔助數(shù)組，用外排的方式，小的開始填，直到有個動到末尾，將另一個數(shù)組剩余部分拷貝到末尾。
4.再將輔助數(shù)組拷貝回原數(shù)組。
「時間復(fù)雜度:O(N * logN)」
「空間復(fù)雜度:O(N)」

歸并排序?qū)嶋H上就是一個二叉樹的后序遍歷過程。

function mergeSort(arr) {
    if (arr == null || arr.length <= 0) {
        return [];
    }
    sortProcess(arr, 0, arr.length - 1);

    return arr;
}

function sortProcess(arr, L, R) {
    // 遞歸的終止條件，就是左右邊界索引一樣
    if (L === R) {
        return;
    }
    const middle = L + ((R - L) >> 1); // 找出中間值
    sortProcess(arr, L, middle); // 對左側(cè)部分進(jìn)行遞歸
    sortProcess(arr, middle + 1, R); // 對右側(cè)部分進(jìn)行遞歸
    merge(arr, L, middle, R);
}

function merge(arr, L, middle, R) {
    var help = [];
    var l = L;
    var r = middle + 1;
    var index = 0;

    while (l <= middle && r <= R) {
        help[index++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
    }

    while (l <= middle) {
        help.push(arr[l++]);
    }

    while (r <= R) {
        help.push(arr[r++]);
    }

    for (let i = 0; i < help.length; i++) {
        arr[L + i] = help[i];
    }

    // arr.splice(L, help.length, ...help); // 利用了ES6的語法
}

快排

快速排序?qū)崿F(xiàn)思路：隨機(jī)取出一個值進(jìn)行劃分，大于該值放右邊，小于該值放左邊（該算法在經(jīng)典快排的基礎(chǔ)上經(jīng)過荷蘭國旗思想和隨機(jī)思想進(jìn)行了改造）。
「時間復(fù)雜度：O(N*logN)」
「空間復(fù)雜度：O(logN)」

快速排序其實(shí)就是二叉樹中前序遍歷的處理方式。

function quickSort(arr) {
    if (arr == null || arr.length <= 0) {
        return [];
    }

    quick(arr, 0, arr.length - 1);
    return arr;
}

function quick(arr, L, R) {
    // 遞歸結(jié)束條件是L >= R
    if (L < R) {
        // 隨機(jī)找一個值，然后和最后一個值進(jìn)行交換，將經(jīng)典排序變?yōu)榭焖倥判颍ㄒ驗(yàn)榻?jīng)典排序每次都取最后一個數(shù)據(jù)去對比，對應(yīng)0，1，2……n的情況，其復(fù)雜度為O(N^2))
        swap(arr, L + Math.floor(Math.random() * (R - L + 1)), R);
        //利用荷蘭國旗問題獲得劃分的邊界，返回的值是小于區(qū)域的最大索引和大于區(qū)域的最小索引，在這利用荷蘭國旗問題將等于區(qū)域部分就不用動了
        const tempArr = partition(arr, L, R, arr[R]);
        quick(arr, L, tempArr[0]);
        quick(arr, tempArr[1], R);
    }
}

// 返回值是小于區(qū)域的最后的索引和大于區(qū)域的第一個索引
function partition(arr, L, R, num) {
    var less = L - 1;
    var more = R + 1;
    var cur = L;
    while (cur < more) {
        if (arr[cur] < num) {
            swap(arr, ++less, cur++);
        } else if (arr[cur] > num) {
            swap(arr, --more, cur);
        } else {
            cur++;
        }
    }

    return [less, more];
}

function swap(arr, i, j) {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

堆排序

堆排序思路：
1.讓數(shù)組變成大根堆。
2.把最后一個位置和堆頂做交換。
3.則最大值在最后，則剩下部分做heapify，則重新調(diào)整為大根堆，則堆頂位置和該部分最后位置做交換。
4.重復(fù)進(jìn)行，直到減完，則這樣最后就調(diào)整完畢，整個數(shù)組排完序（為一個升序）。
「時間復(fù)雜度:O(N * logN)」
「空間復(fù)雜度:O(1)」

function heapSort(arr) {
    if (arr == null || arr.length <= 0) {
        return [];
    }

    // 首先是建立大頂堆的過程
    for (let i = 0; i < arr.length; i++) {
        heapInsert(arr, i);
    }

    var size = arr.length;//這個值用來指定多少個數(shù)組成堆，當(dāng)?shù)玫揭粋€排序的值后這個值減一

    //將堆頂和最后一個位置交換
    /**
     * 當(dāng)大頂堆建立完成后，然后不斷將最后一個位置和堆頂交換；
     * 這樣最大值就到了最后，則剩下部分做heapify，重新調(diào)整為大根堆，則堆頂位置和倒數(shù)第二個位置交換，重復(fù)進(jìn)行，直到全部排序完畢*/
    //由于前面已經(jīng)是大頂堆，所以直接交換
    swap(arr, 0, --size);
    while(size > 0) {
        // 重新變成大頂堆
        heapify(arr, 0, size);
        // 進(jìn)行交換
        swap(arr, 0, --size);
    }

    return arr;
}

// 加堆過程中
function heapInsert(arr, index) {
    //比較當(dāng)前位置和其父位置，若大于其父位置，則進(jìn)行交換，并將索引移動到其父位置進(jìn)行循環(huán)，否則跳過
    //結(jié)束條件是比父位置小或者到達(dá)根節(jié)點(diǎn)處
    while (arr[index] > arr[parseInt((index - 1) / 2)]) {
        // 進(jìn)行交換
        swap(arr, index, parseInt((index - 1) / 2));
        index = parseInt((index - 1) / 2);
    }
}

//減堆過程
/**
 * size指的是這個數(shù)組前多少個數(shù)構(gòu)成一個堆
 * 如果你想把堆頂彈出，則把堆頂和最后一個數(shù)交換，把size減1，然后從0位置經(jīng)歷一次heapify，調(diào)整一下，剩余部分變成大頂堆*/
function heapify(arr, index, size) {
    let left = 2 * index + 1;
    while (left < size) {
        let largest = (left + 1 < size && arr[left] < arr[left + 1]) ? left + 1 : left;
        largest = arr[index] > arr[largest] ? index : largest;

        //如果最大值索引和傳進(jìn)來索引一樣，則該值到達(dá)指定位置，直接結(jié)束循環(huán)
        if (index == largest) {
            break;
        }

        // 進(jìn)行交換，并改變索引和其左子節(jié)點(diǎn)
        swap(arr, index, largest);
        index = largest;
        left = 2 * index + 1;
    }
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
責(zé)任編輯：姜華 來源： 前端點(diǎn)線面
數(shù)組排序快速排序法
相關(guān)推薦

2023-06-05 07:30:51

2023-05-15 07:32:01

算法訓(xùn)練滑動窗口

2023-07-10 08:01:13

島嶼問題算法

2023-07-03 08:01:54

2023-04-17 07:33:11

反轉(zhuǎn)鏈表移除鏈表

2023-05-22 07:31:32

Nums快慢指針

2023-05-29 07:31:35

單調(diào)棧數(shù)組循環(huán)

2023-06-26 07:31:44

屬性物品背包

2023-06-13 06:51:15

斐波那契數(shù)算法

2023-06-19 07:31:34

普通動態(tài)規(guī)劃字符串

2021-09-23 10:53:43

數(shù)據(jù)中心

2016-08-05 20:21:51

CTO導(dǎo)師技術(shù)

2016-08-05 18:53:25

CTO導(dǎo)師技術(shù)

2021-07-08 20:22:05

AI

2013-04-22 12:58:14

TechExcel敏捷研發(fā)

2016-10-17 13:50:31

2009-04-29 18:12:41

GAUPS培訓(xùn)

2013-07-13 22:38:14

微軟社區(qū)微軟MVPMWW

2015-01-04 14:54:28

IT訓(xùn)練營

2016-08-04 13:41:27

CTO訓(xùn)練營，技術(shù)管理
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號