冒泡排序

Hankercat 2018-07-16 原文

冒泡排序的基本思想：从数列的第一个数开始，把第1个数和第二个数比较，如果第一个比第二个大，就交换两个数的位置（从小到大排序时），然后比较第二个数字和第三个数字的大小，直到比较到最后一位，我们的第一趟排序结束，此时最大值就会出现在最后面。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名“冒泡排序”（和选择排序差不多，选择排序是选择出最大或者最小的数和前面的数字移形换位，冒泡排序是一步一步走到最后面）。

冒泡算法是稳定的算法：因为我们是通过一一比较来交换的，如果两个数字的大小相同，我们就不会交换他们的位置。

冒泡步骤详解：

第一趟：

第二趟：

第三趟：

第四趟：

第五趟：

冒泡排序的时间复杂的：

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数

和记录移动次数

均达到最小值：

，

。

所以，冒泡排序最的时间复杂度为

。
　　若初始文件是反序的，需要进行

趟排序。每趟排序要进行

次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

冒泡排序的最坏时间复杂度为

。

综上，因此冒泡排序总的平均时间复杂度为

。

冒泡排序代码：

 1 #include<iostream>
 2 using namespace std;
 3 int main(){
 4     int n,a[100001];
 5     //读入数据 
 6     cin >> n;
 7     for(int i=0;i<n;i++){
 8         cin>>a[i]; 
 9     }
10     //处理数据 
11     for(int i=0;i<n-1;i++){
12         for(int j=0;j<n-1-i;j++){
13             if(a[j]>a[j+1]){
14                 swap(a[j],a[j+1]);
15             }
16         }
17     }
18     //输出数据 
19     for(int i=0;i<n;i++){
20         cout<<a[i]<<" "; 
21     }
22     return 0;
23 }