JS实现的冒泡排序，快速排序，插入排序算法示例

本文实例讲述了JS实现的冒泡排序，快速排序，插入排序算法。分享给大家供大家参考，具体如下：

一、冒泡排序

大致分两步：

1、依次对比相邻2个数字，前者比后者大就调换位置

2、重复第一步操作，直到所有数字都按顺序排列

function bubbleSort(arr){
  for(var i=1; i<arr.length; i++){
   for(var j=0; j<arr.length-i; j++){
    if(arr[j]>arr[j+1]){
     arr[j]=[arr[j+1],arr[j+1]=arr[j]][0];
    }
   }
  }
  return arr;
}

二、快速排序

大致分三步：

1、找基准（一般是以中间项为基准）
2、遍历数组，小于基准的放在left，大于基准的放在right
3、递归

function quickSort(arr){
   //如果数组<=1,则直接返回
   if(arr.length<=1){return arr;}
   var pivotIndex=Math.floor(arr.length/2);
   //找基准，并把基准从原数组删除
   var pivot=arr.splice(pivotIndex,1)[0];
   //定义左右数组
   var left=[], right=[];
   //比基准小的放在left，比基准大的放在right
   for(var i=0;i<arr.length;i++){
    if(arr[i]<=pivot){
     left.push(arr[i]);
    }else{
     right.push(arr[i]);
    }
   }
   //递归
   return quickSort(left).concat(pivot, quickSort(right));
}

三、插入排序（对于少量元素比较有效）

原理：像排序一手扑克牌，开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的

位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较，如图2-1所示。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌。

手上的牌是有序数列，桌子上的牌是无序数列。

function insertSort(arr){
  //从第二个数开始，依次插入
  for(var i=1; i<arr.length; i++){
   //判断目标元素是否小于前一个元素
   if(arr[i]<arr[i-1]){
    var current=arr[i];
    var j=i-1;
    //从有序数列从后往前对比，如果目标元素小于与之对比的当前元素，当前元素位置往后挪一位
    while(j>=0 && current<arr[j]) {
     arr[j+1]=arr[j];
     j--;
    }
    //插入
    arr[j+1]=current;
   }
  }
  return arr;
}

插入排序另一种写法（个人感觉还是这种效率快）

function insertSort(arr) {
  for(let i=1; i<arr.length; i++) {
    if(arr[i] < arr[0]) {
      arr.unshift(arr.splice(i,1)[0]);
    }else {
      for(let j=i-1; j>=0; j--) {
        if(arr[i] > arr[j]) {
          let current = arr.splice(i,1)[0];
          arr.splice(j+1,0,current);
          break;
        }
      }
    }
  }
  return arr;
}

感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具：http://tools.jb51.net/code/HtmlJsRun测试上述代码运行效果。

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

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

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

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

赞 (0)

