•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小的排好序的元素,即数组有序。
综上:冒泡排序是正确的。
分享到:
相关推荐
算法导论习题解答算法导论习题解答算法导论习题解答算法导论习题解答算法导论习题解答
英文原版 教师手册 算法导论-习题答案-含课后习题详细解答
算法导论习题解答算法导论习题解答
NULL 博文链接:https://amazingidiot.iteye.com/blog/1127870
NULL 博文链接:https://amazingidiot.iteye.com/blog/1127865
算法导论习题解答 算法导论习题解答 算法导论习题解答
算法导论习题解答算法导论习题解答算法导论习题解答算法导论习题解答
柯尔曼-算法导论-第2版-习题解答 柯尔曼-算法导论-第2版-习题解答 柯尔曼-算法导论-第2版-习题解答 柯尔曼-算法导论-第2版-习题解答
算法导论习题解答中文版算法导论习题解答中文版算法导论习题解答中文版
算法导论习题解答,相当nice,相当完整...一个字帅
包括课本中所有伪代码java实现,部分习题,少部分思考题编程题实现
算法导论的习题的解答 算法导论习题解答,跟算法导论>>配套的习题解答,英文 就是你要找的
超经典的MIT出版的算法导论习题解答,对学习算法的朋友提供一个很好的参考。
算法导论+习题解答(第二版) 算法导论+习题解答(第二版) 算法导论+习题解答(第二版)
算法导论+每章后面的习题解答。
这个是对MIT的算法导论的习题解答。希望能够与学习这本书的读者一起交流学习
算法导论习题解答.pdf
能用代码表示的都用代码表示,不能表示的写出思路,思路都没写的就是我也做不出来