哪一个是真正的气泡类型，哪一个更好？
哪一个是真正的气泡类型，哪一个更好？
提问于 2010-12-04 01:00:30
我和一个朋友争论了下面两个算法的真实泡沫类型，关于哪个更好，没有提到哪个是我的，我只想听听你对这两个算法的回答(用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;
} }回答 3
Stack Overflow用户
回答已采纳
发布于 2010-12-04 01:06:42
第二个更接近真正的那个。所有比较都应该在相邻元素之间进行。
但真正的冒泡排序将采用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);
}Stack Overflow用户
发布于 2010-12-04 01:10:27
嵌套循环冒泡排序的伪代码是：
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之前的元素已经排序，所以不需要在它们上面浪费时间。
这意味着第一种方法也更好。
Stack Overflow用户
发布于 2010-12-04 03:46:38
问题2的答案是:两者都不是“更好”。这两种算法都是O(n^2)排序算法(非常糟糕)。除了对排序算法的介绍外，冒泡排序是无用的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4347923
复制相关文章
相似问题
腾讯云开发者