相关推荐

  • javascript算法学习(直接插入排序)

    1.基本思想 假设待排序的记录存放在数组R[1..n]中.初始时,R[1]自成1个有序区,无序区为R[2..n].从i=2起直至i=n为止,依次将R[i]插入当前的有序区R[1..i-1]中,生成含n个记录的有序区. 复制代码 代码如下: <!doctype html> <html> <head><title>javascript直接插入排序</title> <meta charset = "utf-8" /> &

  • Javascript实现快速排序（Quicksort）的算法详解

    Javascript实现快速排序（Quicksort）的算法详解

    目前,最常见的排序算法大概有七八种,其中"快速排序"(Quicksort)使用得最广泛,速度也较快.它是图灵奖得主C. A. R. Hoare(1934--)于1960时提出来的. "快速排序"的思想很简单,整个排序过程只需要三步: (1)在数据集之中,选择一个元素作为"基准"(pivot). (2)所有小于"基准"的元素,都移到"基准"的左边:所有大于"基准"的元素,都移到"

  • 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数据结构与算法之基本排序算法定义与效率比较【冒泡、选择、插入排序】

    本文实例讲述了JavaScript数据结构与算法之基本排序算法定义与效率比较.分享给大家供大家参考,具体如下: javascript数据结构与算法--基本排序算法(冒泡.选择.排序)及效率比较 一.数组测试平台 javascript数据结构与算法--基本排序(封装基本数组的操作),封装常规数组操作的函数,比如:插入新数据,显示数组数据,还有交换数组元素等操作来调用不同的排序算法 function CArray(numElements) { this.dataStore = []; this.po

  • javascript 冒泡排序 正序和倒序实现代码

    复制代码 代码如下: <script type="text/javascript"> var R1=[5,2,10,4,90,88,65,62]; var R2=[5,2,10,4,90,88,65,62]; function BubbleSort1(){ var n=R1.length; for(var i=0;i<n-1;i++){ var flag=false; for(var j=0;j<n-i;j++){ var temp; if(R1[j]<R

  • Javascript快速排序算法详解

    快速排序是对冒泡排序的一种改进.通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,最终达到整个数据变成有序序列. 假设要排序的数组是A[0]--A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为基准数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序.值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对

  • JavaScript 冒泡排序和选择排序的实现代码

    废话不多说了,直接给大家贴代码了,具体代码如下所述: var array = [1,2,3,4,5]; // ---> 服务 //效率 ---> 针对一个有序的数组 效率最高 //标志 true false for(var j = 0; j < array.length - 1;j++ ){ //- j 每次排序完成之后 后面减少比较的次数 var isTrue = true; //如果数组本身就是升序,则直接输出 for(var i = 0; i < array.length -

  • 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

  • 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,

  • C#实现冒泡排序和插入排序算法

    1.选择排序(冒泡排序) 升序 用第一个元素跟其他元素比较,如果该元素比其他元素,则交换,保证该元素是最小的.然后再用第二个元素跟后面其他的比较,保证第二个元素是除第一个最小的.依次循环,直到整个数组. /// <summary> /// 选择排序 /// </summary> public class Selection:BaseSort { public static long usedTimes = 0; public Selection() { } public stati

  • JS实现的冒泡排序，快速排序，插入排序算法示例

    JS实现的冒泡排序，快速排序，插入排序算法示例

    本文实例讲述了JS实现的冒泡排序,快速排序,插入排序算法.分享给大家供大家参考,具体如下: 一.冒泡排序 大致分两步: 1.依次对比相邻2个数字,前者比后者大就调换位置 2.重复第一步操作,直到所有数字都按顺序排列 function bubbleSort(arr){ for(var i=1; i<arr.length; i++){ for(var j=0; j<arr.length-i; j++){ if(arr[j]>arr[j+1]){ arr[j]=[arr[j+1],arr[j+

  • Python实现的直接插入排序算法示例

    Python实现的直接插入排序算法示例

    本文实例讲述了Python实现的直接插入排序算法.分享给大家供大家参考,具体如下: # -*- coding:utf-8 -*- '''直接插入的python实现 时间复杂度O(n**2) 空间复杂度O(1) 稳定 思想:先将前两个元素排序,第三个元素插入前面已排好序列, 后面的元素依次插入之前已经排好序的序列 ''' author = 'Leo Howell' L = [89,67,56,45,34,23,1] def direct_insert_sort(numbers): for i in

  • JS实现的JSON数组去重算法示例

    本文实例讲述了JS实现的JSON数组去重算法.分享给大家供大家参考,具体如下: 需求描述:去除JSON数组中paymode字段相同的项,并将paymoney累加. paylist:[{paymode:'1',payname:"现金",paymoney:"20"}, {paymode:'2',payname:"支付宝",paymoney:"50"},{paymode:'1',payname:"现金",paym

  • JS实现判断有效的数独算法示例

    JS实现判断有效的数独算法示例

    本文实例讲述了JS实现判断有效的数独算法.分享给大家供大家参考,具体如下: 判断一个 9x9 的数独是否有效.只需要根据以下规则,验证已经填入的数字是否有效即可. 1.数字 1-9 在每一行只能出现一次. 2.数字 1-9 在每一列只能出现一次. 3.数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次. 数独部分空格内已填入了数字,空白格用 '.' 表示. 示例 1: 输入: [ ["5","3",".",".",

  • 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); 方法二:

  • Java实现直接插入排序和折半插入排序算法示例

    Java实现直接插入排序和折半插入排序算法示例

    直接插入排序​ 1 排序思想: 将待排序的记录Ri插入到已经排好序的记录R1,R2,--,R(N-1)中. 对于一个随机序列而言,就是从第二个元素开始,依次将这个元素插入到它之前的元素中的相应位置.它之前的元素已经排好序. 第1次排序:将第2个元素插入到前边的有序列表(此时前边只有一个元素,当然是有序的),之后,这个序列的前2个元素就是有序的了. 第2次排序:将第3个元素插入到前边长度为2的有序列表,使得前2个元素是有序的. 以此类推,直到将第N个元素插入到前面长度为(N-1)的有序列表中. 2

  • tween.js缓动补间动画算法示例

    一.理解tween.js 如果看到上面的已经理解了,可以跳过下面的部分.下面为对Tween.js的解释 下面就介绍如何使用这个Tween了,首先b.c.d三个参数(即初始值,变化量,持续时间)在缓动开始前,是需要先确定好的. 首先引入一个概念就补间动画 Flash做动画时会用到Tween类,利用它可以做很多动画效果,例如缓动.弹簧等等. tween.js在Flash中可以解释为补间动画. 那么问题来了,什么是补间动画呢? 相信学过Flash的都知道补间动画是flash主要的非常重要的表现手段之一

  • java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述

    算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗点说,就是计算机解题的过程.在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法.前者是推理实现的算法,后者是操作实现的算法. 一个算法应该具有以下五个重要的特征: 1.有穷性: 一个算法必须保证执行有限步之后结束: 2.确切性: 算法的每一步骤必须有确切的定义: 3.输入:一个算法有0个或多个输入,以刻画运算对象的初始情况: 4.输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果.没有输出的算法是毫无意义的:

  • JS前端面试必备——基本排序算法原理与实现方法详解【插入/选择/归并/冒泡/快速排序】

    JS前端面试必备——基本排序算法原理与实现方法详解【插入/选择/归并/冒泡/快速排序】

    本文实例讲述了JS前端面试必备--基本排序算法原理与实现方法.分享给大家供大家参考,具体如下: 排序算法是面试及笔试中必考点,本文通过动画方式演示,通过实例讲解,最后给出JavaScript版的排序算法 插入排序 算法描述: 1. 从第一个元素开始,该元素可以认为已经被排序 2. 取出下一个元素,在已经排序的元素序列中从后向前扫描 3. 如果该元素(已排序)大于新元素,将该元素移到下一位置 4. 重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置 5. 将新元素插入到该位置后 6. 重复

随机推荐