js数值排序中冒泡算法的4种简单实现

zacklee 发布于2019-08-29 15:10 / 1393人阅读

摘要：实现数组排序的算法很多其中冒泡算法是比较简单的冒泡的基本原理是相邻的两个数进行比较按照排序的条件进行互换例如对数值从小到大排序随着不断的互换最大的那个值会慢慢冒泡到数组的末端基于这个原理我们就可以写冒泡排序了为了简单起见下面的例子都是对数值

实现数组排序的算法很多,其中冒泡算法是比较简单的
冒泡的基本原理是相邻的两个数进行比较,按照排序的条件进行互换,例如对数值从小到大排序,
随着不断的互换,最大的那个值会慢慢冒泡到数组的末端
基于这个原理我们就可以写冒泡排序了

为了简单起见下面的例子都是对数值数组进行从小到大排序,先模拟一个20个字符的数组

function getRandomArr(n) {
  let arr = [];
  for (let i = 0; i < n; i++) {
    arr.push(~~(Math.random() * 100));
  }
  return arr
}
let randomArr = getRandomArr(20);

第一种冒泡算法
从原理可知,冒泡算法最少是需要2层循环的,当其中一个数值冒泡到末端时,这个数值下次就不需要参与循环了,这样循环的范围就会慢慢缩小,最后数组完成排序

function bubbleSort(arr) {
  let len = arr.length;
  let temp;
  let i = len - 1;
  while(i > 0) {
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
    i--;//不断缩小范围
  }
  return arr;
}
console.log(randomArr)//[ 93, 72, 29, 17, 82, 26, 56, 71, 35, 48, 37, 42, 3, 11, 33, 66, 81, 53, 59, 53 ]
console.log("bubbleSort", bubbleSort(randomArr.concat()));//bubbleSort [ 3, 11, 17, 26, 29, 33, 35, 37, 42, 48, 53, 53, 56, 59, 66, 71, 72, 81, 82, 93 ]

在冒泡的过程中,我们可以发现,如果数组后面部分已经排好序了,也就是不用再交换双方的位置时,只要记录好最后一次交换的位置,就有很大的可能缩小下次循环的范围,这样就能提高冒泡的性能(这只是猜想)
第二种冒泡算法

function bubbleSort2(arr) { 
  let len = arr.length;
  let i = len - 1;
  let temp;
  let pos;//用来记录位置的
  while (i > 0) {
    pos = 0;//初始为0如果数组一开始已经排好序了,那么就可以很快终止冒泡
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        pos = j;
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
    i = pos;
  }
  return arr;
}
console.log(randomArr)//[47, 31, 85, 65, 44, 56, 54, 5, 67, 44, 76, 13, 90, 12, 83, 72, 2, 69, 58, 60]
console.log("bubbleSort2", bubbleSort2(randomArr.concat()));//bubbleSort2 [2, 5, 12, 13, 31, 44, 44, 47, 54, 56, 58, 60, 65, 67, 69, 72, 76, 83, 85, 90]

其实对于第一种循环,是从左到右进行冒泡,我们也可以从右到左冒泡,但是从右到左的方法和第一种基本就一样了,但是我们可以在内层循环中实现先向左冒泡,再向右冒泡
第三种冒泡方法

