資訊專欄INFORMATION COLUMN
摘要：歸并排序是建立在歸并操作上的一種有效的排序算法該算法是采用分治法的一個(gè)非常典型的應(yīng)用。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。歸并排序歸并排序是一種非常穩(wěn)定的排序方法，它的時(shí)間復(fù)雜度無論是平均，最好，最壞都是。
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide andConquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。歸并排序
歸并排序是一種非常穩(wěn)定的排序方法，它的時(shí)間復(fù)雜度無論是平均，最好，最壞都是NlogN。
歸并排序的2個(gè)步驟先拆分，一直拆分到只有一個(gè)數(shù)
拆分完成后，開始遞歸合并
拆分過程從上圖可以看出，歸并排序會將一個(gè)數(shù)組進(jìn)行兩兩拆分，一直拆分到只有一個(gè)數(shù)的時(shí)候停止拆分。
那么拆分的代碼就很簡單了，就是得到一個(gè)指向中間的指針q，將數(shù)組拆分成(start,p)和（p，end）兩個(gè)部分。
p表示數(shù)組的開始下標(biāo)
r表示數(shù)組的結(jié)束下標(biāo)
function divide(p, r){
return Math.floor( (p + r) / 2 );
}
合并過程
合并的過程就如上圖所示
遍歷兩組數(shù)據(jù)
進(jìn)行對比大小
較小的那個(gè)值取出來放在第一個(gè)位置
舉個(gè)例子：
假設(shè)現(xiàn)在數(shù)組A的數(shù)據(jù)是[2,5,1,3]
經(jīng)過我們的拆分后會是(0,2),(2,4);
我們通過A.slice(0,2)和A.slice(2,4)=>得到兩個(gè)數(shù)組A1[2,5]和A2[1,3]
然后我們對數(shù)組[2,5,1,3]進(jìn)行遍歷，第一次會得到兩邊較小的數(shù)1，第二次2，第三次3，第四次是5
function merge(A, p, q, r){
const A1 = A.slice(p, q);
const A2 = A.slice(q, r);
// 哨兵，往A1和A2里push一個(gè)最大值，比如防止A1里的數(shù)都比較小，導(dǎo)致第三次遍歷某個(gè)數(shù)組里沒有值
A1.push(Number.MAX_SAFE_INTEGER);
A2.push(Number.MAX_SAFE_INTEGER);
// 循環(huán)做比較，每次取出較小的那個(gè)值
for (let i = p, j = 0, k = 0; i < r; i++) {
if (A1[j] < A2[k]) {
A[i] = A1[j];
j++;
} else {
A[i] = A2[k];
k++;
}
}
}
主程序
主程序就是做遞歸重復(fù)上面的操作了
function merge_sort(A, p = 0, r) {
r = r || A.length;
if (r - p === 1) {
return;
}
const q = divide(p, r);
merge_sort(A, p, q);
merge_sort(A, q, r);
merge(A, p, q, r);
return A;
}
完整代碼
function divide(p, r) {
return Math.floor((p + r) / 2);
}
function merge(A, p, q, r) {
const A1 = A.slice(p, q);
const A2 = A.slice(q, r);
A1.push(Number.MAX_SAFE_INTEGER);
A2.push(Number.MAX_SAFE_INTEGER);
for (let i = p, j = 0, k = 0; i < r; i++) {
if (A1[j] < A2[k]) {
A[i] = A1[j];
j++;
} else {
A[i] = A2[k];
k++;
}
}
}
function merge_sort(A, p = 0, r) {
r = r || A.length;
if (r - p === 1) {
return;
}
const q = divide(p, r);
merge_sort(A, p, q);
merge_sort(A, q, r);
merge(A, p, q, r);
return A;
}
推薦閱讀
數(shù)據(jù)結(jié)構(gòu)系列：
js數(shù)據(jù)結(jié)構(gòu)-棧
js數(shù)據(jù)結(jié)構(gòu)-鏈表
js數(shù)據(jù)結(jié)構(gòu)-隊(duì)列
js數(shù)據(jù)結(jié)構(gòu)-二叉樹（二叉堆）
js數(shù)據(jù)結(jié)構(gòu)-二叉樹（二叉搜索樹）
js數(shù)據(jù)結(jié)構(gòu)-散列表(哈希表)
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/100887.html
摘要：今天再來看看另外三種時(shí)間復(fù)雜度都是的排序算法，分別是希爾排序歸并排序和快速排序。三數(shù)取中法求將放到數(shù)組的末尾總結(jié)這三種排序算法的平均時(shí)間復(fù)雜度都是，歸并排序和快速排序的應(yīng)用更廣泛。 1. 回顧 前面說完了三種較為簡單的排序算法，分別是冒泡排序，選擇排序和插入排序，它們的平均情況時(shí)間復(fù)雜度都是 O(n2)，比較的高，適合小規(guī)模的數(shù)據(jù)排序，其中插入排序的效率稍高，所以更推薦使用插入排序。今...
摘要：排序算法是最基本最常用的算法，不同的排序算法在不同的場景或應(yīng)用中會有不同的表現(xiàn)，我們需要對各種排序算法熟練才能將它們應(yīng)用到實(shí)際當(dāng)中，才能更好地發(fā)揮它們的優(yōu)勢。今天，來總結(jié)下各種排序算法。 排序算法是最基本最常用的算法，不同的排序算法在不同的場景或應(yīng)用中會有不同的表現(xiàn)，我們需要對各種排序算法熟練才能將它們應(yīng)用到實(shí)際當(dāng)中，才能更好地發(fā)揮它們的優(yōu)勢。今天，來總結(jié)下各種排序算法。 下面這個(gè)表格...
摘要：的陣列視為基本型別，所以必須用傳參考才能修改原陣列插入排序快速排序歸并排序堆排序獲取個(gè)數(shù)處理一半的數(shù)據(jù) function bubble_sort(&$arr) {//php的陣列視為基本型別，所以必須用傳參考才能修改原陣列 for ($i = 0; $i < count($arr) - 1; $i++) for ($j = 0; $j < count($arr)...
摘要：本篇主要實(shí)現(xiàn)九八大排序算法，分別是冒泡排序，插入排序，選擇排序，希爾排序，歸并排序，快速排序，堆排序計(jì)數(shù)排序。希爾排序是非穩(wěn)定排序算法。歸并排序算法依賴歸并操作。但是，計(jì)數(shù)排序可以用在基數(shù)排序算法中，能夠更有效的排序數(shù)據(jù)范圍很大的數(shù)組。 本篇主要實(shí)現(xiàn)九(八）大排序算法，分別是冒泡排序，插入排序，選擇排序，希爾排序，歸并排序，快速排序，堆排序,計(jì)數(shù)排序。希望大家回顧知識的時(shí)候也能從我的這...
摘要：創(chuàng)建最大堆堆排序八計(jì)數(shù)排序以上節(jié)選自維基百科代碼如下為數(shù)組中的最大值待排序數(shù)組長度設(shè)置輸出序列，初始化為設(shè)置技術(shù)序列，初始化為本文章參考維基百科和八大排序算法實(shí)現(xiàn)合輯 一、冒泡排序 冒泡排序算法的運(yùn)作如下： 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。針對所有的元素重復(fù)以上的步驟，...
閱讀 1129·2021-11-23 10:05
閱讀 1809·2021-11-12 10:36
閱讀 1868·2019-08-30 15:56
閱讀 1699·2019-08-29 12:32
閱讀 3057·2019-08-28 18:04
閱讀 3444·2019-08-26 12:17
閱讀 2516·2019-08-26 11:35
閱讀 1259·2019-08-23 15:11
