js 冒泡排序

叁歲伎倆 2021-12-23 04:45 363阅读 0赞

冒泡排序

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

  1. function sortArr(arr,n){
  2.         for( let i=0; i<n;i++){
  3.     //n
  4.             // 一共比较n-1轮
  5.             for(let j=0; j<n;j++){
  6.     //n*n
  7.                 if(arr[j] > arr[j+1]){
  8.                     let a = arr[j],
  9.                         b = arr[j+1];
  10.                     arr[j] = b;
  11.                     arr[j+1] = a;
  12.                     // console.log('change')//发生交换的次数 9
  13.                 }
  14.                 // console.log('compare')//比较的次数 64
  15.             }
  16.         }
  17.     }

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

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

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

  1. function betterSortArr(arr,n){
  2.         for( let i=0; i<n;i++){
  3.             let isFlag = false;
  4.             // 一共比较n-1轮
  5.             for(let j=0; j<n;j++){
  6.                 if(arr[j] > arr[j+1]){
  7.                     // let a = arr[j],
  8.                     //     b = arr[j+1];
  9.                     // arr[j] = b;
  10.                     // arr[j+1] = a;
  11.                     arr[j] = arr.splice(j+1,1,arr[j])[0]
  12.                     isFlag = true;
  13.                     // console.log('change')//发生交换的次数 9
  14.                 }
  15.                 // console.log('compare')//比较的次数 40
  16.                 // 次数少了24次
  17.             }
  18.             if(!isFlag){
  19.                 break;
  20.             }
  21.         }
  22.     }

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

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

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

发表评论

表情：
评论列表 （有 0 条评论，363人围观）

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

相关阅读

    相关 js 冒泡排序

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

    叁歲伎倆叁歲伎倆/ 0 赞/ 364 阅读

    相关 js 冒泡排序

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

    太过爱你忘了你带给我的痛太过爱你忘了你带给我的痛/ 0 赞/ 468 阅读