（冒泡排序的正确性）冒泡排序是一种流行但低效的排序算法，它的作用是反复交换相邻的未按次序排列的元素。
BUBBLESORT(A)
1 for i=1 to A.length-1 2 for j=A.length downto i+1 3 if A[j]<A[j-1] 4 exchangeA[j] with A[j-1]
a.假设A'表示BUBBLESORT(A)的输出。为了证明BUBBLESORT正确，我们必须证明它将终止并且有：
其中n=A.length。为了证明BUBBLESORT确实完成了排序，我们还需要证明什么？
下面两部分将证明上述不等式。
b.为2~4行的for循环精确地说明一个循环不变式，并证明该循环不变式不等式成立。你的证明应该使用下面的循环不等式证明的结构。
c.使用（b）部分证明的循环不等式的终止条件，为第1~4行的for 循环说明一个循环不变式，该不变式将使你能证明上述不等式、你的证明应该使用下面的循环不等式证明的结构。
d.冒泡排序的最坏情况运行时间是多少？与插入排序的运行时间相比，其性能如何？
