JavaScript中归并排序的介绍(代码示例)
归并排序(MERGE-SORT)是创立在归并操纵上的一种有效的排序算法,该算法是采纳分治法(pide andConquer)的一个非常典型的利用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
归并排序
归并排序是一种非常不乱的排序办法,它的时间复杂度不管是均匀,最好,最坏都是NlogN。
归并排序的2个步骤
先拆分,不断拆分到只要一个数
拆分完成后,开端递归合并
拆分历程
从上图可以看出,归并排序会将一个数组停止两两拆分,不断拆分到只要一个数的时候休止拆分。
那么拆分的代码就很简便了,就是得到一个指向中心的指针q,将数组拆分成(start,p)和(p,end)两个部分。
p表示数组的开端下标
r表示数组的完毕下标
function pide(p, r){ return Math.floor( (p + r) / 2 ); }
合并历程
合并的历程就如上图所示
遍历两组数据
停止对照大小
较小的阿谁值取出来放在第一个位置
举个例子:
假设此刻数组A的数据是[2,5,1,3]
经过我们的拆分后会是(0,2),(2,4);
我们通过A.slice(0,2)和A.slice(2,4)=>得到两个数组A1[2,5]和A2[1,3]
然后我们对数组[2,5,1,3]停止遍历,第一次会得到两边较小的数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一个最大值,比方防止A1里的数都比力小,致使第三次遍历某个数组里没有值 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 = pide(p, r); merge_sort(A, p, q); merge_sort(A, q, r); merge(A, p, q, r); return A; }
完全代码
function pide(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 = pide(p, r); merge_sort(A, p, q); merge_sort(A, q, r); merge(A, p, q, r); return A; }
以上就是JavaScript中归并排序的介绍(代码示例)的具体内容,更多请关注百分百源码网其它相关文章!