哪一个才是真正的冒泡排序算法，哪一个更好？

Question

我和一个朋友就以下两个算法的真正冒泡排序及哪一个更好进行了争论，没有提到哪一个是我的，我只想听听你们关于这两个问题的答案（用c++编写）

1-哪一个是真正的冒泡排序？
2-哪一个更好？

以下是这两个算法：

// Number one :
void BubbleSort(int Arr[], int size)
{   for (int i=0;i<size-1;i++)
        for (int j=i+1;j<size;j++)
            if (Arr[i]>Arr[j])
            {   int temp = Arr[i];
                Arr[i] = Arr[j];
                Arr[j] = temp;
}           }

// Number two : 
void BubbleSort(int Arr[], int size)
{   for (int i=0;i<size-1;i++)
        for (int j=0;j<size-1;j++)
            if (Arr[j]>Arr[j+1])
            {   int temp = Arr[j];
                Arr[j] = Arr[j+1];
                Arr[j+1] = temp;
}           }

- Tamer Shlash

---

需要注意的是，冒泡排序在任何生产代码中都不应该被使用，因为与其他基于比较的排序算法（如插入排序）相比，它表现得非常糟糕。插入排序同样易于实现，但在几乎所有情况下（如果不是全部），都能胜过冒泡排序。我甚至认为，现在不应该再教授冒泡排序了。 - helpermethod

Python在走廊的尽头，向右第二个门。说真的：使用C缩进；不要掩饰它。 - pmg

Answer 1

第二个版本更接近实际的冒泡排序。所有比较都应该是相邻元素之间进行。

但是真正的冒泡排序应该使用一个 while 循环而不是外部的 for 循环，while 循环只有在上一次通过交换了元素后才会再次执行，就像这样:

void BubbleSort(int Arr[], int size) 
{   
    bool swapped;
    do {
        swapped = false;
        for (int j=0;j<size-1;j++)
            if (Arr[j]>Arr[j+1]) {
                int temp = Arr[j];
                Arr[j] = Arr[j+1];
                Arr[j+1] = temp;
                swapped = true;
            }
    } while (swapped);
}

- Steve Blackwell

---

每次循环后，我认为你需要将“swapped”重新设置为false，对吗？ - Paul R

Answer 2

问题2的答案是：两者都不是“更好”的选择。它们都是O(n^2)的排序算法（非常糟糕）。除了作为排序算法的入门之外，冒泡排序毫无用处。

- Zac Howland

Answer 3

嵌套循环冒泡排序的伪代码如下：

procedure bubbleSort( A : list of sortable items ) 
  n := length(A)-1
  for(i=0; i<= n; i++) 
     for(j=n; j>i; j--) 
        if A[j-1] > A[j] then
           swap (A[j-1], A[j])
        end if
     end for
  end for
end procedure

这意味着第一个方法更接近最优解，因为内部循环仅迭代 i 后的元素。而你展示的第二种方法有一个内部循环，它遍历了所有元素，即使在 i 之前的元素已经排序好了，所以没有必要浪费时间在它们上面。

这意味着第一个方法也更好。

- Alain

---

但在他的第一种方法中，他比较的是Arr[i]和Arr[j]，而不是Arr[j-1]和Arr[j]。 - Steve Blackwell