function bubbleSort3(arr) {
  let len = arr.length;
  let low = 0;
  let higth = len - 1;
  let temp;
  while (low < higth) {
    for (let j = low; j < higth; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
    higth--;
    for (let j = higth; j > low; j--) {
      if (arr[j] < arr[j - 1]) {
        temp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = temp;
      }
    }
    low++;
  }
  return arr;
}
console.log(randomArr)//[40, 78, 16, 97, 38, 27, 66, 44, 45, 31, 12, 1, 99, 68, 36, 42, 40, 54, 6, 42]
console.log("bubbleSort3", bubbleSort3(randomArr.concat()));//bubbleSort3 [1, 6, 12, 16, 27, 31, 36, 38, 40, 40, 42, 42, 44, 45, 54, 66, 68, 78, 97, 99]

最后可以结合第三种和第二种方法
第四种冒泡的方法

function bubbleSort4(arr) { 
  let len = arr.length;
  let low = 0;
  let higth = len - 1;
  let temp;
  while (low < higth) {
    let hPos = 0;
    let lPos = higth;
    for (let j = low; j < higth; j++) {
      if (arr[j] > arr[j + 1]) {
        hpos = j;
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
    heigth = hPos;
    for (let j = higth; j > low; j--) {
      if (arr[j] < arr[j - 1]) {
        lPos = j;
        temp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = temp;
      }
    }
    low = lPos;
  }
  return arr;
}
console.log(randomArr)//[40, 78, 16, 97, 38, 27, 66, 44, 45, 31, 12, 1, 99, 68, 36, 42, 40, 54, 6, 42]
console.log("bubbleSort4", bubbleSort4(randomArr.concat()));//[1, 6, 12, 16, 27, 31, 36, 38, 40, 40, 42, 42, 44, 45, 54, 66, 68, 78, 97, 99]

下面对这4种方法在chrome控制台下进行一个简单的性能测试

var randomArr = getRandomArr(10000);
console.time("1");
bubbleSort(randomArr.concat());
console.timeEnd("1");
console.time("2");
bubbleSort2(randomArr.concat());
console.timeEnd("2");
console.time("3");
bubbleSort3(randomArr.concat());
console.timeEnd("3");
console.time("4");
bubbleSort4(randomArr.concat());
console.timeEnd("4");
VM371:4 1: 329.705ms
VM371:7 2: 379.501ms
VM371:10 3: 310.843ms
VM371:13 4: 306.847ms

在经过多次测试发现一个有趣的现象执行最快的是第4种方法,最慢的是第2种,没错最慢的是我认为可以提高性能的第2种方法,这就相当尴尬了,不知道有哪位小伙伴可以解释一下

idc机房托管云服务器最简单的排序算法 java中排序实现的 js冒泡排序 java三种排序算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/113146.html

js数值排序中冒泡算法的4种简单实现

摘要：实现数组排序的算法很多其中冒泡算法是比较简单的冒泡的基本原理是相邻的两个数进行比较按照排序的条件进行互换例如对数值从小到大排序随着不断的互换最大的那个值会慢慢冒泡到数组的末端基于这个原理我们就可以写冒泡排序了为了简单起见下面的例子都是对数值实现数组排序的算法很多,其中冒泡算法是比较简单的冒泡的基本原理是相邻的两个数进行比较,按照排序的条件进行互换,例如对数值从小到大排序,随着不断的互...

wean 2019-08-22 16:44 评论0 收藏0
js数值排序中冒泡算法的4种简单实现

摘要：实现数组排序的算法很多其中冒泡算法是比较简单的冒泡的基本原理是相邻的两个数进行比较按照排序的条件进行互换例如对数值从小到大排序随着不断的互换最大的那个值会慢慢冒泡到数组的末端基于这个原理我们就可以写冒泡排序了为了简单起见下面的例子都是对数值实现数组排序的算法很多,其中冒泡算法是比较简单的冒泡的基本原理是相邻的两个数进行比较,按照排序的条件进行互换,例如对数值从小到大排序,随着不断的互...

zzzmh 2019-08-02 10:18 评论0 收藏0
Github标星2w+，热榜第一，如何用Python实现所有算法

摘要：归并排序归并排序，或，是创建在归并操作上的一种有效的排序算法，效率为大符号。以此类推，直到所有元素均排序完毕。与快速排序一样都由托尼霍尔提出的，因而也被称为霍尔选择算法。 showImg(https://segmentfault.com/img/remote/1460000019096360);编译：周素云、蒋宝尚学会了Python基础知识，想进阶一下，那就来点算法吧！毕竟编程语言只...

zxhaaa 2019-07-31 10:23 评论0 收藏0
✨✨[数据结构]——最经典的七大排序（超详细近两万字教程，你值得拥有）✨✨

文章目录一，插入排序1，直接插入排序（1）基本思想（2）主要步骤（3）代码实现（4）性能分析 2，希尔排序(1) 基本思想(2) 主要步骤(3) 代码实现(4) 性能分析二，选择排序1，直接选择排序（1）基本思想（2）主要步骤（3）代码实现（4）性能分析 2，堆排序（1）基本思想&主要步骤（2）大堆和小堆（3）父子结点（3）主要步骤（4）向下调整法（5）特别注意（6）代码实现（7...

antyiwei 2021-10-08 10:04 评论0 收藏0
一些前端算法詳解 --- (不定时更新)

摘要：也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因於年提出而得名。前言因為比较随心所欲,所以我不按难度分享算法,所以你们会看到有时候顺序有变化,因為我发表的时候会按照难度修改下位置,尽量让你们看的时候能从简单开始,以后每次更新都加个更新时间好了,让你们知道我进度.新增计时函数直观对比效率并且因為资料比较杂,很多都是我个人理解说法,如果有发...

Baaaan 2019-08-26 10:35 评论0 收藏0