介绍

冒泡排序（英语：Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢 “浮” 到数列的顶端。

原理

冒泡排序算法的运作如下：

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

复杂度

• 平均时间复杂度 $O(n^{2})$
• 最坏时间复杂度 $O(n^{2})$
• 最优时间复杂度 $O(n)$
• 空间复杂度总共 $O(n)$，需要辅助空间$O(1)$

伪代码

function bubble_sort (array, length) {
    var i, j;
    for(i from 0 to length-1){
        for(j from 0 to length-1-i){
            if (array[j] > array[j+1])
                swap(array[j], array[j+1])
        }
    }
}

动画

实现

JavaScript

/* Bubble Sort is an algorithm to sort an array. It
*  compares adjacent element and swaps their position
*  The big O on bubble sort in worst and best case is O(N^2).
*  Not efficient.
*  Somehow if the array is sorted or nearly sorted then we can optimize bubble sort by adding a flag.
*
*  In bubble sort, we keep iterating while something was swapped in
*  the previous inner-loop iteration. By swapped I mean, in the
*  inner loop iteration, we check each number if the number proceeding
*  it is greater than itself, if so we swap them.
*
*  Wikipedia: https://en.wikipedia.org/wiki/Bubble_sort
*  Animated Visual: https://www.toptal.com/developers/sorting-algorithms/bubble-sort
*/

/**
 * Using 2 for loops.
 */
function bubbleSort (items) {
  const length = items.length
  let noSwaps

  for (let i = length; i > 0; i--) {
    // flag for optimization
    noSwaps = true
    // Number of passes
    for (let j = 0; j < (i - 1); j++) {
      // Compare the adjacent positions
      if (items[j] > items[j + 1]) {
        // Swap the numbers
        [items[j], items[j + 1]] = [items[j + 1], items[j]]
        noSwaps = false
      }
    }
    if (noSwaps) {
      break
    }
  }

  return items
}

/**
 * Using a while loop and a for loop.
 */
function alternativeBubbleSort (arr) {
  let swapped = true

  while (swapped) {
    swapped = false
    for (let i = 0; i < arr.length - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]]
        swapped = true
      }
    }
  }

  return arr
}

参考

• 冒泡排序 - 维基百科，自由的百科全书 (opens new window)