C++冒泡排序的基本思想和步骤
发布网友
发布时间：2022-04-24 11:18
共4个回答
热心网友
时间：2023-10-11 00:03
冒泡排序的基本概念是：依次比较相邻的两个数，将大数放在前面，小数放在后面。即首先比较第1个和第2个数，将大数放前，小数放后。然后比较第2个数和第3个数，将大数放前，小数放后，如此继续，直至比较最后两个数，将大数放前，小数放后，此时第一趟结束，在最后的数必是所有数中的最小数。重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再大于第2个数），将大数放前，小数放后，一直比较到最小数前的一对相邻数，将大数放前，小数放后，第二趟结束，在倒数第二个数中得到一个新的最小数。如此下去，直至最终完成排序。
排序过程
设想被排序的数组R［1..N］垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。
算法示例
49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97 97
Procere BubbleSort(Var R : FileType) //从下往上扫描的起泡排序//
Begin
For I := 1 To N-1 Do //做N-1趟排序//
begin
NoSwap := True; //置未排序的标志//
For J := N - 1 DownTo 1 Do //从底部往上扫描//
begin
If R[J+1]< R[J] Then //交换元素//
begin
Temp := R[J+1]; R[J+1 := R[J]; R[J] := Temp;
NoSwap := False
end;
end;
If NoSwap Then Return//本趟排序中未发生交换，则终止算法//
end
End; //BubbleSort//
该算法的时间复杂性为O(n2),算法为稳定的排序方法
热心网友
时间：2023-10-11 00:04
同上..其实冒泡排列就是多个for循环的经典应用
热心网友
时间：2023-10-11 00:04
冒泡排序的时间复杂度较其他的算法要长，建议用归并排序，他的时间复杂度为log2n
热心网友
时间：2023-10-11 00:05
冒泡排序顾名思义就是大的下沉，小的上浮，当然，可以扩展为小的下沉，大的上浮
比如有以下数据
源数据 B E D C A
第一轮 B D C A E
第二轮 B C A D E
第三轮 B A C D E
第四轮 A B C D E
实现代码如下：
#include <iostream>
using namespace std;
void Sort(int *p, int n)
{
for(int i=1; i<n; i++)// n－1轮比较
{
for(int j=0; j<n-i; j++)
{
if(p[j] > p[j+1]) // 从小到大排序
{
// 交换2个数
p[j] = p[j] ^ p[j+1];
p[j+1] = p[j] ^ p[j+1];
p[j] = p[j] ^ p[j+1];
}
}
}
}
int main(void)
{
int n[10] = {4,52,1,4,6,0,2,5,6,9};
Sort(n, 10);
for(int i=0; i<10; i++)
cout<<n[i]<<" ";
cout<<"\n";
return 0;
}
