冒泡排序

冒泡排序的思想就是相邻交换从而将最小元素浮上来，达到“冒泡”的效果

这里我们也可以划分已排序区域和未排序区域，已经“冒泡”的就是已经排序的，我们要做的是将未排序区域中的最小元素浮上来

BUBBLE-SORT(A)
for i ← 1 to n do
 for j ← n-1 down to i do
  if A[j+1] < A[j]
   then swapped with A[j+1] and A[j]

算法正确性

循环不变式为

$A[0…i-1]$已排序

初始：该区间没有元素
维持：假设$A[0…i-1]$已排序，注意第二层循环，$j$是从$n-1$一直往$i$移动，若$j+1$比$j$小，则交换元素，因此$A[i]$一定是$A[i…n]$的最小值，因此$A[0…i]$为已排序序列，再$i$自增，循环不变式维持
终止：此时，$i=n$，$A[0…n-1]$排序完成，而$A[n]$是$A[1…n]$的最大元素，$A[1…n]$排序完成