js 冒泡排序

太过爱你忘了你带给我的痛 2021-09-20 09:14 387阅读 0赞

**冒泡排序**

每次遍历时，从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾！ 采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。重复此操作，直到整个数列都有序为止

function sortArr(arr,n){
            for( let i=0; i<n;i++){
        //n
                // 一共比较n-1轮
                for(let j=0; j<n;j++){
        //n*n
                    if(arr[j] > arr[j+1]){
                        let a = arr[j],
                            b = arr[j+1];
                        arr[j] = b;
                        arr[j+1] = a;
                        // console.log('change')//发生交换的次数 9
                    }
                    // console.log('compare')//比较的次数 64
                }
            }
        }

冒泡排序的时间复杂度为O(N^2)，即数列长度的平方次数

发生交换的次数根据不同数列的情况不同最终的次数也是不一样的，但是比较的次数却是固定的，这样就显得效率不高

进阶版，添加一个标记，在排序完成之后停止比较，以防止没有意义的交换， 提高效率

function betterSortArr(arr,n){
            for( let i=0; i<n;i++){
                let isFlag = false;
                // 一共比较n-1轮
                for(let j=0; j<n;j++){
                    if(arr[j] > arr[j+1]){
                        // let a = arr[j],
                        //     b = arr[j+1];
                        // arr[j] = b;
                        // arr[j+1] = a;
                        arr[j] = arr.splice(j+1,1,arr[j])[0]
                        isFlag = true;
                        // console.log('change')//发生交换的次数 9
                    }
                    // console.log('compare')//比较的次数 40
                    // 次数少了24次
                }
                if(!isFlag){
                    break;
                }
            }
        }

如果一趟遍历中发生了交换，则标记为true，否则为false。如果某一趟没有发生交换，说明排序已经完成！

let arr = [45,21,48,65,98,44,87,55,89,98]
    let length = arr.length
    sortArr(arr,length)
    betterSortArr(arr,length)

转载于:https://www.cnblogs.com/qisimx/p/10541397.html

发表评论取消回复

表情：

评论列表（有 0 条评论，387人围观）

还没有评论，来说两句吧...

相关阅读

相关 js冒泡排序

接看例子： var arr = [12, 23, 13, 35, 46, 67, 89, 97, 32]; for (var i = 0; i ...

向右看齐/ 2024年04月18日 19:08/ 0 赞/ 75 阅读

相关 js冒泡排序

上代码： const arr = [ 10, 2, 4, 6, 0, 4, 7, 8 ] const LEN = arr.length for (le

客官°小女子只卖身不卖艺/ 2023年05月28日 12:54/ 0 赞/ 12 阅读

相关 js 冒泡排序

function bubleSort(arra)\{ var temp; for(var i=0;i<arra.length;i++

古城微笑少年丶/ 2023年02月19日 07:28/ 0 赞/ 11 阅读

相关 js冒泡排序

/ 冒泡排序：通过前后数据的大小对比将小的放在前面，大的放在后面 / var list = [9, 5, 3, 7, 2, 1] for

本是古典何须时尚/ 2022年12月31日 11:27/ 0 赞/ 132 阅读

相关 js冒泡排序原理

<!DOCTYPE html> <html> <head lang="en"> <meta charset="UTF-8">

本是古典何须时尚/ 2022年07月13日 23:18/ 0 赞/ 190 阅读

相关 js冒泡排序

说明时间复杂度指的是一个算法执行所耗费的时间空间复杂度指运行完一个程序所需内存的大小稳定指，如果a=b,a在b的前面，排序后a仍然在b的前面

太过爱你忘了你带给我的痛/ 2022年06月18日 09:18/ 0 赞/ 200 阅读

相关 js冒泡排序，简单的冒泡排序

<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8">

灰太狼/ 2022年02月02日 16:41/ 0 赞/ 244 阅读

相关 js冒泡排序

var i; var j; var k=""; var g=0; cars=news Array() var num = Mat

系统管理员/ 2022年01月09日 13:27/ 0 赞/ 240 阅读

相关 js 冒泡排序

冒泡排序每次遍历时，从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾！采用相同的方法再次遍历时，第二大

叁歲伎倆/ 2021年12月23日 04:45/ 0 赞/ 288 阅读

相关 js 冒泡排序

冒泡排序每次遍历时，从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾！采用相同的方法再次遍历时，第二大

太过爱你忘了你带给我的痛/ 2021年09月20日 09:14/ 0 赞/ 388 阅读