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

作者：前端點(diǎn)線面 2023-04-03 07:33:05

Java數(shù)組排序方式一般有四種：冒泡排序法、快速排序法、選擇排序法、插入排序法。

冒泡

冒泡排序的思路：遍歷數(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ù)放在頭部。
「時(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)思路：將一個(gè)新的數(shù)，和前面的比較，只要當(dāng)前數(shù)小于前一個(gè)則和前一個(gè)交換位置，否則終止。
「時(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)備一個(gè)輔助數(shù)組，用外排的方式，小的開始填，直到有個(gè)動(dòng)到末尾，將另一個(gè)數(shù)組剩余部分拷貝到末尾。
4.再將輔助數(shù)組拷貝回原數(shù)組。
「時(shí)間復(fù)雜度:O(N * logN)」
「空間復(fù)雜度:O(N)」
歸并排序?qū)嶋H上就是一個(gè)二叉樹的后序遍歷過程。

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); // 對(duì)左側(cè)部分進(jìn)行遞歸
    sortProcess(arr, middle + 1, R); // 對(duì)右側(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ī)取出一個(gè)值進(jìn)行劃分，大于該值放右邊，小于該值放左邊（該算法在經(jīng)典快排的基礎(chǔ)上經(jīng)過荷蘭國(guó)旗思想和隨機(jī)思想進(jìn)行了改造）。
「時(shí)間復(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ī)找一個(gè)值，然后和最后一個(gè)值進(jìn)行交換，將經(jīng)典排序變?yōu)榭焖倥判颍ㄒ驗(yàn)榻?jīng)典排序每次都取最后一個(gè)數(shù)據(jù)去對(duì)比，對(duì)應(yīng)0，1，2……n的情況，其復(fù)雜度為O(N^2))
        swap(arr, L + Math.floor(Math.random() * (R - L + 1)), R);
        //利用荷蘭國(guó)旗問題獲得劃分的邊界，返回的值是小于區(qū)域的最大索引和大于區(qū)域的最小索引，在這利用荷蘭國(guó)旗問題將等于區(qū)域部分就不用動(dòng)了
        const tempArr = partition(arr, L, R, arr[R]);
        quick(arr, L, tempArr[0]);
        quick(arr, tempArr[1], R);
    }
}

// 返回值是小于區(qū)域的最后的索引和大于區(qū)域的第一個(gè)索引
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.把最后一個(gè)位置和堆頂做交換。
3.則最大值在最后，則剩下部分做heapify，則重新調(diào)整為大根堆，則堆頂位置和該部分最后位置做交換。
4.重復(fù)進(jìn)行，直到減完，則這樣最后就調(diào)整完畢，整個(gè)數(shù)組排完序（為一個(gè)升序）。
「時(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;//這個(gè)值用來指定多少個(gè)數(shù)組成堆，當(dāng)?shù)玫揭粋€(gè)排序的值后這個(gè)值減一

    //將堆頂和最后一個(gè)位置交換
    /**
     * 當(dāng)大頂堆建立完成后，然后不斷將最后一個(gè)位置和堆頂交換；
     * 這樣最大值就到了最后，則剩下部分做heapify，重新調(diào)整為大根堆，則堆頂位置和倒數(shù)第二個(gè)位置交換，重復(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)行交換，并將索引移動(dòng)到其父位置進(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指的是這個(gè)數(shù)組前多少個(gè)數(shù)構(gòu)成一個(gè)堆
 * 如果你想把堆頂彈出，則把堆頂和最后一個(gè)數(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ù)組排序快速排序法