算法重头学-归并排序

归并排序

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

上一章我们大概了解了一下“插入排序”，并且使用js对插入排序进行了实现。本章紧接着谈到“归并排序”，因为这里要用到“插入排序”算法评估的最佳场景。

假设数组Array[1,N]，且该数组为从小到大已正向排序的，现需将数值Value插入到该数组，当且仅当Value < Array[1]时只需要做一次比较运算即可得到插入位置，这种情况是“插入排序”的最佳场景。

代码

"use strict";
var arr = [5,2,4,6,1,3];function sort(arr){let len = arr.length;merge(arr,0,len-1,len-1);console.log(arr);
}function merge(arr,start,end){if(start >= end){return;}//以数组的中点为分界线，分别对左右2段进行排序let middle = Math.floor((start + end)/2);merge(arr,start,middle);merge(arr,middle + 1,end);let s = start,m = middle,i,tmp;/*** 2个已排序的数组进行合并* arr[s,m]为Left数组，arr[m+1,end]为Right数组* 利用插入排序的最优场景，将arr[m+1,end]中的*一次遍历结束的标志是：2个数组都为空（全部扫描）**/while( s <= m && m < end){//正向排序的最优处理方案，将一个值插入到所有值都比该数值都大的正向数组中if(arr[s] >= arr[m + 1]){tmp = arr[m + 1];for(i = m ; i >= s ; i--){arr[i + 1] = arr[i];}arr[s] = tmp;m++;}else{//缩小下一次检索的范围s++;}}
}sort(arr);

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！