全部栏目

首页 行业资讯 宠物日常 宠物养护 宠物健康 宠物故事

什么是冒泡排序算法

发布网友 发布时间：2022-04-26 03:24

我来回答

共8个回答

懂视网 时间：2022-05-07 04:01

简化版的桶排序不仅仅有上一节所遗留的问题，更要命的是：它非常浪费空间！例如需要排序数的范围是0~2100000000之间，那你则需要申请2100000001个变量，也就是说要写成int a[2100000001]。因为我们需要用2100000001个“桶”来存储0~2100000000之间每一个数出

　　简化版的桶排序不仅仅有上一节所遗留的问题，更要命的是：它非常浪费空间！例如需要排序数的范围是0~2100000000之间，那你则需要申请2100000001个变量，也就是说要写成int a[2100000001]。因为我们需要用2100000001个“桶”来存储0~2100000000之间每一个数出现的次数。即便只给你5个数进行排序（例如这5个数是1，1912345678，2100000000，18000000和912345678），你也仍然需要2100000001个“桶”，这真是太浪费了空间了！还有，如果现在需要排序的不再是整数而是一些小数，比如将5.567，2.12，1.1，3.123，4.1234这五个数进行从小大排序又该怎么办呢？现在我们来学习另一种新的排序算法：冒泡排序。它可以很好的解决这两个问题。
　　冒泡排序的基本思想是：每次比较两个相邻的元素，如果他们的顺序错误就把他们交换过来。

　　例如我们需要将12 35 99 18 76这5个数进行从大到小进行排序。既然是从大到小排序也就是说越小的越靠后，你是不是觉得我在说废话，但是这句话很关键(∩_∩)。

　　首先比较第1位和第2位的大小，现在第1位是12，第2位是35。发现12比35要小，因为我们希望越小越靠后嘛，因此需要交换这两个数的位置。交换之后这5个数的顺序是35 12 99 18 76。

　　按照刚才的方法，继续比较第2位和第3位的大小，第2位是12，第3位是99。12比99要小，因此需要交换这两个数的位置。交换之后这5个数的顺序是35 99 12 18 76。

　　根据刚才的规则，继续比较第3位和第4位的大小，如果第3位比第4位小，则交换位置。交换之后这5个数的顺序是35 99 18 12 76。

　　最后，比较第4位和第5位。4次比较之后5个数的顺序是35 99 18 76 12。

　　经过4次比较后我们发现最小的一个数已经就位（已经在最后一位，请注意12这个数的移动过程），是不是很神奇。现在再来回忆一下刚才比较的过程。每次都是比较相邻的两个数，如果后面的数比前面的数大，则交换这两个数的位置。一直比较下去直到最后两个数比较完毕后，最小的数就在最后一个了。就如同是一个气泡，一步一步往后“翻滚”，直到最后一位。所以这个排序的方法有一个很好听的名字“冒泡排序”。


　　说道这里其实我们的排序只将5个数中最小的一个归位了。每将一个数归位我们将其称为“一趟”。下面我们将继续重复刚才的过程，将剩下的4个数一一归位。

　　好现在开始“第二趟”，目标是将第2小的数归位。首先还是先比较第1位和第2位，如果第1位比第2位小，则交换位置。交换之后这5个数的顺序是99 35 18 76 12。接下来你应该都会了，依次比较第2位和第3位，第3位和第4位。注意此时已经不需要再比较第4位和第5位。因为在第一趟结束后已经可以确定第5位上放的是最小的了。第二趟结束之后这5个数的顺序是99 35 76 18 12。

　　“第三趟”也是一样的。第三趟之后这5个数的顺序是99 76 35 18 12。

　　现在到了最后一趟“第四趟”。有的同学又要问了，这不是已经排好了吗？还要继续？当然，这里纯属巧合，你可以用别的数试一试可能就不是了。你能找出这样的数据样例来吗？请试一试。

