冒泡排序

简介

冒泡排序是一种流行但低效的排序算法，它的作用是反复交换相邻的未按次序排列的元素。

BUBBLESORT(A)

for i = 1 to A.length -1
  for j = A.length downto i + 1
    if A[j] < A[j - 1]
      exchange A[j] with A[j - 1]

假设$ A^{‘}$表示BUBBLESORT(A)的输出。为了证明BUBBLESORT正确，我们必须证明它将终止并且有：
$ A^{‘}[1] $

其中n=A.length。