JavaScript排序——冒泡法排序

什么是冒泡法排序

冒泡法排序（升序的情况）就是一组无序的数，比较相邻的数，如果前面的数大于后面的数，交换位置，第一轮会得出一个最大的，冒泡到最右边；第二次第二大的数冒泡到右边第二个位置；以此类推，直到最后一次得到有序的序列。

最一般的代码，这个代码最容易被想到

/**
 * @desc 冒泡法排序（升序排序）
 * @param {Array} arr 要被排序的数组
 */
var bubbleSort= function(arr){
  // 边界情况
  if(arr.length <= 1) return arr
  // 循环次数，只需要循环元素个数-1次就可以排完
  for(let i=arr.length-1, tmp; i>0 ;i--){
    // 每次循环
    for(let j=0; j<i; j++){
      tmp = arr[j]
      // 如果前面的数字比后面的大，就要交换
      if(arr[j] > arr[j+1]){
        arr[j] = arr[j+1]
        arr[j+1] = tmp
      }
    }
  }
  return arr
}

时间复杂度和空间复杂度

平均时间复杂度：O(n^2)
最好情况：O(n)
最坏情况：O(n^2)
空间复杂度：O(1)
稳定性：稳定

咋算出来的时间复杂度：
time = (n-1)+(n-2)+(n-3)+.....+2+1 = n*(n-1)/2
所以时间复杂度是O(n^2)

冒泡排序时间复杂度还是很高的，对于大量数据时，最好不要用

优化，这里贴出从最笨到最优化的情况

/**
 * @description 数组冒泡法从小到大排序
 * @param {Array} arr 一个乱序数组
 * @return 排好序的数组
 */

let arr = [4, 3, 2, 1];
let arr1 = [1,2,3,4,5];

// 最原始
function bubbleSort1(arr) {
  let max = arr.length - 1;
  for (let j = 0; j < max; j++) {
    console.log("第" + (j + 1) + "次循环：")
    for (let i = 0; i < max; i++) {
      if (arr[i] > arr[i + 1]) {
        let temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
      }
      console.log(arr)
    }
  }
  // return arr
}


// 优化1：每次循环，冒泡到最后的那个都不用再进行排序了。
function bubbleSort2 (arr) {
  // 边界情况
  if (arr.length <= 1) return arr
  // 循环次数
  for (let i = arr.length - 1, tmp; i > 0; i--) {
    console.log("第" + (arr.length-i) + "次循环：")
    // 每次循环
    for (let j = 0; j < i; j++) {
      tmp = arr[j]
      // 如果前面的数字比后面的大，就要交换
      if (arr[j] > arr[j + 1]) {
        arr[j] = arr[j + 1]
        arr[j + 1] = tmp
      }
      console.log(arr)
    }
  }
  // return arr
}

// 优化2：如果不再交换了，就说明已经是最优的了，就不必再循环了
function bubbleSort3(arr) {
  let max = arr.length - 1;
  let temp = [];
  for (let j = 0; j < max; j++) { // 第j轮循环
    console.log("第" + (j + 1) + "次循环：")
    let done = true;        // 优化1：如果不再交换了，就说明已经是最优的了，就不必再循环了
    for (let i = 0; i < max - j; i++) { // 每轮训话具体的操作
      if (arr[i] > arr[i + 1]) {  // 要交换
        temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        done = false;
      }
      console.log(arr)
    }
    if (done) break; // 跳出循环
  }
  // return arr
}

// 优化3：界定有序边界值
function bubbleSort4(arr) {
  let sortBorder = arr.length - 1;
  let temp = [];
  let lastChangeIndex = 0;
  for (let j = 0; j < arr.length; j++) {
    console.log("第" + (j + 1) + "次循环：")
    let done = true;
    for (let i = 0; i < sortBorder; i++) {
      if (arr[i] > arr[i + 1]) {
        temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        done = false;
        lastChangeIndex = i;
      }
      console.log(arr)
    }
    sortBorder = lastChangeIndex;
    if (done) break;
  }
  // return arr
}