　　“冒泡排序”原理是：每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数（既第5位）归位，第二趟只能将倒数第2位上的数（既第4位）归位，第三趟只能将倒数第3位上的数（既第3位）归位，而现在前面还有两个位置上的数没有归位，因此我们仍然需要进行“第四趟”。

　　“第四趟”只需要比较第1位和第2位的大小。因为后面三个位置上的数归位了，现在第1位是99，第2位是76，无需交换。这5个数的顺序不变仍然是99 76 35 18 12。到此排序完美结束了，5个数已经有4个数归位，那最后一个数也只能放在第1位了。

　　最后我们总结一下：如果有n个数进行排序，只需将n-1个数归位，也就是说要进行n-1趟操作。而“每一趟”都需要从第1位开始进行相邻两个数的比较，将较小的一个数放在后面，比较完毕后向后挪一位继续比较下面两个相邻数的大小，重复此步骤，直到最后一个尚未归位的数，已经归位的数则无需再进行比较（已经归位的数你还比较个啥，浪费表情）。

　　这个算法是不是很强悍。记得我每次拍集体照的时候就总是被别人换来换去的，当时特别烦。不知道发明此算法的人当时的灵感是否来源于此。罗里吧嗦地说了这么多，下面是代码。建议先自己尝试去实现一下看看，再来看我是如何实现的。

