JavaScript实现选择排序算法的实例分析（图）-js教程-PHP中文网

首页

web前端

js教程

JavaScript实现选择排序算法的实例分析（图）

黄舟

Apr 15, 2017 am 09:31 AM

javascript算法选择排序

这篇文章主要介绍了JavaScript实现的选择排序算法,结合实例形式分析了选择排序的原理、实现步骤与相关操作技巧,需要的朋友可以参考下

本文实例讲述了JavaScript实现的选择排序算法。分享给大家供大家参考，具体如下：

简单选择排序是人们最熟悉的比较方式，其算法思想为：从数组的开头开始，将第一个元素和其他元素进行比较。检查完所有元素后，最小的元素会被放到数组的第一个位置，然后算法会从第二个位置继续。这个过程会一直进行，当进行到数组的倒数第二个位置时，所有的数据便完成了排序。

代码如下：

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>JavaScript选择排序</title>
</head>
<body>
<script type="text/javascript">
 function selectSort(nums){//选择排序
  var min;//最小值
  for(var outer=0;outer<nums.length-1;outer++){//外循环选中元素
   min=outer;
   for(var inner=outer+1;inner<=nums.length;++inner){
    if(nums[inner]<nums[min]){//如果内循环中元素比选中元素小
     min=inner;//将其标为最小元素
    }//直到每次外循环的最小元素
    swap(nums,outer,min);//最小值被调整到合适的位置
   }
  }
 }
 function swap(arr,i,j){//交换位置
  var temp=arr[i];
  arr[i]=arr[j];
  arr[j]=temp;
 }
 function show(nums){//显示数组
  for(var i=0;i<nums.length;i++){
   document.write(nums[i]+&#39; &#39;);
  }
  document.write(&#39;<br>&#39;);
 }
 var nums=[6,8,0,6,7,4,3,5,5,10];
 show(nums);//6 8 0 6 7 4 3 5 5 10
 selectSort(nums);
 show(nums);//0 3 4 5 5 6 6 7 9 10
</script>
</body>
</html>

分析可得，简单选择排序的时间复杂度为O（n2）。选择排序的主要操作是进行关键字之间的比较，因此改进简单选择排序应该从如何减少比较出发。其实现实生活中就有一个很好的例子，就是比赛总的锦标赛。8个人中选出冠军其实不需要7+6+5=18场比赛，可以通过两两比较也就是11场比赛。这种方法叫做树形选择排序。

树形选择排序是一种按照锦标赛的思想进行选择排序的方法，首先对n个记录的关键字进行两两比较，然后在其中n/2个较小者之间再进行两两比较，直到找出最小关键字。可以通过一个完全二叉树来表示，由于含有n个结点的完全二叉树的深度为log2n+1，所以排序过程中每选择一个次小关键字仅需要log2n次操作，所以其时间复杂度O（nlog2n），但是这种排序有一种缺点就是占用空间大。

所以我们需要介绍一种更加优秀的排序，也就是堆排序。

附：堆排序算法

堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占用一个存储空间。

堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得当前无序区中选取最大（或最小）关键字的记录变得简单。我们以大跟堆为例子，排序的基本操作如下：

首先是建堆，建堆就是不断调整堆的过程，从len2处开始调整，一直到第一个节点，此处len是堆中元素的个数。建堆的过程是线性的过程，从len2到0处一直调用调整堆的过程，建堆的时间复杂度为O（n）。
接下来是调整堆，调整堆在建堆和堆排序的过程中都会用到，利用的思想是比较节点i和它的孩子节点left(i)和right(i)，选出三者最大（或最小）者，如果最大（小）值不是节点i而是它的一个子节点，那么交换两个节点，然后继续递归。
然后是堆排序：将堆的根节点取出，最后一个元素替换根节点，将前面len-1个节点继续进行堆调整的过程，然后再讲根节点取出，直到所有结点取出。调整堆的时间复杂度为O(log2n)
所以堆排序的时间复杂度为O（nlog2n）。堆排序是就地排序，其辅助空间为O（1）。但是它不稳定，（排序的稳定性是指如果在排序的序列中，存在前后相同的两个元素的话，排序前和排序后他们的相对位置不发生变化）。

下面模拟建堆的过程：

堆排序对于记录数较少的文件并不值得提倡，但是对于n较大的文件还是挺有效的。

以上是JavaScript实现选择排序算法的实例分析（图）的详细内容。更多信息请关注PHP中文网其他相关文章！

声明

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

Python和JavaScript：了解每个的优势May 06, 2025 am 12:15 AM

Python和JavaScript各有优势，选择取决于项目需求和个人偏好。1.Python易学，语法简洁，适用于数据科学和后端开发，但执行速度较慢。2.JavaScript在前端开发中无处不在，异步编程能力强，Node.js使其适用于全栈开发，但语法可能复杂且易出错。

JavaScript的核心：它是在C还是C上构建的？May 05, 2025 am 12:07 AM

javascriptisnotbuiltoncorc; saninterpretedlanguagethatrunsonenginesoftenwritteninc.1）javascriptwasdesignedAsalightweight，解释edganguageforwebbrowsers.2）Enginesevolvedfromsimpleterterterpretpreterterterpretertestojitcompilerers，典型地提示。

JavaScript应用程序：从前端到后端May 04, 2025 am 12:12 AM

JavaScript可用于前端和后端开发。前端通过DOM操作增强用户体验，后端通过Node.js处理服务器任务。1.前端示例：改变网页文本内容。2.后端示例：创建Node.js服务器。

Python vs. JavaScript：您应该学到哪种语言？May 03, 2025 am 12:10 AM

选择Python还是JavaScript应基于职业发展、学习曲线和生态系统：1)职业发展：Python适合数据科学和后端开发，JavaScript适合前端和全栈开发。2)学习曲线：Python语法简洁，适合初学者；JavaScript语法灵活。3)生态系统：Python有丰富的科学计算库，JavaScript有强大的前端框架。

JavaScript框架：为现代网络开发提供动力May 02, 2025 am 12:04 AM

JavaScript框架的强大之处在于简化开发、提升用户体验和应用性能。选择框架时应考虑：1.项目规模和复杂度，2.团队经验，3.生态系统和社区支持。

JavaScript，C和浏览器之间的关系May 01, 2025 am 12:06 AM

引言我知道你可能会觉得奇怪，JavaScript、C 和浏览器之间到底有什么关系？它们之间看似毫无关联，但实际上，它们在现代网络开发中扮演着非常重要的角色。今天我们就来深入探讨一下这三者之间的紧密联系。通过这篇文章，你将了解到JavaScript如何在浏览器中运行，C 在浏览器引擎中的作用，以及它们如何共同推动网页的渲染和交互。JavaScript与浏览器的关系我们都知道，JavaScript是前端开发的核心语言，它直接在浏览器中运行，让网页变得生动有趣。你是否曾经想过，为什么JavaScr