您好,登錄后才能下訂單哦!
這篇文章主要介紹“TypeScript怎么實現(xiàn)歸并排序”,在日常操作中,相信很多人在TypeScript怎么實現(xiàn)歸并排序問題上存在疑惑,小編查閱了各式資料,整理出簡單好用的操作方法,希望對大家解答”TypeScript怎么實現(xiàn)歸并排序”的疑惑有所幫助!接下來,請跟著小編一起來學(xué)習(xí)吧!
歸并排序(merge sort)是一種常見的排序算法:
它的基本思想是將待排序數(shù)組分成若干個子數(shù)組。
然后將相鄰的子數(shù)組歸并成一個有序數(shù)組。
最后再將這些有序數(shù)組歸并(merge)成一個整體有序的數(shù)組。
這個算法最早出現(xiàn)在1945年,由約翰·馮·諾伊曼(John von Neumann)(又一個天才,現(xiàn)代計算機(jī)之父,馮·諾依曼結(jié)構(gòu)、普林斯頓結(jié)構(gòu))首次提出。
當(dāng)時他在為美國政 府工作,研究原子彈的問題。
由于當(dāng)時計算機(jī),他在研究中提出了一種高效計算的方法,這個方法就是歸并排序。
歸并排序的基本思路是先將待排序數(shù)組遞歸地拆分成兩個子數(shù)組,然后對每個子數(shù)組進(jìn)行排序,最后將兩個有序子數(shù)組合并成一個有序數(shù)組。
在實現(xiàn)中,我們可以使用“分治法”來完成這個過程,即將大問題分解成小問題來解決。
歸并排序的算法復(fù)雜度為 O(nlogn),是一種比較高效的排序算法,因此在實際應(yīng)用中被廣泛使用。
雖然歸并排序看起來比較復(fù)雜,但是只要理解了基本思路,實現(xiàn)起來并不困難,而且它還是一個非常有趣的算法。
歸并排序是一種基于分治思想的排序算法,其基本思路可以分為三個步驟:
步驟一:分解(Divide):歸并排序使用遞歸算法來實現(xiàn)分解過程,具體實現(xiàn)中可以分為以下幾個步驟:
如果待排序數(shù)組長度為1,認(rèn)為這個數(shù)組已經(jīng)有序,直接返回;
將待排序數(shù)組分成兩個長度相等的子數(shù)組,分別對這兩個子數(shù)組進(jìn)行遞歸排序;
將兩個排好序的子數(shù)組合并成一個有序數(shù)組,返回這個有序數(shù)組。
步驟二:合并(Merge):合并過程中,需要比較每個子數(shù)組的元素并將它們有序地合并成一個新的數(shù)組:
可以使用兩個指針 i 和 j 分別指向兩個子數(shù)組的開頭,比較它們的元素大小,并將小的元素插入到新的有序數(shù)組中。
如果其中一個子數(shù)組已經(jīng)遍歷完,就將另一個子數(shù)組的剩余部分直接插入到新的有序數(shù)組中。
最后返回這個有序數(shù)組。
步驟三:歸并排序的遞歸終止條件:
歸并排序使用遞歸算法來實現(xiàn)分解過程,當(dāng)子數(shù)組的長度為1時,認(rèn)為這個子數(shù)組已經(jīng)有序,遞歸結(jié)束。
總體來看,歸并排序的基本思路是分治法,分成子問題分別解決,然后將子問題的解合并成整體的解。
下面是TypeScript實現(xiàn)的歸并排序代碼,帶有詳細(xì)的注釋:
// 定義函數(shù)mergeSort,參數(shù)是待排序數(shù)組arr function mergeSort(arr: number[]): number[] { // 計算數(shù)組長度 const n = arr.length; // 如果數(shù)組長度小于等于1,則直接返回該數(shù)組 if (n <= 1) { return arr; } // 計算中間位置 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)); // 合并兩個排好序的數(shù)組 return merge(left, right); } // 定義函數(shù)merge,參數(shù)是兩個排好序的數(shù)組left和right function merge(left: number[], right: number[]): number[] { // 定義指針變量,分別指向兩個數(shù)組的開頭 let i = 0, j = 0; // 定義一個空數(shù)組,用來存放合并后的數(shù)組 const result = []; // 比較兩個數(shù)組的第一個元素,將較小的放入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ù)實現(xiàn)歸并排序的遞歸調(diào)用,在該函數(shù)內(nèi),如果數(shù)組的長度小于等于1,直接返回該數(shù)組。
如果數(shù)組的長度大于1,那么執(zhí)行以下代碼:
先計算數(shù)組的中點,并將數(shù)組分為左右兩半。
遞歸調(diào)用左邊和右邊的數(shù)組,最終得到兩個有序的數(shù)組。
merge
函數(shù)實現(xiàn)將兩個有序的數(shù)組合并為一個有序的數(shù)組。
復(fù)雜度的分析過程:
假設(shè)數(shù)組長度為 n,需要進(jìn)行 logn 次歸并操作;
每次歸并操作需要 O(n) 的時間復(fù)雜度;
因此,歸并排序的時間復(fù)雜度為 O(nlogn)。
最好情況: O(log n)
最好情況下,待排序數(shù)組已經(jīng)是有序的了,那么每個子數(shù)組都只需要合并一次,即只需要進(jìn)行一次歸并操作。
因此,此時的時間復(fù)雜度是 O(log n)。
最壞情況: O(nlogn)
最壞情況下,待排序數(shù)組是逆序的,那么每個子數(shù)組都需要進(jìn)行多次合并。
因此,此時的時間復(fù)雜度為 O(nlogn)。
平均情況: O(nlogn)
在平均情況下,我們假設(shè)待排序數(shù)組中任意兩個元素都是等概率出現(xiàn)的。
此時,可以證明歸并排序的時間復(fù)雜度為 O(nlogn)。
到此,關(guān)于“TypeScript怎么實現(xiàn)歸并排序”的學(xué)習(xí)就結(jié)束了,希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí),快去試試吧!若想繼續(xù)學(xué)習(xí)更多相關(guān)知識,請繼續(xù)關(guān)注億速云網(wǎng)站,小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。