算法学习：冒泡排序的一些思考

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。
更新于: 2021-12-19 12:57:29
冒泡排序演示

网上抄的实现

function bubbleSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len - 1; i++) {
    for (var j = 0; j < len - 1 - i; j++) {
      console.log("STD当前/下一个：", arr[j], arr[j + 1]);
      if (arr[j] > arr[j + 1]) {
        // 相邻元素两两对比
        var temp = arr[j + 1]; // 元素交换
        arr[j + 1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}

console.log(bubbleSort([4, 2, 1, 3]));

特点

升序排序，每一轮的比较会把最大的数沉到最底。

降序排序，每一轮的比较会把最小的数沉到最底。

问题分解

  1. 相隔元素
  2. 两两比较，数组交换顺序
  3. 每进行一轮有一个排好
  4. 要进行几次比较

1. 怎么表示相邻元素

// 因为要取下一个元素，所以，在平时循环的基础上，再减1
var max = arr.lenght -1;

for (var i = 0; i < max; i++) {
    var cur = arr[i];
    var next = arr[i + 1];
}

// cur: 当前元素
// next: 下一个元素

2. 交换数组元素

function swap(arr, i, j) {
  var temp = arr[j];
  arr[j] = arr[i];
  arr[i] = temp;
}

3. 一轮比较的逻辑

function bsort1(arr) {
  for (var i = 0; i < arr.length - 1; i++) {
    var cur = arr[i];
    var next = arr[i + 1];

    if (cur > next) {
      swap(arr, i, i + 1);
    }
  }
  return arr;
}

4. 要进行多少轮这种比较呢(结论: arr.length -1)

目前是简单的归纳，可能后面还要找更加可靠的证明来支持

//最多的情况，完全反序 [4,3,2,1]
//1: [3,2,1,4]
//2: [2,1,3,4]
//3: [1,2,3,4]

function bsort(arr) {
  for (var i = 0; i < arr.length - 1; i++) {
    bsort1(arr);
  }
  return arr;
}

个人实现的完整代码如下

function swap(arr, i, j) {
  var temp = arr[j];
  arr[j] = arr[i];
  arr[i] = temp;
}

function bsort1(arr, j) {
  for (var i = 0; i < arr.length - 1 - j; i++) {
    var cur = arr[i];
    var next = arr[i + 1];

    console.log("当前/下一个：", cur, next);

    if (cur > next) {
      swap(arr, i, i + 1);
    }
  }
  return arr;
}

function bsort(arr) {
  for (var i = 0; i < arr.length - 1; i++) {
    bsort1(arr, i);
  }
  return arr;
}

var arr1 = [4, 3, 2, 1];

console.log(bsort(arr1));

结论：我的方法有问题，已经修复

1. 次数过多(4,3/3/4类似这种已经循环过的，不需要再进行比较)，貌似原版也是这种实现

2. 里层循环应该受外层的影响

3. 改进版已经修改此问题

关于循环次数的问题，以 arr=[5,4,3,2,1] 为例

// 次数问题分析
function sub(arr, j) {
  for (var i = 0; i < arr.length - 1 /* - j */; i++) {
    var cur = arr[i];
    var next = arr[i + 1];

    console.log("当前/下一个：", cur, next);
  }
  return arr;
}

function main(arr) {
  for (var i = 0; i < arr.length - 1; i++) {
    sub(arr, i);
  }
  return arr;
}

var arr1 = [5, 4, 3, 2, 1];
main(arr1);
优化后的情况: 
当前/下一个： 5 4
当前/下一个： 4 3
当前/下一个： 3 2
当前/下一个： 2 1
当前/下一个： 5 4
当前/下一个： 4 3
当前/下一个： 3 2
当前/下一个： 5 4
当前/下一个： 4 3
当前/下一个： 5 4

每循环一次，减少内层一次
1: 4(外层:i=0, 内层: 0,1,2,3)
2: 3(外层:i=1, 内层: 0,1,2)
3: 2(外层:i=2, 内层: 0,1)
4: 1(外层:i=3, 内层: 0)
优化前的情况: 
5个元素：4*4=16次
当前/下一个： 5 4
当前/下一个： 4 3
当前/下一个： 3 2
当前/下一个： 2 1
当前/下一个： 5 4
当前/下一个： 4 3
当前/下一个： 3 2
当前/下一个： 2 1
当前/下一个： 5 4
当前/下一个： 4 3
当前/下一个： 3 2
当前/下一个： 2 1
当前/下一个： 5 4
当前/下一个： 4 3
当前/下一个： 3 2
当前/下一个： 2 1

循环次数(N为数组长度arr.length)

优化前： (N-1) * (N-1)

优化后：1 + 2 + 3 + …(N-1)

等差数列公式

参考