java - 这是正确的冒泡排序算法吗？

Question

已关闭。此问题不符合 Stack Overflow guidelines 。目前不接受答案。

---

这个问题似乎与 help center 中定义的范围内的编程无关。 .

已关闭 9 年前。

Improve this question

我编写了以下代码来使用冒泡排序对数组值中的元素进行排序。这是正确的还是有什么遗漏？我的测试用例很好，但也许测试用例还缺少一些东西。

public void sort(ValuePair[] values) {

    ValuePair value = null;

    for (int i = 0; i < values.length; i++) {
        for (int j = 1 + i; j < values.length; j++) {
            if (values[i].getValue() > values[j].getValue()) {
                value = values[j];
                values[j] = values[i];
                values[i] = value;
            }
        }
    }
}

Answer 1

您的代码是正确的，因为它将对数组进行排序。然而，它总是需要 N*(N-1) 次遍历数组。这不是用于实现的典型算法冒泡排序。典型的算法使用带有排序测试的重复循环。这在某种程度上更有效，因为它数组排序后立即终止(考虑以排序数组开始的情况)。

阅读Wikepedia article on bubble sort它很好地证明了这一点。

冒泡排序的稍微改进的伪代码版本如下所示:

procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat
       swapped = false
       for i = 1 to n-1 inclusive do
          if A[i-1] > A[i] then
             swap(A[i-1], A[i])
             swapped = true
          end if
       end for
       n = n - 1
    until not swapped
end procedure

这里的教训是，虽然你的算法和维基百科算法都具有相同的大 O 特征，但有一个小变化它们的实现方式可能会对它们的实际性能特征产生重大影响。