排序算法1-冒泡排序

冒泡排序

• 平均时间复杂度:O(n^2)
• 最好情况:O(n)
• 最坏情况:O(n^2)
• 空间复杂度:O(1)
• 排序方式:In-place
• 稳定性:稳定

算法步骤:
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

function bubbleSort(arr) {
  let len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

改进
优化1 优化外层循环当内层循环没有交换发生时说明已经排序完成
优化2 记录下内层最后一次交换的位置,因为在这之后没有发生交换说明后面已经排好序了

function bubbleSort(arr) {
  let len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    let bool = true;
    let lastJ = 0;
    for (let j = 0; j < len - 1 - lastJ; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        bool = false;
        lastJ = j;
      }
    }
    if (bool) return;
    console.log(arr);
  }
}