冒泡排序就是将数列中第一个关键字和第二个关键字比较，若为逆序，则交换两个关键字，继续比较第二个，第三个关键字，重复直到最后一个。这样子，数列中最大值就位于最后的位置。然后开始第二轮比较，直到 N-1 的位置。一直循环比较 N 轮，直到数列中所有的记录都排序好。冒泡排序总是从左往右遍历，并选择最大的关键字放在最左边。

图片来源：维基百科

冒泡排序是一种稳定的排序方法。
冒泡排序的平均时间复杂度为 O(n²)。
冒泡排序的空间复杂度为 O(1)。排序过程中仅需要一个元素的辅助空间用来元素的交换。

冒泡排序的伪代码：

FOR i ← 0 to length(A) - 1
  FOR j ← 0 to length(A) - i - 1
    IF A[j] > A[j+1]
      swap A[j] and A[j+1]
    END IF
  END FOR
END FOR

优化后的冒泡排序的伪代码：

REPEAT
  FOR i ← 0 to length(A) - 1
    swapped ← false
    FOR j ← 0 to length(A) - i - 1
      IF A[j] > A[j+1]
        swap A[j] and A[j+1]
        swapped ← true
      END IF
    END FOR
  END FOR
UNTIL NOT swapped

鸡尾酒排序(Cocktail Sort)

图片来源：维基百科

鸡尾酒排序是一种稳定的排序方法。
鸡尾酒排序的平均时间复杂度为 O(n²)。
鸡尾酒排序的空间复杂度为 O(1)。

鸡尾酒排序，也叫定向冒泡排序(bidirectional bubble sort)，是冒泡排序的一种变形。该算法与冒泡排序的不同之处，就是它每次遍历序列时同时从两个方向上排序。

鸡尾酒排序的伪代码：

swapped ← true
start ← 0
end ← length(A) - 1
WHILE swapped
  swapped ← false
  FOR i ← start to end - 1
    IF A[i] > A[i+1]
      swap A[i] and A[i+1]
      swapped ← true
    END IF
  END FOR
  end ← end - 1
  IF !swapped
    BREAK WHILE LOOP
  END IF
  FOR j ← end - 1 downto start
    IF A[j] > A[j+1]
      swap A[j] and A[j+1]
      swappped ← true
    ENDIF
  END FOR
  start ← start + 1
END WHILE