JavaScript排序算法之归并排序

归并排序
服务器君一共花费了112.223 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

归并操作的过程如下:

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  4. 重复步骤3直到某一指针达到序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾
<script type="text/javascript">
//document.write("----------归并排序-----复杂排序里唯一一个稳定的,时间复杂度为nlogn------<br />");
//var array = new Array(12, 25, 32, 16, 18, 27, 59, 69, 36);
var count = 0;
//调用排序方法进行排序
//mSort(array, array, 0, array.length - 1);
//source源数组
//dest目标数组
//s起始下标
//t目标下标
function mSort(source, dest, s, t) {
	var result = "";
	var m; //取中间值
            
	var dest2 = new Array();
	if (s == t) {
 		dest[s] = source[s];
    }
 	else {
      	m = Math.floor((s + t) / 2);
    	mSort(source, dest2, s, m);
     	mSort(source, dest2, m+1 , t);
      	merge(dest2, dest, s, m, t);
     	/* 输出结果 */
     	result += "<br />第" + ++count + "遍排序的结果是:";
 		for (var n = 0; n < dest.length; n++) {
         	result+= array[n] + ",";
       	}
    	/* 输出结果结束 */
	}
	return result;
}
        
/* 输出结果结束 */
//将两个数组按照从小到大的顺序融合
//source原数组
//dest排序后的数组
//s第一个下标
//m第二个数组下表
//n总长度
function merge(source, dest, s, m, n) {
	for (var j = m+1, k = s; j <= n && s <= m; k++) {
 		if (source[s] < source[j]) {
     		dest[k] = source[s++];
   		}
  		else {
        	dest[k] = source[j++];
      	}
 	}
           
	//将剩余排不完的有序数组加入到dest的末端
  	if (s <= m) {
       	for (var l = 0; l <= m - s; l++) {
       		dest[k + l] = source[s+l];
     	}
 	}
	if (j <= n) {
     	for (var l = 0; l <= n - j; l++) {
     		dest[k + l] = source[j+l];
      	}
	}
}
//document.write("<br /><br />")
</script>

效果演示

本文地址:http://www.nowamagic.net/librarys/veda/detail/255,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/255

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《代码大全(第2版)》 史蒂夫•迈克康奈尔 (Steve McConnell) (作者), 金戈 (译者)

代码大全(第2版)是著名IT畅销书作者、《IEEE Software》杂志前主编、具有20年编程与项目管理经验的Steve McConnell十余年前的经典著作的全新演绎:第2版做了全面的更新,增加了很多与时俱进的内容,包括对新语言、新的开发过程与方法论的讨论等等。这是一本百科全书式的软件构建手册,涵盖了软件构建活动的方方面面,尤其强调提高软件质量的种种实践方法。

更多计算机宝库...