首页 > 其他分享 >js 实现冒泡排序及优化方案

js 实现冒泡排序及优化方案

时间:2022-09-01 18:58:32浏览次数:76  
标签:count arr console log 冒泡排序 js let 优化

// 冒泡排序
// 原理就是每一轮循环,将一个最大的值放冒泡到最后
// 1.每一趟都是比较相邻两个元素,如果后一个元素大于前一个,则交换两个元素
// 2.第一趟从第一个元素开始进行交换,最后一个元素不参与交换,第二趟最后两个元素不参与交互,以此类推
function bubbleSort(arr) {
    if (arr.length < 2) {
        return arr;
    }
    // 定义 count 代表执行了趟循环
    let count = 0;
    // 冒泡排序排的趟数=数组的长度-1
    // 第一层 for 循环代表一共排序多少趟
    for (let i = 0; i < arr.length - 1; i++) {
        count++;
        // 第二层 for 循环代表每趟需要比较多少次 每趟比较的次数会减i,因为每趟会将最后排好一个元素,排了多少趟,则代表排好了几个元素
        for (let j = 0; j < arr.length - 1 - i; j++) {
            // 在大于的时候才会交换,等于的时候不交换,所以冒泡排序属于稳定排序算法,不会对相等两个元素执行交换
            // j=>左指针,j + 1=>右指针
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    console.log(`执行了${count}趟循环`);
    return arr;
}
console.log("普通冒泡排序");
console.log(bubbleSort([6, 3, 7, 8, 2, 4, 0, 1, 6, 5]));
console.log(bubbleSort([1, 2, 3, 4, 5, 6, 7, 8, 9, 9]));
// 一重优化:增加交换过的状态值,当循环一趟,没有交换过,说明数组已经是有序了,下次不需要再次循环了
function bubbleSort1(arr) {
    if (arr.length < 2) {
        return arr;
    }
    // 定义 count 代表执行了趟循环
    let count = 0;
    // 冒泡排序排的趟数=数组的长度-1
    // 第一层 for 循环代表一共排序多少趟
    for (let i = 0; i < arr.length - 1; i++) {
        count++;
        let hasSort = true;
        // 第二层 for 循环代表每趟需要比较多少次 每趟比较的次数会减i,因为每趟会将最后排好一个元素,排了多少趟,则代表排好了几个元素
        for (let j = 0; j < arr.length - 1 - i; j++) {
            // 在大于的时候才会交换,等于的时候不交换,所以冒泡排序属于稳定排序算法,不会对相等两个元素执行交换
            // j=>左指针,j + 1=>右指针
            if (arr[j] > arr[j + 1]) {
                // 只要交换过,则不是有序
                hasSort = false;
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        if (hasSort) {
            break;
        }
    }
    console.log(`执行了${count}趟循环`);
    return arr;
}
console.log("一重优化冒泡排序");
console.log(bubbleSort1([6, 3, 7, 8, 2, 4, 0, 1, 6, 5]));
console.log(bubbleSort1([1, 2, 3, 4, 5, 6, 7, 8, 9, 9]));
// 二重优化
function bubbleSort2(arr) {
    if (arr.length < 2) {
        return arr;
    }
    // 定义 count 代表执行了趟循环
    let count = 0;
    // 记录最后一次交互元素时当前位置
    let lastChangeIndex = 0;
    // 记录无序数列的右边界
    let sortBorder = arr.length - 1;
    // 冒泡排序排的趟数=数组的长度-1
    // 第一层 for 循环代表一共排序多少趟
    for (let i = 0; i < arr.length - 1; i++) {
        count++;
        let hasSort = true;
        // 第二层 for 循环代表每趟需要比较多少次 每趟比较的次数会减i,因为每趟会将最后排好一个元素,排了多少趟,则代表排好了几个元素
        for (let j = 0; j < sortBorder; j++) {
            // 在大于的时候才会交换,等于的时候不交换,所以冒泡排序属于稳定排序算法,不会对相等两个元素执行交换
            // j=>左指针,j + 1=>右指针
            if (arr[j] > arr[j + 1]) {
                // 只要交换过,则不是有序
                hasSort = false;
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                lastChangeIndex = j;
            }
            sortBorder = lastChangeIndex;
        }
        if (hasSort) {
            break;
        }
    }
    console.log(`执行了${count}趟循环`);
    return arr;
}
console.log("二重优化冒泡排序");
console.log(bubbleSort2([6, 3, 7, 8, 2, 4, 0, 1, 6, 5]));
console.log(bubbleSort2([1, 2, 3, 4, 5, 6, 7, 8, 9, 9]));

参考链接:https://blog.csdn.net/hcz666/article/details/117810787

标签:count,arr,console,log,冒泡排序,js,let,优化
From: https://www.cnblogs.com/beileixinqing/p/16647525.html

相关文章

  • C#程序优化的50种方案
    C#程序优化的50种方案码农人生C#编程欢迎围观交流​关注 58人赞同了该文章一、用属性代替可访问的字段1、.NET数据绑定只支持数据绑定,使用......
  • 人均瑞数系列,瑞数 5 代 JS 逆向分析
    声明本文章中所有内容仅供学习交流使用,不用于其他任何目的,不提供完整代码,抓包内容、敏感网址、数据接口等均已做脱敏处理,严禁用于商业用途和非法用途,否则由此产生的一切......
  • JS 事件盘点
    1.鼠标事件鼠标在元素上移动mousemove鼠标从该元素上移出mouseout鼠标移动到该元素mouseover鼠标点击(单击)click鼠标双击dbclick鼠标右击contextmenu可以配......
  • TDengine3.0计算查询引擎的优化与升级
    在8月13日的 TDengine 开发者大会上,TDengine计算引擎架构师廖浩均带来题为《TDengine3.0——全新计算查询引擎的设计》的主题演讲,详细阐述了TDengine3.0计算查......
  • 生成二维码并以图片格式下载-qrcodejs2
    1、安装qrcodejs2npminstallqrcodejs2--save2、在需要的页面引入importQRCodefrom"qrcodejs2";3、页面中使用<divid="qrcode"ref="qrcode"></div>4......
  • UE4研发手游时如何渲染与优化环境反射?
    本文介绍了四个小主题,分别是UE4Mobile端的Skylight和ReflectionCapture之间的关系,如何让ReflectionCapture采集天光,ReflectionCapture的亮度校正算法分析及在期在移动端可......
  • slam14(1) v3_3 后端优化 BA位姿图优化
      https://blog.csdn.net/heroybc/article/details/106355948 1.位姿图  当把BA优化问题中的位姿图的问题简化要怎么做?BA优化中的计算量很大很大,为了减少计......
  • Flask 学习-31.flask_jwt_extended 验证token四种方headers/cookies/json/query_stri
    前言用户携带授权token访问时,其jwt的所处位置列表,默认是在请求头部headers中验证。可以通过JWT_TOKEN_LOCATION进行全局配置,设置token是在请求头部,还是cookies,还是json,......
  • JS缓存三种方法
    1.sessionStorage:临时的会话存储只要当前的会话窗口未关闭,存储的信息就不会丢失,即便刷新了页面,或者在编辑器中更改了代码,存储的会话信息也不会丢失。2.localStor......
  • vue项目中main.js使用方法详解
    vue项目中main.js使用方法详解目录第一部分:main.js文件解析第二部分:Vue.use的作用以及什么时候使用Vue.use是什么?(官方文档)Vue.use()什么时候使用?补充:关于main.js方便小技......