前端-冒泡排序 (交换排序)

1. 冒泡排序 (交换排序)

   • 稳定性: 稳定

   • 时间复杂度: O(n^2)
     每一次排序, 将最小的值往前移动到最终的位置

   • 比较次数: n(n-1)/2

   • 移动次数: 3n(n-1)/2 (每次比较都必须进行交换元素, 需要移动三次)
         每一趟排序必定有一个元素放置到了其最终的位置上面

function BubbleSort(arr) {
  const len = arr.length;
  let i, j, flag;
  // i其实可以看成是排序的次数
  for (i = 0; i < len; i++) {
    flag = false; // 表示上一次的循环过程中 是否有交换位置的操作, 没有的话, 表示已经完成好了所有的排序
    // 从后往前面进行排序
    for (j = len - 1; j > i; j--) {
      if (arr[j - 1] > arr[j]) { // 前面的元素大于后面的 则交换位置, 把小的元素往前面移动
        flag = true;
        // swap(arr, j-1, j)
        temp = arr[j - 1];
        arr[j - 1] = arr[j];
        arr[j] = temp;
      }
    }
    if (!flag) {
      return;
    }
  }
}

const a = [5, 2, 4, 3, 8, 6, 9, 0, 1, 7];
BubbleSort(a);
console.log(a);