#include 
int main()
{
 int a[100],i,j,t,n;
 scanf("%d",&n); //输入一个数n，表示接下来有n个数
 for(i=1;i<=n;i++) //循环读入n个数到数组a中
 scanf("%d",&a[i]);
 //冒泡排序的核心部分
 for(i=1;i<=n-1;i++) //n个数排序，只用进行n-1趟
 {
 for(j=1;j<=n-i;j++) //从第1位开始比较直到最后一个尚未归位的数，想一想为什么到n-i就可以了。
 {
  if(a[j]






　　可以输入以下数据进行验证




10
8 100 50 22 15 6 1 1000 999 0





　　运行结果是




0 1 6 8 15 22 50 100 999 1000





 



　　将上面代码稍加修改，就可以解决第1节遗留的问题，如下。



#include 
struct student
{
 char name[21];
 char score;
};//这里创建了一个结构体用来存储姓名和分数
int main()
{
 struct student a[100],t;
 int i,j,n;
 scanf("%d",&n); //输入一个数n
 for(i=1;i<=n;i++) //循环读入n个人名和分数
 scanf("%s %d",a[i].name,&a[i].score);
 //按分数从高到低进行排序
 for(i=1;i<=n-1;i++) 
 {
 for(j=1;j<=n-i;j++)
 {
  if(a[j].score






　　可以输入以下数据进行验证








5
huhu 5
haha 3
xixi 5
hengheng 2
gaoshou 8









　　运行结果是




gaoshou
huhu
xixi
haha
hengheng





 



　　冒泡排序的核心部分是双重嵌套循环。不难看出冒泡排序的时间复杂度是O(N2)。这是一个非常高的时间复杂度。冒泡排序早在1956年就有人开始研究，之后有很多人都尝试过对冒泡排序进行改进，但结果却令人失望。如Knuth（Donald E. Knuth中文名为高德纳，1974年图灵奖获得者）所说：“冒泡排序除了它迷人的名字和导致了某些有趣的理论问题这一事实之外，似乎没有什么值得推荐的。”你可能要问：那还有没有更好的排序算法呢？请期待下周更新——快速排序。








【啊哈！算法】算法2：邻居好说话——冒泡排序

http://bbs.ahalei.com/thread-4400-1-1.html (出处: 啊哈磊_编程从这里起步) 






                                                            

                        
                        热心网友
                        时间：2022-05-07 01:09
                    

                    
冒泡排序算法：重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
扩展资料：
冒泡排序算法的原理如下：
1，比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2，对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3，针对所有的元素重复以上的步骤，除了最后一个。
4，持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
参考资料：百度百科---冒泡排序

                                        
                                                            

                        
                        热心网友
                        时间：2022-05-07 02:27
                    

                    
基本思路：对尚未排序的各元素从头到尾依次比较相邻的两个元素是否逆序（与欲排顺序相反），若逆序就交换这两元素，经过第一轮比较排序后便可把最大（或最小）的元素排好，然后再用同样的方法把剩下的元素逐个进行比较，就得到了你所要的顺序。可以看出如果有
n
个元素，那么一共要进行
n-1
轮比较，第
i
轮要进行
j=n-i
次比较。
我也不知道你说的是用哪种语言编写：就列出了如下几种，希望你能满意
#include<stdio.h>
void
main()
{
int
a[10];
int
i,j,t;
printf("输入10个整数：\n");
for(
i
=
0;
i
<
10;
i
++
)
scanf("%d",&a[
i
]);
//依次输入10个整数
for(
j
=
0;
j
<
9;
j
++
)
//进行9轮排序
即n－1次
{
for(
i
=
0;
i
<
9-j;
i
++)
//每轮进行n－1－j
次比较，最多n－1－j
次交换
if(
a[
i
]
>
a[
i
+
1
]
)
{
t
=
a[
i
]
;
a[
i
]
=
a[
i
+
1
];
//小的沉底，大的上浮
a[
i
+
1
]
=
t;
}
}
printf("排序结果:");
for(
i
=
0;
i
<
10;
i
++
)
//依次输出排序结果
printf("%d\t",a[
i
]);
printf("\n");
}
PASCAL为例子
procere
Bubble_Sort(var
L:List);
vari,j:position;
begin
for
i:=First(L)
to
Last(L)-1
do
for
j:=First(L)
to
Last(L)-i
do
if
L[j]>L[j+1]
then
4
swap(L[j],L[j+1]);
//交换L[j]和L[j+1]
end;
下面使用c++语言编写
#include<iostream.h>
void
main()
{
int
a[n],i,j,temp;
cout<<"请输入数字："<<endl;
for(i=0;i<=n;i++)
cin>>a;
//依次输入n个整数
for(i=0;i<n;i++)
{
for（j=i+1;j<n;j++）
if(a<a[j])
//利用临时变量temp交换顺序
{
temp=a[j];
a[j]=a;
a=temp;
}
cout<<a<<'
';
//依次输出结果
}
下面使用Visual
Basic编写
Option
Explicit
Private
Sub
Form_Load()
Dim
a,
c
As
Variant
Dim
i
As
Integer,
temp
As
Integer,
w
As
Integer
a
=
Array(12,
45,
17,
80,
50)
For
i
=
0
To
UBound(a)
-
1
If
(a(i)
>
a(i
+
1))
Then
'若是递减,改为a(i)<a(i+1)
temp
=
a(i)
a(i)
=
a(i
+
1)
a(i
+
1)
=
temp
End
If
Next
For
Each
c
In
a
Print
c;
Next
End
Sub

                                                            

                        
                        热心网友
                        时间：2022-05-07 04:02
                    

                    
基本思路：对尚未排序的各元素从头到尾依次比较相邻的两个元素是否逆序（与欲排顺序相反），若逆序就交换这两元素，经过第一轮比较排序后便可把最大（或最小）的元素排好，然后再用同样的方法把剩下的元素逐个进行比较，就得到了你所要的顺序。可以看出如果有 n 个元素，那么一共要进行 n-1 轮比较，第 i 轮要进行 j=n-i 次比较。

我也不知道你说的是用哪种语言编写：就列出了如下几种，希望你能满意
  #include<stdio.h>
  void main()
  {
  int a[10];
  int i,j,t;
  printf("输入10个整数：\n");
  for( i = 0; i < 10; i ++ )
  scanf("%d",&a[ i ]); //依次输入10个整数
  for( j = 0; j < 9; j ++ ) //进行9轮排序 即n－1次
  {
  for( i = 0; i < 9-j; i ++) //每轮进行n－1－j 次比较，最多n－1－j 次交换
  if( a[ i ] > a[ i + 1 ] ) 
  {
  t = a[ i ] ;
  a[ i ] = a[ i + 1 ]; //小的沉底，大的上浮
  a[ i + 1 ] = t;
  }
  }
  printf("排序结果:");
  for( i = 0; i < 10; i ++ ) //依次输出排序结果
  printf("%d\t",a[ i ]);
  printf("\n");
  }
  PASCAL为例子
  procere Bubble_Sort(var L:List);
  vari,j:position;
  begin 
  for i:=First(L) to Last(L)-1 do
  for j:=First(L) to Last(L)-i do
  if L[j]>L[j+1] then 4 swap(L[j],L[j+1]); 
  //交换L[j]和L[j+1]
  end;
  下面使用c++语言编写
  #include<iostream.h>
  void main()
  {
  int a[n],i,j,temp;
  cout<<"请输入数字："<<endl;
  for(i=0;i<=n;i++)
  cin>>a; //依次输入n个整数
  for(i=0;i<n;i++)
  {
  for（j=i+1;j<n;j++）
  if(a<a[j]) //利用临时变量temp交换顺序
  { temp=a[j];
  a[j]=a;
  a=temp;
  }
  cout<<a<<' '; //依次输出结果
  }
  下面使用Visual Basic编写
   Option Explicit
  Private Sub Form_Load()
  Dim a, c As Variant
  Dim i As Integer, temp As Integer, w As Integer
  a = Array(12, 45, 17, 80, 50)
  For i = 0 To UBound(a) - 1
  If (a(i) > a(i + 1)) Then '若是递减,改为a(i)<a(i+1)
  temp = a(i)
  a(i) = a(i + 1)
  a(i + 1) = temp
  End If
  Next
  For Each c In a
  Print c;
  Next
  End Sub

                                        
                                                            

                        
                        热心网友
                        时间：2022-05-07 05:53
                    

                    
冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到最大数前的一对相邻数，将小数放前，大数放后，第二趟结束，在倒数第二个数中得到一个新的最大数。如此下去，直至最终完成排序。
由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。
用二重循环实现，外循环变量设为i，内循环变量设为j。外循环重复9次，内循环依次重复
9，8，...，1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2,...,9，对于每一个i,
j的值依次为1,2,...10-i。
产生
在许多程序设计中，我们需要将一个数列进行排序，以方便统计，而冒泡排序一直由于其简洁的思想方法而倍受青睐。
排序过程
设想被排序的数组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(n^2),算法为稳定的排序方
编辑本段
冒泡排序代码
AAuto
bubble_sort
=
function(array){
var
temp;
for(
i=1;#array
){
//i前面的已经是最小的数，并排序好了
for(j=#array;i+1;-1){
//挨个比较
if(array[j]<array[j-1]){
//小的总是往前排
bubble
=
array[j]
array[j]
=
array[j-1];
array[j-1]
=
bubble;
}
}
}
}
io.print("----------------")
io.print("冒泡排序(
交换类换排序
)")
io.print("----------------")
array
={2;46;5;17;1;2;3;99;12;56;66;21};
bubble_sort(array,1,#array)
//输出结果
for(i=1;#array;1){
io.print(
array[i]
)
}
C
void
bubble_sort(int
*x,
int
n)
{
int
j,
k,
h,
t;
for
(h=n-1;
h>0;
h=k)
/*循环到没有比较范围*/
{
for
(j=0,
k=0;
j<h;
j++)
/*每次预置k=0，循环扫描后更新k*/
{
if
(*(x+j)
>
*(x+j+1))
/*大的放在后面，小的放到前面*/
{
t
=
*(x+j);
*(x+j)
=
*(x+j+1);
*(x+j+1)
=
t;
/*完成交换*/
k
=
j;
/*保存最后下沉的位置。这样k后面的都是排序排好了的。*/
}
}
}
}
C++
#include
<iostream>
#define
LEN
9
using
namespace
std;
int
main()
{
int
nArray[LEN];
for(int
i=0;i<LEN;i++)nArray[i]=LEN-i;
cout<<"原始数据为："<<endl;
for(int
i=0;i<LEN;i++)cout<<nArray[i]<<"
";
cout<<endl;
//开始冒泡
{
int
temp;
for(int
i=LEN-1;i>0;i--)
for(int
j=0;j<i;j++)
{
if(nArray[j]>nArray[j+1])
{
temp=nArray[j];
nArray[j]=nArray[j+1];
nArray[j+1]=temp;
}
}
}
//结束冒泡
cout<<"排序结果:"<<endl;
for(int
i=0;i<LEN;i++)cout<<nArray[i]<<"
";
return
0;
}

                                                            

                        
                        热心网友
                        时间：2022-05-07 08:35
                    

                    
起泡排序，别名“冒泡排序”，该算法的核心思想是将无序表中的所有记录，通过两两比较关键字，得出升序序列或者降序序列。

                                        
                                                            

                        
                        热心网友
                        时间：2022-05-07 11:33
                    

                    
#include<stdio.h>
#define
MAX_N
1024
/*存储大小为1024*/
void
bubsort(int
a[],int
n)/*冒泡排序*/
{
int
i,j,tmp;
for(i=0;i<n;i++)
for(j=n-1;j>i;j--)
if(a[j]<a[j-1])/*如果a[j]比前面a[j-1]的小，则交换向上浮*/
{/*交换数组a[j]和a[j-1]*/
tmp=a[j];
a[j]=a[j-1];
a[j-1]=tmp;
}
}
int
main(void)
{
int
i,input,N;
int
arr[MAX_N];/*arr为int线性数组*/
puts("请输入排序数组的大小N:");
scanf("%d",&N);/*读入N*/
printf("请输入要排序的%d个数:\n",N);
for(i=0;i<N;i++)/*输入*/
scanf("%d",&arr[i]);
bubsort(arr,N);/*排序函数*/
puts("排序之后....");
for(i=0;i<N-1;i++)/*输出*/
printf("%d
",arr[i]);
printf("%d\n",arr[N-1]);
return
0;
}

                                                            

                        
                        热心网友
                        时间：2022-05-07 14:47
                    

                    
从小到大的排序
class
Program
{
public
static
void
Sort(int[]
myArray)
{
//
取长度最长的词组
--
冒泡法
for
(int
j
=
1;
j
<
myArray.Length;j++)
{
for
(int
i
=
0;
i
<
myArray.Length
-
1;
i++)
{
//
如果
myArray[i]
>
myArray[i+1]
，则
myArray[i]
上浮一位
if
(myArray[i]
>myArray[i
+
1])
{
int
temp
=
myArray[i];
myArray[i]
=
myArray[i
+
1];
myArray[i
+
1]
=
temp;
}
}
}
}
static
void
Main(string[]
args)
{
int[]
myArray
=
new
int[]
{
10,
8,
3,
5,
6,
7,
4,
6,
9
};
Sort(myArray);
for
(int
m
=
0;
m
<
myArray.Length;
m++)
{
Console.WriteLine(myArray[m]);
}
}
从大到小的排序
class
Program
{
public
static
void
Sort(int[]
myArray)
{
//
取长度最长的词组
--
冒泡法
for
(int
j
=
1;
j
<
myArray.Length;j++)
{
for
(int
i
=
0;
i
<
myArray.Length
-
1;
i++)
{
//
如果
myArray[i]
<
myArray[i+1]
，则
myArray[i]
下沉一位
if
(myArray[i]
<
myArray[i
+
1])
{
int
temp
=
myArray[i];
myArray[i]
=
myArray[i
+
1];
myArray[i
+
1]
=
temp;
}
}
}
}
static
void
Main(string[]
args)
{
int[]
myArray
=
new
int[]
{
10,
8,
3,
5,
6,
7,
4,
6,
9
};
Sort(myArray);
for
(int
m
=
0;
m
<
myArray.Length;
m++)
{
Console.WriteLine(myArray[m]);
}
}
声明声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL:11247931@qq.com