为什么我的降序冒泡排序不适用于升序输入？

Question

此代码适用于大多数输入，但输入按升序排列时除外。

例如输入为 [1,2,3,4,5]，输出为 [5,1,4,2,3]，预期为 [5,4,3,2,1]

DescBubbleSort(A) 
    for i from n downto 1 do
        for j from n downto i + 1 do
            if A[j] > A[j − 1] then
                A[j] swap A[j-1]
    return A

Answer 1

你的操作顺序错了。
根据this Wiki-Entry，正确的代码是：

 for (n=A.size; n>1; --n){
    for (i=0; i<n-1; ++i){
      if (A[i] > A[i+1]){
        A.swap(i, i+1)
      }
    }
  }

编辑：

抱歉我不够详细（虽然 SO 不喜欢像“找到我的错误”这样的问题）。
无论如何：我假设你的代码是在 Pascal 中。我希望我正确地更正了您的代码如下：

for i from n downto 1 do
  for j from n downto n-i+1 do
    if A[j] > A[j-1] then
      A[j] swap A[j-1]
return A

Swift 中的相同（我测试过）：

var a = [1,2,3,4,5]
print(a) // Prints [1, 2, 3, 4, 5]
for i in stride(from: 4, through: 1, by: -1) {
  for j in stride(from: 4, through: 4-i+1, by: -1) {
    if a[j] > a[j-1] {
      a.swapAt(j, j-1)
    }
  }
}
print(a) // Prints [5, 4, 3, 2, 1]

如您所见，您的错误位于第 2 行 downto i + 1。

为什么我的降序冒泡排序不适用于升序输入？

Why does my Descending Bubble Sort not work for an input in ascending order?

sorting

bubble-sort