cari

Rumah >hujung hadapan web >tutorial js >JavaScript实现选择排序算法的实例分析（图）

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

黄舟
黄舟asal
2017-04-15 09:31:361914semak imbas

这篇文章主要介绍了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较大的文件还是挺有效的。

Atas ialah kandungan terperinci JavaScript实现选择排序算法的实例分析（图）. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan：
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Artikel sebelumnya：理解Javascript中的“+”运算符Artikel seterusnya：JavaScript实现快速排序算法的代码图文分析

Artikel berkaitan

Lihat lagi