欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

TypeScript實(shí)現(xiàn)十大排序算法之歸并排序示例詳解

 更新時(shí)間:2023年02月23日 09:49:59   作者:coderwhy  
這篇文章主要為大家介紹了TypeScript實(shí)現(xiàn)十大排序算法之歸并排序示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

一. 歸并排序的定義

歸并排序(merge sort)是一種常見的排序算法:

  • 它的基本思想是將待排序數(shù)組分成若干個(gè)子數(shù)組。
  • 然后將相鄰的子數(shù)組歸并成一個(gè)有序數(shù)組。
  • 最后再將這些有序數(shù)組歸并(merge)成一個(gè)整體有序的數(shù)組。

這個(gè)算法最早出現(xiàn)在1945年,由約翰·馮·諾伊曼(John von Neumann)(又一個(gè)天才,現(xiàn)代計(jì)算機(jī)之父,馮·諾依曼結(jié)構(gòu)、普林斯頓結(jié)構(gòu))首次提出。

  • 當(dāng)時(shí)他在為美國政 府工作,研究原子彈的問題。
  • 由于當(dāng)時(shí)計(jì)算機(jī),他在研究中提出了一種高效計(jì)算的方法,這個(gè)方法就是歸并排序。

歸并排序的基本思路是先將待排序數(shù)組遞歸地拆分成兩個(gè)子數(shù)組,然后對每個(gè)子數(shù)組進(jìn)行排序,最后將兩個(gè)有序子數(shù)組合并成一個(gè)有序數(shù)組。

  • 在實(shí)現(xiàn)中,我們可以使用“分治法”來完成這個(gè)過程,即將大問題分解成小問題來解決。

歸并排序的算法復(fù)雜度為 O(nlogn),是一種比較高效的排序算法,因此在實(shí)際應(yīng)用中被廣泛使用。

雖然歸并排序看起來比較復(fù)雜,但是只要理解了基本思路,實(shí)現(xiàn)起來并不困難,而且它還是一個(gè)非常有趣的算法。

二. 歸并排序的流程

歸并排序是一種基于分治思想的排序算法,其基本思路可以分為三個(gè)步驟:

步驟一:分解(Divide):歸并排序使用遞歸算法來實(shí)現(xiàn)分解過程,具體實(shí)現(xiàn)中可以分為以下幾個(gè)步驟:

  • 如果待排序數(shù)組長度為1,認(rèn)為這個(gè)數(shù)組已經(jīng)有序,直接返回;
  • 將待排序數(shù)組分成兩個(gè)長度相等的子數(shù)組,分別對這兩個(gè)子數(shù)組進(jìn)行遞歸排序;
  • 將兩個(gè)排好序的子數(shù)組合并成一個(gè)有序數(shù)組,返回這個(gè)有序數(shù)組。

步驟二:合并(Merge):合并過程中,需要比較每個(gè)子數(shù)組的元素并將它們有序地合并成一個(gè)新的數(shù)組:

  • 可以使用兩個(gè)指針 i 和 j 分別指向兩個(gè)子數(shù)組的開頭,比較它們的元素大小,并將小的元素插入到新的有序數(shù)組中。
  • 如果其中一個(gè)子數(shù)組已經(jīng)遍歷完,就將另一個(gè)子數(shù)組的剩余部分直接插入到新的有序數(shù)組中。
  • 最后返回這個(gè)有序數(shù)組。

步驟三:歸并排序的遞歸終止條件:

  • 歸并排序使用遞歸算法來實(shí)現(xiàn)分解過程,當(dāng)子數(shù)組的長度為1時(shí),認(rèn)為這個(gè)子數(shù)組已經(jīng)有序,遞歸結(jié)束。

總體來看,歸并排序的基本思路是分治法,分成子問題分別解決,然后將子問題的解合并成整體的解。

三. 歸并排序的圖解

四. 歸并排序的代碼

下面是TypeScript實(shí)現(xiàn)的歸并排序代碼,帶有詳細(xì)的注釋:

// 定義函數(shù)mergeSort,參數(shù)是待排序數(shù)組arr
function mergeSort(arr: number[]): number[] {
    // 計(jì)算數(shù)組長度
    const n = arr.length;
    // 如果數(shù)組長度小于等于1,則直接返回該數(shù)組
    if (n <= 1) {
        return arr;
    }
    // 計(jì)算中間位置
    const middle = Math.floor(n / 2);
    // 對左邊的數(shù)組進(jìn)行歸并排序
    const left = mergeSort(arr.slice(0, middle));
    // 對右邊的數(shù)組進(jìn)行歸并排序
    const right = mergeSort(arr.slice(middle));
    // 合并兩個(gè)排好序的數(shù)組
    return merge(left, right);
}

