1

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

令 Π 是一组 (x,y) 对，其中 x,y 是存在于 A 和 index(x) < index(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个点是正确的答案吗？

4

2 回答 2

0

It looks to me that in your example dataset, bubble-sort will always "fix" exactly one element, because each element is out of order. If, however, you were to move the 0 closer to the front of the original list, then you would generate some pairs that are already in sorted order. These pairs would not be "fixed" by bubble-sort, and in such a case you would be correct in saying that bubble sort may "fix" up to 1 element on each step.

So in the general case, you are correct. In the specific case you used in your example, the teacher is correct.

Note: I am assuming that "step" refers to the application of the bubble-sort algorithm to a single pair of numbers in the set.

于 2011-12-15T23:14:18.770 回答
0

冒泡排序涉及重复循环遍历数组。在每次遍历数组期间，它会重复交换在碰到它们时出现乱序的相邻元素。

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

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

我怀疑您正在考虑步骤，而您的教授正在考虑通过，但无论如何他都不完全正确，因为通过整个阵列的某些通过可以修复多个无序对，而最后通过则无法解决任何问题（因为没有需要在那个时候修复）。

于 2011-12-15T23:32:23.060 回答