JS排序算法之冒泡排序，选择排序与插入排序实例分析

本文实例讲述了JS排序算法之冒泡排序，选择排序与插入排序。分享给大家供大家参考，具体如下：

冒泡排序：

对数组的中的数据，依次比较相邻两数的大小。

如果前面的数据大于后面的数据，就交换这两个数。

时间复杂度O(n^2)

function bubble(array){
 var temp;
 for(var i=0; i<arr.length; i++){
  for(var j=0; j<arr.length; j++){
   if(arr[j]>arr[j+1]){
    temp = arr[j+1];
    arr[j+1] =arr[j];
    arr[j]=temp;
   }
  }console.log(arr);
 }
}//冒泡排序

选择排序：

首先从原始数组中选择一个最小的数据，和第一个位置1的数据交换。

再从剩下的n-1个数据中选择次小的数据，将其和第二个位置的数据交换。

不断重复，知道最后两个数据完成交换。

时间复杂度O(n^2)

function selectionSort(array){
 var min,temp;
 for(var i=0; i<array.length-1; i++){
  min=i;
  for(var j=i+1; j<array.length; j++){
   if(array[j]<array[min]){
    min=j;
   }
  }
  swap(array,min,i);
 }
 console.log(array);
}//选择排序
function swap(array,i,j){
 var temp =array[i];
 array[i]=array[j];
 array[j]=temp;
}//两个数字交换

插入排序：

首先对前两个数据从小到大比较。

接着将第三个数据与排好的前两个数据比较，将第三个数据插入合适的位置。以此类推。

(插入排序有两个循环，外循环将数组挨个移动，内循环将对外循环选中的元素及他前面的数进行比较。)

时间复杂度O(n^2)

function insertSort(arr){
 var temp, j;
 for(var i=1; i<arr.length; i++){
  temp =arr[i];
  j=i;
  while(j>0 && arr[j-1]>temp){
   arr[j]=arr[j-1];
   j--;
  }
  arr[j]=temp;
 }
}

PS：这里再为大家推荐一款关于排序的演示工具供大家参考：

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

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

赞 (0)

相关推荐

  • JS折半插入排序算法实例

    本文实例讲述了JS折半插入排序算法.分享给大家供大家参考,具体如下: function pushArrayWithIndex(arr, index, value) { // 将元素添加到数组的指定位置 var temArr = arr.slice(0, index); temArr.push(value); return temArr.concat(arr.slice(index)); } /* test for pushArrayWithIndex var arr = [1, 2, 3, 4,

  • JavaScript希尔排序、快速排序、归并排序算法

    以var a = [4,2,6,3,1,9,5,7,8,0];为例子. 1.希尔排序. 希尔排序是在插入排序上面做的升级.是先跟距离较远的进行比较的一些方法. function shellsort(arr){ var i,k,j,len=arr.length,gap = Math.ceil(len/2),temp; while(gap>0){ for (var k = 0; k < gap; k++) { var tagArr = []; tagArr.push(arr[k]) for (i

  • Javascript中的常见排序算法

    具体代码及比较如下所示: 复制代码 代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">  <html xmlns="http://www.w3.org/1999/xhtml" lang="gb2312">

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

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

  • JS实现的计数排序与基数排序算法示例

    本文实例讲述了JS实现的计数排序与基数排序算法.分享给大家供大家参考,具体如下: 计数排序 计数排序就是简单的桶排序,一个桶代表数组中一个数出现的个数,所以需要一个和数组数字范围一样大的辅助数组,一般用在范围小于100的排序,时间复杂度为O(n),空间复杂度为数组的数字范围. /** * 范围在 start - end 之间的排序 * 计数排序需要辅助数组,该辅助数组的长度是待排序数组的范围,所以一般用作范围小于100的排序 */ function countSort(arr, start, e

  • JavaScript排序算法之希尔排序的2个实例

    JavaScript排序算法之希尔排序的2个实例

    插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率.但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位.希尔排序按其设计者希尔(Donald Shell)的名字命名,该算法由1959年公布.一些老版本教科书和参考手册把该算法命名为Shell-Metzner,即包含Marlene Metzner Norton的名字,但是根据Metzner本人的说法,"我没有为这种算法做任何事,我的名字不应该出现在算法的名字中." 希尔排序基本思想:先取一个小于n的

  • Javascript堆排序算法详解

    堆排序分为两个过程: 1.建堆. 堆实质上是完全二叉树,必须满足:树中任一非叶子结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字. 堆分为:大根堆和小根堆,升序排序采用大根堆,降序排序采用小根堆. 如果是大根堆,则通过调整函数将值最大的节点调整至堆根. 2.将堆根保存于尾部,并对剩余序列调用调整函数,调整完成后,再将最大跟保存于尾部-1(-1,-2,...,-i),再对剩余序列进行调整,反复进行该过程,直至排序完成. 复制代码 代码如下: //调整函数 function head

  • js交换排序 冒泡排序算法（Javascript版）

    比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数. 针对所有的元素重复以上的步骤,除了最后一个. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较. function sort(elements){ for(var i=0;i<elements.length-1;i++){ for(var j=0;j<elements.length-i-1;j++){ if(elemen

  • JavaScript排序算法动画演示效果的实现方法

    JavaScript排序算法动画演示效果的实现方法

    之前在知乎看到有人在问 自己写了一个冒泡排序算法如何用HTML,CSS,JavaScript展现出来排序过程.   感觉这个问题还挺有意思 .前些时间就来写了一个.这里记录一下实现过程. 基本的思想是把排序每一步的时候每个数据的值用DOM结构表达出来. 问题一:如何将JavaScript排序的一步步进程展现出来? 我试过的几种思路: 1.让JavaScript暂停下来,慢下来. JavaScript排序是很快的,要我们肉眼能看到它的实现过程,我首先想到的是让排序慢下来. 排序的每一个循环都让它停

  • Javascript冒泡排序算法详解

    比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数. 针对所有的元素重复以上的步骤,除了最后一个. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较. 复制代码 代码如下: function sort(elements){   for(var i=0;i<elements.length-1;i++){     for(var j=0;j<elements.length-i-

  • Javascript排序算法之合并排序（归并排序）的2个例子

    归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用. 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个

  • JavaScript中几种常见排序算法小结

    说明 写这个主要是为了锻炼自己,并无实际意义. 每个浏览器测试得出的数据会不一样.比如我用chrome 测试 一般快速排序都会最快,IE 则根据数组长度有可能希尔最快. 不要用太大数据去测试冒泡排序(浏览器崩溃了我不管) 如果有兴趣可以 下载测试页面 个人理解 冒泡排序:最简单,也最慢,貌似长度小于7最优 插入排序: 比冒泡快,比快速排序和希尔排序慢,较小数据有优势 快速排序:这是一个非常快的排序方式,V8的sort方法就使用快速排序和插入排序的结合 希尔排序:在非chrome下数组长度小于10

随机推荐