首页 > 其他分享 >js 冒泡排序

js 冒泡排序

时间:2023-10-17 16:07:53浏览次数:45  
标签:arr temp 元素 冒泡排序 js 算法 数组 排序

1.冒泡排序

人们开始学习排序算法时,通常都先学冒泡算法,因为它在所有排序算法中最简单。然而,从运行时间的角度来看,冒泡排序是最差的一个。冒泡排序比较所有相邻的两个项,如果第一个比第二个大,则交换它们。元素项向上移动至正确的顺序,就好像气泡升至表面一样,冒泡排序因此得名。

编码思路:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
  5. 之所以叫冒泡排序,每一轮两两比较之后,都会冒出一个本轮最大的数,将其移动到本轮尾部。

代码:

// 冒泡排序
function bubbleSort(arr) {
  // 循环次数
  for (let i = 1; i < arr.length; i++) {
    // 比较
    for (let j = 0; j < arr.length - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 交换位置
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

2.选择排序

选择排序算法是一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值并将其放置在第一位,接着找到第二小的值并将其放在第二位,以此类推。如此往复,直到将整个数组排序。

编码思路

js  冒泡排序_排序算法

代码:

// 选择排序
function selectSort(arr) {
  // 循环次数
  for (let i = 0; i < arr.length - 1; i++) {
    // 假设一个最小值的下标
    let minIndex = i;
    // 通过一轮比较出一个最小值下标
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[minIndex] > arr[j]) {
        // 让贤
        minIndex = j;
      }
    }
    // 交换位置(如果相同没必要交换)
    if(minIndex != i){
      let temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
}

3.插入排序

对比生活中整理扑克牌的思路,将每一张牌插入到其他已经有序的牌中的适当位置。在计算机的实现中,为了要给插入的元素腾出空间,我们需要将其余元素在插入之前向后移动一位。

它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

编码思路:

  • 从第一个元素开始,该元素可以认为已经被排序;
  • 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  • 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  • 重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置;
  • 将新元素插入到该位置后;
  • 重复步骤 2~5。

js  冒泡排序_排序算法_02

代码:

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

3.4 其它排序

排序的算法有很多种,上面的几种是我们比较容易理解的,下面再列举几种排序思想,了解即可。

3.4.1 归并排序

归并排序是一种分而治之算法。其思想是将原始数组切分成较小的数组,直到每个小数组只有一个位置,接着将小数组归并成较大的数组,直到最后只有一个排序完毕的大数组。

js  冒泡排序_冒泡排序_03

js  冒泡排序_数组_04

// 先自上往下递归拆分数组为单个元素, 再利用merge方法,自下往上合并元素返回结果
function mergeSort(arr) {
    var len = arr.length;
    if (len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
    left = arr.slice(0, middle),
    right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    var result = [];
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    while (left.length){
        result.push(left.shift());
    }
    while (right.length){
        result.push(right.shift());
    }
    return result;
}

3.4.2 快速排序

和归并排序一样,快速排序也使用分而治之的方法,将原始数组分为较小的数组(但它没有像归并排序那样将它们分割开)。

(1) 首先,从数组中选择一个值作为主元(pivot),也就是数组中间的那个值。

(2) 创建两个指针(引用),左边一个指向数组第一个值,右边一个指向数组最后一个值。移动左指针直到我们找到一个比主元大的值,接着,移动右指针直到找到一个比主元小的值,然后交换它们,重复这个过程,直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前,而比主元大的值都排在主元之后。这一步叫作划分(partition)操作。

(3) 接着,算法对划分后的小数组(较主元小的值组成的子数组,以及较主元大的值组成的子数组)重复之前的两个步骤,直至数组已完全排序。

js  冒泡排序_排序算法_05

3.4.3 计数排序

分布式排序使用已组织好的辅助数据结构(称为桶),然后进行合并,得到排好序的数组。计数排序使用一个用来存储每个元素在原始数组中出现次数的临时数组。在所有元素都计数完成后,临时数组已排好序并可迭代以构建排序后的结果数组。它是用来排序整数的优秀算法(它是一个整数排序算法),时间复杂度为O(n+k),其中k是临时计数数组的大小;但是,它确实需要更多的内存来存放临时数组。

js  冒泡排序_冒泡排序_06

3.4.4 桶排序

桶排序(也被称为箱排序)也是分布式排序算法,它将元素分为不同的桶(较小的数组),再使用一个简单的排序算法,例如插入排序(用来排序小数组的不错的算法),来对每个桶进行排序。然后,它将所有的桶合并为结果数组。

js  冒泡排序_排序算法_07

3.4.5 基数排序

基数排序也是一个分布式排序算法,它根据数字的有效位或基数(这也是它为什么叫基数排序)将整数分布到桶中。基数是基于数组中值的记数制的。比如,对于十进制数,使用的基数是10。因此,算法将会使用10个桶用来分布元素并且首先基于个位数字进行排序,然后基于十位数字,然后基于百位数字,以此类推。

js  冒泡排序_排序算法_08


标签:arr,temp,元素,冒泡排序,js,算法,数组,排序
From: https://blog.51cto.com/u_16248220/7904756

相关文章

  • JSVC简介
    JSVC简介及原理-掘金(juejin.cn)jsvc可以理解为类unix系统下的启动并守护java进程的可执行程序,属于ApacheCommonsDaemon项目。包括一下方法:voidinit(String[]arguments):Hereopenconfigurationfiles,createatracefile,createServerSockets,Threadsvoidsta......
  • 【原型链污染】Python与Js
    【原型链污染】Python与Js一、背景最近在TSCTF的比赛题中遇到了Python的原型链污染题目,所以借此机会学习一下。说到原型链,最多的还是在Js中,所以就一并学习一下。(因为是菜鸡所以文章可能的存在一些错误,欢迎批评指正)。二、JS原型链简介原型是Js代码中对象的继承方式。其实和别的......
  • 在html中 如何 插入 js 和 css 代码 以及 如何 引用 js 和 css 文件
    在HTML中插入JavaScript和CSS代码,以及引用JavaScript和CSS文件的方法如下:插入JavaScript代码:在HTML文件中,你可以使用<script>标签来插入JavaScript代码。例如:<script>functionmyFunction(){alert("Hello,World!");}</script>引用JavaScript文件:如果你的JavaScript......
  • javaweb-jsp脚本总结笔记
    1什么是JSPjsp又叫JavaserveltPage这门技术最大的特点就是,写jsp就像是再写html但是不仅可以写静态页面,而且可以内置Java代码写出动态页面,也就是说可以为用户提供动态数据。总的来说jsp=java+HTML2.JSP快速入门2.1提供对应的驱动包2.1创建对应jsp文件2.2写对应代码......
  • React学习笔记04-JSX语法
    1.JSX语法JSX将HTML语法直接加入到JavaScript代码中,再通过翻译器转换到纯JavaScript后由浏览器执行。在实际开发中,JSX在产品打包阶段都已经编译成纯JavaScript,不会带来任何副作用,反而会让代码更加直观并易于维护。编译过程由Babel的JSX编译器实现。 2.JSX语法的......
  • 完美兼容IE,chrome,ff的设为首页、加入收藏及保存到桌面js代码
    今天给大家分享一段设为首页、收藏本站及保存到桌面的js代码,非常实用。scripttype="text/javascript"//设为首页functionSetHome(obj,url){try{obj.style.behavior=’url(#default#homepage)’;obj.setHomePage(url);}catch(e){if(window.netscape){try{netscape.security.Priv......
  • 聊聊 RXJS
    一什么是rxjs?RxJS(ReactiveExtensionsforJavaScript)是一个用于响应式编程的JavaScript库。它通过使用可观察对象(Observables)和操作符(Operators)来处理异步和事件驱动的代码。什么是响应式编程?程序的输入可以被当成一个数据流,例如excel表格的累加。响应式编程世界里知名度......
  • js Promise、generator、async/await
    1.Promise的出现是为了解决ajax回调地狱的问题,但是Promise的链式调用看起来也不太美观。2.generator的出现就是为了让异步流程看起来更直观。3.然而generator在定义的时候是直观的,在执行的时候又会面临回调地狱的问题,所以async/await应运而生,async/await可以直接......
  • 冒泡排序算法(Bubble Sort)—经典排序算法
    导言冒泡排序是最基本、最简单的排序算法之一,它通过多次遍历待排序的数组或列表,依次比较相邻的元素并交换位置,使得较大(或较小)的元素逐渐“浮”到数组的一端。原理分析冒泡排序算法通过多次遍历待排序的数组或列表,依次比较相邻的元素并交换位置,使得较大(或较小)的元素逐渐“浮”到数组......
  • nodejs和nginx配置
    用的是express模板。下载的是阿里云Nginx证书。配完nginx.conf,可以用nginx-t;检查一下,只要提示isok和successful就行,然后重启用sudoservicenginxreload;如果提示‘Redirectingto/bin/systemctlreloadnginx.service’,没有关系。重点证书不仅要放在Nginx里,项目也是要......