5

我和朋友争论了以下两种算法的真正冒泡排序，关于哪一种更好，不说哪个是我的，我只是想听听你对这两个算法的两个问题的回答（写在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;
}           }
4

3 回答 3

12

第二个更接近真实的。所有比较都应该在相邻元素之间进行。

但真正的冒泡排序会采用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);
}
于 2010-12-03T17:06:41.927 回答
1

问题 #2 的答案：两者都不是“更好”。两者都是 O(n^2) 排序算法（这很糟糕）。除了介绍排序算法，冒泡排序没什么用。

于 2010-12-03T19:46:38.427 回答
1

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

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 之前的元素已经排序，所以没有必要在它们上浪费时间。

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

于 2010-12-03T17:10:26.820 回答