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]+' ');
  }
  document.write('<br>');
 }
 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相关内容感兴趣的读者可查看本站专题：《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

赞 (0)

相关推荐

  • javascript随机之洗牌算法深入分析

    洗牌算法是我们常见的随机问题,在玩游戏.随机排序时经常会碰到.它可以抽象成这样:得到一个M以内的所有自然数的随机顺序数组. 在百度搜"洗牌算法",第一个结果是<百度文库-洗牌算法>,扫了一下里面的内容,很多内容都容易误导别人走上歧途,包括最后用链表代替数组,也只是一个有限的优化(链表也引入了读取效率的损失). 该文里的第一种方法,可以简单描述成:随机抽牌,放在另一组:再次抽取,抽到空牌则重复抽."抽到空牌则重复抽"这会导致后面抽到空牌的机会越来越大,显然

  • 基于JavaScript实现的插入排序算法分析

    基于JavaScript实现的插入排序算法分析

    本文实例讲述了基于JavaScript实现的插入排序算法.分享给大家供大家参考,具体如下: 根据排序过程中使用的存储器不同,可以将排序方法分为两大类:内部排序和外部排序. 内部排序是指待排序记录存放在计算机随机存储器中进行的排序过程:外部排序指的是待排序的记录数量很大,以致内存一次不能容纳全部记录,在排序过程中尚需对外存进行访问的排序过程. 下面介绍几种常见的内部排序方式: 插入排序 插入排序是一种最简单的排序方法,它的基本操作是将一个记录插入已排好序的有序表中,从而得到一个新的.记录数加1的有

  • JS随机洗牌算法之数组随机排序

    JS随机洗牌算法之数组随机排序

    推荐阅读:JavaScript学习笔记之数组的增.删.改.查 JavaScript学习笔记之数组求和方法 JavaScript学习笔记之数组随机排序 洗牌算法是一个比较形象的术语,本质上让一个数组内的元素随机排列.举例来说,我们有一个如下图所示的数组,数组长度为 9,数组内元素的值顺次分别是 1~9: 从上面这个数组入手,我们要做的就是打乱数组内元素的顺序: 代码实现 维基百科上的 Fisher–Yates shuffle 词条对洗牌算法做了详细介绍,下面演示的算法也是基于其中的理论编写的: A

  • JavaScript实现经典排序算法之冒泡排序

    冒泡排序可谓是最经典的排序算法了,它是基于比较的排序算法,时间复杂度为O(n^2),其优点是实现简单,n较小时性能较好. 1)算法原理        相邻的数据进行两两比较,小数放在前面,大数放在后面,这样一趟下来,最小的数就被排在了第一位,第二趟也是如此,如此类推,直到所有的数据排序完成. 2)算法描述        <1>比较相邻的元素.如果第一个比第二个大,就交换它们两个:        <2>对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会

  • 基于JavaScript实现的快速排序算法分析

    基于JavaScript实现的快速排序算法分析

    本文实例讲述了基于JavaScript实现的快速排序算法.分享给大家供大家参考,具体如下: 首先要介绍一下冒泡排序,冒泡排序的过程很简单,首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个关键字交换,然后比较第二个和第三个,直到最后一个比较完成.这是第一趟冒泡,其结果使得关键字最大的记录被安置到最后一个位置上了.然后对序列前n-1个元素进行第二次冒泡,将倒数第二个选出.以此类推直到所有被选出,冒泡结束. 通过分析可以得出,冒泡排序的时间复杂度为O(n2). 快速排序是对冒泡

  • 详解js数组的完全随机排列算法

    详解js数组的完全随机排列算法

    Array.prototype.sort 方法被许多 JavaScript 程序员误用来随机排列数组.最近做的前端星计划挑战项目中,一道实现 blackjack 游戏的问题,就发现很多同学使用了 Array.prototype.sort 来洗牌. 洗牌 以下就是常见的完全错误的随机排列算法: function shuffle(arr){ return arr.sort(function(){ return Math.random() - 0.5; }); } 以上代码看似巧妙利用了 Array.

  • JS实现的随机排序功能算法示例

    本文实例讲述了JS实现的随机排序功能算法.分享给大家供大家参考,具体如下: 使用JS编写一个方法 让数组中的元素每次刷新随机排列 方法一: var arr =[1,2,3,4]; var t; for(var i = 0;i < arr.length; i++){ var rand = parseInt(Math.random()*arr.length); t = arr[rand]; arr[rand] =arr[i]; arr[i] = t; } console.log(arr); 方法二:

  • JavaScript实现经典排序算法之选择排序

    表现最稳定的排序算法之一,因为无论什么数据进去都是O(n²)的时间复杂度.....所以用到它的时候,数据规模越小越好.唯一的好处可能就是不占用额外的内存空间. 1)算法原理 先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕. 2)算法描述和实现 n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果.具体算法描述如下: <1>初始状态:无序区为R[1..n],有序区为

  • JavaScript随机打乱数组顺序之随机洗牌算法

    假如有一个数组是这样子: var arr1 = ["a", "b", "c", "d"]; 如何随机打乱数组顺序,也即洗牌. 有一个比较广为传播的简单随机算法: function RandomSort (a,b){ return (0.5 - Math.random()); } 实际证明上面这个并不完全随机. 随便一搜网上太多这种东西了,看一下stackoverflow上的一个高分回答,答案出自github上. knuth-s

  • JavaScript实现经典排序算法之插入排序

    插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂.像排序一手扑克牌,开始时,我们的左手为空并且桌子上的牌面向下.然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置.为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较,拿在左手上的牌总是排序好的,原来这些牌是桌子上牌堆中顶部的牌. 1)算法原理 插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法.它的工作原理是通过构建有序

  • 基于JavaScript实现的希尔排序算法分析

    基于JavaScript实现的希尔排序算法分析

    本文实例讲述了基于JavaScript实现的希尔排序算法.分享给大家供大家参考,具体如下: 通过对直接插入排序的分析,可知其时间复杂度为O(n2),但是,如果待排序序列为正序时,其时间复杂度可提高至O(n).希尔排序正是对此进行改进的排序.希尔排序的核心理念与插入排序不同,它会首先比较距离较远的元素,而非相邻元素.通过定义一个间隔序列来表示在排序过程中进行比较的元素之间有多远的间隔. 下图演示了希尔排序中间隔序列是如何运行的: 下面我们通过js来实现希尔排序,代码如下: <!DOCTYPE ht

  • JS实现随机数生成算法示例代码

    1: 复制代码 代码如下: var MT = []; var index = 0; function initialize_generator(seed) { MT[0] = seed; for (var i = 1; i < 624; i++) { MT[i] = 0xffffffff & (0x6c078965 * (MT[i - 1] ^ (MT[i - 1] >> 30)) + i); } } function generate_numbers() { for (var

随机推荐