第 86 期(算法-排序)：经典排序算法之冒泡排序

[wingmeng]

冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

• 原理： 依次比较两个相邻的元素，将值大的元素交换到右边，然后不断重复直到没有相邻元素需要交换。
• 复杂度： 时间复杂度：O(n²)，空间复杂度：O(1)
• 稳定性： 冒泡排序是稳定的排序算法，因为可以实现值相等的元素的相对位置不变。

算法分析：

1. N 个数字要排序完成，总共进行 N-1 趟排序，每 i 趟的排序次数为 (N-i) 次，所以可以用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数；
2. 冒泡排序每进行一趟排序都会找出一个较大值，所以每一趟都会比上次少比较一次。

function bubbleSort(arr) {
  var len = arr.length;

  for (var i = 0; i < len - 1; i++) {
    for (var j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {  // 相邻元素两两对比
        var temp = arr[j + 1];

        // 元素交换
        arr[j + 1] = arr[j];
        arr[j] = temp;
      }
    }
  }

  return arr;
}