[算法] 冒泡排序

1. 概念

2. 举例

3. 分析

4. 代码

 1     //在冒泡排序的过程中，关键字较小的记录好比水中的气泡逐趟向上漂浮，而关键字较大的记录好比石块往下沉，每一趟有一块“最大”的石头沉到水底。  
 2     #include <iostream>  
 3     using namespace std;  
 4       
 5     void busort(int a[],int size)  
 6     {  
 7         for(int i=0;i<size-1;i++)  
 8             for(int j=size-1;j>i;j--)  
 9             if(a[j]<a[j-1])  
10             {  
11                 int temp=a[j];  
12                 a[j]=a[j-1];  
13                 a[j-1]=temp;  
14             }  
15     }  
16       
17     int main()  
18     {  
19         int a[]={12,36,24,85,47,30,53,91};  
20         for(int i=0;i<8;i++)  
21             cout<<a[i]<<" ";  
22         cout<<endl;  
23       
24         busort(a,8);  
25         for(int i=0;i<8;i++)  
26             cout<<a[i]<<" ";  
27         cout<<endl;  
28       
29         return 0;  
30     }

View Code

5. 代码说明

int a[]={12,36,24,85,47,30,53,91};

busort(a,8);

复杂度计算 n*（n-1）/2

复杂度次数	i	j	初始数组a[]	一次冒泡后的数组a[]
1	0	7	12,36,24,85,47,30,53,91	12,36,24,85,47,30,53,91
2	0	6	12,36,24,85,47,30,53,91	12,36,24,85,47,30,53,91
3	0	5	12,36,24,85,47,30,53,91	12,36,24,85,30,47,53,91
4	0	4	12,36,24,85,30,47,53,91	12,36,24,30,85,47,53,91
5	0	3	12,36,24,85,30,47,53,91	12,36,24,30,85,47,53,91
6	0	2	12,36,24,30,85,47,53,91	12,24,36,30,85,47,53,91
7	0	1	12,24,36,30,85,47,53,91	12,24,36,30,85,47,53,91
8	1	7	12,24,36,30,85,47,53,91	12,24,36,30,85,47,53,91

9	1	6	12,24,36,30,85,47,53,91	12,24,36,30,85,47,53,91
10	1	5	12,24,36,30,85,47,53,91	12,24,36,30,47,85,53,91
11	1	4	12,24,36,30,47,85,53,91	12,24,36,30,47,85,53,91
12	1	3	12,24,36,30,47,85,53,91	12,24,30,36,47,85,53,91
13	1	2	12,24,30,36,47,85,53,91	12,24,30,36,47,85,53,91

14	2	7	12,24,30,36,47,85,53,91	12,24,30,36,47,85,53,91
15	2	6	12,24,30,36,47,85,53,91	12,24,30,36,47,53,85,91
16	2	5	12,24,30,36,47,53,85,91	12,24,30,36,47,53,85,91
17	2	4	12,24,30,36,47,53,85,91	12,24,30,36,47,53,85,91
18	2	3	12,24,30,36,47,53,85,91	12,24,30,36,47,53,85,91

19	3	7	12,24,30,36,47,53,85,91	12,24,30,36,47,53,85,91
20	3	6	12,24,30,36,47,53,85,91	12,24,30,36,47,53,85,91
21	3	5	12,24,30,36,47,53,85,91	12,24,30,36,47,53,85,91
22	3	4	12,24,30,36,47,53,85,91	12,24,30,36,47,53,85,91

23	4	7	12,24,30,36,47,53,85,91	12,24,30,36,47,53,85,91
24	4	6	12,24,30,36,47,53,85,91	12,24,30,36,47,53,85,91
25	4	5	12,24,30,36,47,53,85,91	12,24,30,36,47,53,85,91

26	5	7	12,24,30,36,47,53,85,91	12,24,30,36,47,53,85,91
27	5	6	12,24,30,36,47,53,85,91	12,24,30,36,47,53,85,91

28	6	7	12,24,30,36,47,53,85,91	12,24,30,36,47,53,85,91