我们如何使用归纳法证明冒泡排序是正确的？我们如何选择在整个证明制定过程中遵循的不变量（这一步对我来说似乎是一项任意任务，所以如果可以更深入地解释它，我将不胜感激）？
我知道每次迭代后最大的元素总是会出现在列表的末尾，但我不知道如何使用这个事实来证明算法是正确的。
谢谢您的帮助！
问问题
1397 次
1 回答
0
我不确定这是否是你想要的，但他就是我的看法。
冒泡排序背后的想法是你通过值的向量（从左到右）。我称之为通行证。在传递过程中，值对被检查并交换为正确的顺序（右上方）。
在第一次通过期间，将达到最大值。当达到最大值时，最大值将高于它旁边的值，因此它们将被交换。这意味着 max 将成为传递中下一对的一部分。重复此过程，直到 pass 完成并且 max 位于向量的右端。
在第二次传递期间，向量中的第二高值也是如此。唯一的区别是它不会在最后与最大值交换。现在正确设置了两个最右边的值。
我每下一次传一个值就会被整理到右边。
有 N 个值和 N 个传递。这意味着在 N 次通过后，所有 N 个值都会被排序
于 2012-12-04T22:53:28.960 回答