算法导论习题解答 2-2

•2-2 冒泡排序算法的正确性证明
伪代码：
BUBBLESORT(A)
1、 for i <- 1 to Length[A]
2、      do for j <- 1 to Length[A]downto i+1
3、                do if A[j] < A[j-1]
4、                      then exchange A[j] <-> A[j-1]

证明：令n=Length[A]
（1）、对第2~4行的for循环，循环不变式是A[j]是子数组A[j…n]中的最小值，且子数组中的元素并未改变。
初始化：开始时，j=n，子数组中只包含A[n]，故循环不变式成立；
保持：假设对于任意的一个j，使得A[j]是子数组A[j…n]中的最小值，在下一轮循环中，若A[j] < A[j-1]，则A[j]和A[j-1]交换。使得A[j-1]是子数组A[j-1…n]中的最小值，循环不变式依然成立；
终止：循环结束时j=i，A[j]是子数组A[j…n]中的最小值，且子数组中的元素并未改变。
（2）、对于1~4行的for循环，循环不变式是每次循环前，A[1…i-1]中包含了整个数组中前i-1小的排好序的元素，而A[i…n]中包含剩下的元素。
初始化：第一次循环前i=1，子数组为空，循环不变式成立；
保持：假设对于任意一个i，使得A[1…i-1]中包含了整个数组中前i-1小的排好序的元素，而A[i…n]中包含剩下的元素，则内层循环保证了A[i]是子数组A[i…n]中的最小元素，则A[1…i]中包含了整个数组中前i小的排好序的元素，而A[i+1…n]中包含剩下的元素。循环不变式成立。
终止：循环结束时i=n+1，则A[1…n]中包含了整个数组中前n小的排好序的元素，即数组有序。
综上：冒泡排序是正确的。