有人可以向我解释一下关于冒泡排序这一说法背后的逻辑吗？

Question

假设我们有一个名为 A 的数组

。令 Π 为一组 (x,y) 对，其中 x,y 是 A 数组中存在的值，并且索引(x) < 。索引(y)并且x＞y。

例如，如果我们有这个数组

      3 2 9 8 3 0

，那么 (3,2) 将在 Π 中。 (3,0) 也将在 Π 中。

Π 中的所有对将如下

   { (3,2), (3,0), (8,0), (9,0),(9,3),(2,0),(8,3),(9,8) }

我希望我没有忘记一些事情

我意识到如果我们修复所有这些对，那么我们将对数组进行排序。当我说修复时，我的意思是，例如 (3,2) 使其成为 (2,3) ，而对于其他人，

我不明白的是，冒泡排序每一步修复多少对？我的老师告诉我 1，我不明白，

让我们运行冒泡排序，

 3 2 9 8 3 0
 2 3 9 8 3 0
 2 3 9 8 3 0
 2 3 8 9 3 0
 2 3 8 3 9 0
 2 3 8 3 0 9

 2 3 8 3 0 9
 2 3 8 3 0 9
 2 3 3 8 0 9
 2 3 3 0 8 9

 2 3 3 0 8 9
 2 3 3 0 8 9
 2 3 0 3 8 9

 2 3 0 3 8 9
 2 0 3 3 8 9

 0 2 3 3 8 9

是不是有一些步骤冒泡排序无法解决任何问题？那么，冒泡排序每一步最多只能修复1个点是正确答案吗？

Answer 1

在我看来，在您的示例数据集中，冒泡排序总是会“修复”一个元素，因为每个元素都是乱序的。但是，如果您将 0 移到更靠近原始列表前面的位置，那么您将生成一些已经按排序顺序的对。这些对不会被冒泡排序“修复”，在这种情况下，您可以正确地说冒泡排序可以在每个步骤上“修复”最多 1 个元素。

所以在一般情况下，你是正确的。在您的示例中使用的具体情况中，老师是正确的。

注意：我假设“步骤”是指将冒泡排序算法应用于集合中的一对数字。

Answer 2

冒泡排序涉及重复循环数组。在每次遍历数组的过程中，它都会重复交换当它碰到时无序的相邻元素。

仅当元素无序时，从一个条目到另一个条目的每一步才会交换。

每次通过数组都会修复至少一个无序对，除非没有（即，数组已经排序，并且通过没有变化的传递是完成信号）。

我怀疑你正在考虑步骤，而你的教授正在考虑传递，但无论如何他都不太正确，因为穿过整个数组的一些传递可以修复多个无序对，而最后一次传递什么也修复不了（因为没有任何东西）那时需要修复）。