JavaScript排序算法之堆排序

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

堆积排序(Heapsort)是指利用堆积树(堆)这种资料结构所设计的一种排序算法,可以利用数组的特点快速定位指定索引的元素。

1991年计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W.Floyd)和威廉姆斯(J.Williams)在1964年共同发明了著名的堆排序算法( Heap Sort )。

堆排序(HeapSort)是一树形选择排序。堆排序的特点是:在排序过程中,将R[l..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构),在当前无序区中选择关键字最大(或最小)的记录。

<script type="text/javascript">
//document.write("----------堆排序,选择排序的升级,任何时候的时间复杂度都为------nlogn------<br />");
//var array = new Array(12, 25, 32, 16, 18, 27, 59, 69, 36);
//heapSort(array);
function heapSort(array) {
	var temp;
	var i;
	var result = "";
	for (i = Math.floor(array.length / 2); i >= 0; i--) {
   		heapAdjust(array, i, array.length - 1); //将数组array构建成一个大顶堆
	}
 	for (i = array.length - 1; i >= 0; i--) {
    	/*把根节点交换出去*/
      	temp = array[i];
    	array[i] = array[0];
       	array[0] = temp;
      	/*余下的数组继续构建成大顶堆*/
     	heapAdjust(array, 0, i - 1);
     	/* 输出结果 */
    	result += "<br />第" + (array.length - i).toString() + "遍排序的结果是:";
      	for (var n = 0; n < array.length; n++) {
         	result += array[n] + ",";
       	}
      	/* 输出结果结束 */
   	}
	return result;
}
//要调整的子树
//start为数组开始下标
//max是数组结束下标
function heapAdjust(array, start, max) {
	var temp, j;
 	temp = array[start];//temp是根节点的值
	for (j = 2 * start; j < max; j *= 2) {
  		if (j < max && array[j] < array[j + 1]) {  //取得较大孩子的下标
      		++j;
     	}
   		if (temp >= array[j])
         	break;
     		array[start] = array[j];
       		start = j;
	}
	array[start] = temp;
}
//document.write("<br /><br />")
</script>

效果演示

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

不打个分吗?

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

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

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

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

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

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

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

《深入理解计算机系统(原书第2版)》 布莱恩特(Randal E.Bryant) (作者), 奥哈拉伦(David R.O'Hallaron) (作者), 龚奕利 (译者), 雷迎春 (译者)

《深入理解计算机系统》从程序员的视角详细阐述计算机系统的本质概念,并展示这些概念如何实实在在地影响应用程序的正确性、性能和实用性。全书共12章,主要内容包括信息的表示和处理、程序的机器级表示、处理器体系结构、优化程序性能、存储器层次结构、链接、异常控制流、虚拟存储器、系统级I/O、网络编程、并发编程等。书中提供子大量的例子和练习题,并给出部分答案,有助于读者加深对正文所述概念和知识的理解。

更多计算机宝库...