快捷導(dǎo)航

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

更新時(shí)間：2023年02月23日 09:49:59 作者：coderwhy

這篇文章主要為大家介紹了TypeScript實(shí)現(xiàn)十大排序算法之歸并排序示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

一. 歸并排序的定義

歸并排序（merge sort）是一種常見(jiàn)的排序算法：

它的基本思想是將待排序數(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í)他在為美國(guó)政府工作，研究原子彈的問(wèn)題。
由于當(dāng)時(shí)計(jì)算機(jī)，他在研究中提出了一種高效計(jì)算的方法，這個(gè)方法就是歸并排序。

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

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

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

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

二. 歸并排序的流程

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

步驟一：分解（Divide）：歸并排序使用遞歸算法來(lái)實(shí)現(xiàn)分解過(guò)程，具體實(shí)現(xiàn)中可以分為以下幾個(gè)步驟：

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

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

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

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

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

總體來(lái)看，歸并排序的基本思路是分治法，分成子問(wèn)題分別解決，然后將子問(wèn)題的解合并成整體的解。

三. 歸并排序的圖解

四. 歸并排序的代碼

下面是TypeScript實(shí)現(xiàn)的歸并排序代碼，帶有詳細(xì)的注釋?zhuān)?/p>

// 定義函數(shù)mergeSort，參數(shù)是待排序數(shù)組arr
function mergeSort(arr: number[]): number[] {
    // 計(jì)算數(shù)組長(zhǎng)度
    const n = arr.length;
    // 如果數(shù)組長(zhǎng)度小于等于1，則直接返回該數(shù)組
    if (n <= 1) {
        return arr;
    }
    // 計(jì)算中間位置
    const middle = Math.floor(n / 2);
    // 對(duì)左邊的數(shù)組進(jìn)行歸并排序
    const left = mergeSort(arr.slice(0, middle));
    // 對(duì)右邊的數(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ù)組的開(kāi)頭
    let i = 0, j = 0;
    // 定義一個(gè)空數(shù)組，用來(lái)存放合并后的數(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++]);
        }
    }
    // 將沒(méi)有比較完的剩余元素放入result數(shù)組
    while (i < left.length) {
        result.push(left[i++]);
    }
    while (j < right.length) {
        result.push(right[j++]);
    }
    // 返回合并后的數(shù)組
    return result;
}


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

代碼執(zhí)行的過(guò)程：

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