冒泡排序

1. 冒泡排序的思想：
   1. 从头开始，比较相邻的两个元素，若第一个比第二个大，则交换他们
   2. 一轮比较结束了之后
   3. 重新从头开始再次循环一遍

冒泡排序的实现

function bubbleSort(nums) {
  // 临时变量用来临时保存两个值交换过程中的一个值
  let temp;
  // 外层比较次数为元素个数
  for (let i = 0; i < nums.length; i++) {
    // 比较的次数为元素数量 - 1
    for (let j = 0; j < nums.length - 1; j++) {
      if (nums[j] > nums[j + 1]) {
        temp = nums[j + 1];
        nums[j + 1] = nums[j];
        nums[j] = temp;
      }
    }
  }
  return nums;
}
// let arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1];
// console.log(bubbleSort(arr));
function createArr(n) {
  let arr = [];
  for (let i = n; i > 0; i--) {
    arr.push(i);
  }
  return arr;
}
let arr = createArr(10000);
console.log(bubbleSort(arr));

比较过程

冒泡算法的改进

如上图所示：虽然经过第一轮比较之后，5已经是数组中最大的元素且位置已经在最后面，但是之后的每一轮比较还是把5给加上了

1. 改进策略：每一轮都相较上一轮减少一次无用的比较

function bubbleSort(nums) {
  let temp;
  for (let i = 0; i < nums.length; i++) {
    // 减少每次重复比较的次数
    for (let j = 0; j < nums.length - i - 1; j++) {
      if (nums[j] > nums[j + 1]) {
        temp = nums[j + 1];
        nums[j + 1] = nums[j];
        nums[j] = temp;
      }
    }
  }
  return nums;
}