(冒泡排序的正确性)冒泡排序是一种流行但低效的排序算法，它的作用是反复交换相邻的为按次序排列的元素。
BubbleSort(A) 1 for (int i = 1; i < A.Length; i++) 2 for (int j = A.Length; j > i; j--) 3 if (A[j] < A[j - 1]) 4 exchange(A[j-1],A[j]);
a.假设A'表示BubbleSort(A)的输出。为了证明BubbleSort正确，我们必须证明它将终止并且有：
A'[1]<=A'[2]<=......<=A'[n] //不等式(2.3)
为了证明BubbleSort确实完成了排序，我们还需要证明什么？下面两部分将证明不等式(2.3)。
b.为内循环精确的说明一个循环不变式，并证明该循环不变式成立。
c.使用(b)部分证明的循环不变式的终止条件，为外循环说明一个循环不变式，该不变式将使你能证明不等式(2.3)。
d.冒泡排序的最坏情况运行时间是多少？与插入排序的运行时间相比，其性能如何？
答：
b.内循环将找出A[i...n]中最小元素，并赋值给A[i]。
循环不变式证明如下：
初始化：当j=n时，if(A[n]<A[n-1]) exchange(A[n],A[n-1]);推出A[n-1]为A[n-1...n]中最小的元素。
保持：非形式化地，第2-4行将A[j-1]和A[j]比较，将较小值的元素赋给A[j-1]，当执行j--后，上次一次A[j-1]为该次的A[j]，再次与前一个元素比较，
并将较小值的元素赋值给A[j-2]。当j=k时，有A[k-1]为A[k-1...n]中的最小的元素。则当j=k+1时，有A[k]为A[k...n]中的最小元素。
终止：当j=i+1时循环终止，此时有A[i]为A[i...n]中的最小的元素。
c.外循环将A[1...i]排列有序。
初始化：i=1时，内循环将找出A[1...n]中的最小值，并赋值给A[1]。A[1]仅有一个元素，故A[1]已有序。
保持：如果i=k时，A[1...k]已有序（即：A'[1]<=A'[2]<=...A'<=[k]）。
则当i=k+1时，内循环将找出A[k+1...n]中最小的元素，并赋值给A[k+1]。故此时有A'[1]<=A'[2]<=...A'<=[k]<=A'[k+1]，即A[1...k+1]已有序。
终止：当i=n-1时，有A'[1]<=A'[2]<=...<=A'[n-1]，而A'[n-1]是A[n-1]与A[n]中较小者，故定有A'[n-1]<=A'[n]。
d.T(n)=(n-1)c1+∑i(n+1-i)c2+∑i(n-i)(c3+c4) （其中i为1到n-1）
=an2+bn+c
与插入排序Θ(n2)运行时间一样。