// 定義函數(shù)merge,參數(shù)是兩個(gè)排好序的數(shù)組left和right
function merge(left: number[], right: number[]): number[] {
    // 定義指針變量,分別指向兩個(gè)數(shù)組的開頭
    let i = 0, j = 0;
    // 定義一個(gè)空數(shù)組,用來存放合并后的數(shù)組
    const result = [];
    // 比較兩個(gè)數(shù)組的第一個(gè)元素,將較小的放入result數(shù)組
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }
    // 將沒有比較完的剩余元素放入result數(shù)組
    while (i < left.length) {
        result.push(left[i++]);
    }
    while (j < right.length) {
        result.push(right[j++]);
    }
    // 返回合并后的數(shù)組
    return result;
}


// 測試數(shù)據(jù)
const testArr = [5, 2, 9, 1, 5, 6];
// 調(diào)用插入排序函數(shù)
const sortedArr = mergeSort(testArr);
// 打印結(jié)果
console.log(sortedArr);

代碼執(zhí)行的過程:

  • mergeSort 函數(shù)實(shí)現(xiàn)歸并排序的遞歸調(diào)用,在該函數(shù)內(nèi),如果數(shù)組的長度小于等于1,直接返回該數(shù)組。
  • 如果數(shù)組的長度大于1,那么執(zhí)行以下代碼:
    • 先計(jì)算數(shù)組的中點(diǎn),并將數(shù)組分為左右兩半。
    • 遞歸調(diào)用左邊和右邊的數(shù)組,最終得到兩個(gè)有序的數(shù)組。
  • merge 函數(shù)實(shí)現(xiàn)將兩個(gè)有序的數(shù)組合并為一個(gè)有序的數(shù)組。

五. 歸并排序的時(shí)間復(fù)雜度

復(fù)雜度的分析過程:

  • 假設(shè)數(shù)組長度為 n,需要進(jìn)行 logn 次歸并操作;
  • 每次歸并操作需要 O(n) 的時(shí)間復(fù)雜度;
  • 因此,歸并排序的時(shí)間復(fù)雜度為 O(nlogn)。

最好情況: O(log n)

  • 最好情況下,待排序數(shù)組已經(jīng)是有序的了,那么每個(gè)子數(shù)組都只需要合并一次,即只需要進(jìn)行一次歸并操作。
  • 因此,此時(shí)的時(shí)間復(fù)雜度是 O(log n)。

最壞情況: O(nlogn)

最壞情況下,待排序數(shù)組是逆序的,那么每個(gè)子數(shù)組都需要進(jìn)行多次合并。

因此,此時(shí)的時(shí)間復(fù)雜度為 O(nlogn)。

平均情況: O(nlogn)

  • 在平均情況下,我們假設(shè)待排序數(shù)組中任意兩個(gè)元素都是等概率出現(xiàn)的。
  • 此時(shí),可以證明歸并排序的時(shí)間復(fù)雜度為 O(nlogn)。

六. 歸并排序的總結(jié)

歸并排序是一種分治策略的排序算法,是利用分治的思想將一個(gè)大問題分成小問題,并在適當(dāng)?shù)牡胤胶喜⑺鼈円越鉀Q該問題的方法。

它是一種穩(wěn)定的排序算法,時(shí)間復(fù)雜度為O(nlogn)。

歸并排序使用了額外的空間,因此更適合處理大數(shù)據(jù)。

  • 歸并排序的基本流程是通過遞歸將數(shù)組分成兩半,分別進(jìn)行遞歸排序,最終再進(jìn)行合并。
  • 具體來說,將數(shù)組的中間元素作為分界點(diǎn),分別對左右兩邊的數(shù)組進(jìn)行排序,并在排序完成后進(jìn)行合并。

歸并排序的代碼實(shí)現(xiàn)較為簡單,但要注意關(guān)于遞歸函數(shù)和合并函數(shù)的實(shí)現(xiàn)。

歸并排序是一種不需要過多研究的算法,適合于所有的排序場景。

以上就是TypeScript實(shí)現(xiàn)十大排序算法之歸并排序示例詳解的詳細(xì)內(nèi)容,更多關(guān)于TypeScript算法歸并排序的資料請關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

最新評論