1.什么是冒泡排序算法？

将一组元素两两相比较，直至该组元素顺序为由小到大。

2.冒泡排序算法原理：

（1）从首位开始，比较相邻的元素，如果第一个元素大于第二个元素，就交换两者位置，直至结尾的最后一对。
（2）经过（1）的动作，此刻参与比较的元素中最大的一个排在了末尾。
（3）将上述动作中最后一位元素之前的元素再次进行（1）（2）步骤，当没有一对元素再需要排序就结束（1）（2）（3）步骤。

3.简单的事例：

首先定义一个数组：int a[6]={3,6,5,2,8,4};
按照冒泡排序的原理:
第一趟排序：

          int exam;
          if(a[0]>a[1]){
                 exam=a[0];
                  a[0]=a[1];
                  a[1]=exam;}//第一位和第二位排序；

           if(a[1]>a[2]){
                 exam=a[1];
                  a[1]=a[2];
                  a[2]=exam;}//第二位和第三位排序；

          if(a[2]>a[3]){
                 exam=a[2];
                  a[2]=a[3];
                  a[3]=exam;}//第三位和第四位排序；
          if(a[3]>a[4]){
                 exam=a[3];
                  a[3]=a[4];
                  a[4]=exam;}//第四位和第五位排序；

          if(a[4]>a[5]){
                 exam=a[4];
                  a[4]=a[5];
                  a[5]=exam;}//第五位和第六位排序；

结果：六个元素比了五次，数组结果a[6]={3,5,2,6,4,8};

第二趟排序：第一次排序的最大值不再参与，此刻五个元素进行比较。

           int exam;
          if(a[0]>a[1]){
                 exam=a[0];
                  a[0]=a[1];
                  a[1]=exam;}//第一位和第二位排序；

           if(a[1]>a[2]){
                 exam=a[1];
                  a[1]=a[2];
                  a[2]=exam;}//第二位和第三位排序；

          if(a[2]>a[3]){
                 exam=a[2];
                  a[2]=a[3];
                  a[3]=exam;}//第三位和第四位排序；
          if(a[3]>a[4]){
                 exam=a[3];
                  a[3]=a[4];
                  a[4]=exam;}//第四位和第五位排序；

结果：五个元素比了四次，数组a[6]={3,2,5,4,6,8};
同理可知接下来还需要3趟排序，所以当假设数组元素有n个时，需要(n-1)趟排序，第i趟排序中元素两两比较的次数为(n-i),(i>=1)。

4.核心代码：

（1）双重循环实现即：

                   for(int i=0;i<n-1;i++)
                   {         
                         for(int j=0;j<n-i-1;j++)//第i趟排序需要两两比较的次数。
                                   {
                                          if(a[j]>a[j+1])
                                               {
                                                     exam=a[j];
                                                      a[j]=a[j+1];
                                                       a[j+1]=exam;
                                                 }
                                       }
                         }

（2）递归实现即：

    void sort(int i,int n,int a[]){  //i初值为0，n代表元素的个数 
          if(i==(n-1)){
                for(int o=0;o<n;o++);
                   cout<<a[o]<<" ";}
          else
         {
               for(int j=0 ;j<n-1;j++){
                    if(a[j]>a[j+1]){
                            exam=a[j];
                            a[j]=a[j+1];
                            a[j+1]=exam;
                      }
            }       
       }
    
    sort(i,n-1,a);  

}

5.优化算法

假设数组a[6]={7,2,3,4,5,6};
第一趟排序后将最大数据排到了最后；
第二趟排序的时候会发现没有出现相邻两数据交换的情况，接下来第三趟至第五趟都没出现；
所以由此可得出，当某趟排序不会发生两两数据进行交换时，该组数据的排序结束。
优化算法如下:

                bool t=false;
              for(int i=0;i<n-1;i++)
                {      
                   for(int j=0;j<n-i-1;j++)
                       {
                            f=false;
                            if(a[j]>a[j+1])
                                 {
                                    exam=a[j];
                                   a[j]=a[j+1];
                                   a[j+1]=exam;
                                     f=true;
                                 }
                         }
                           if(f==false)break;
                  }

6.应用

题目：设有n个正整数，将他们连接成一排，组成一个最大的多位整数。

如:n=3时，3个整数13,312,343,连成的最大整数为34331213。

如:n=4时,4个整数7,13,4,246连接成的最大整数为7424613。

输入描述:

有多组测试样例，每组测试样例包含两行，第一行为一个整数N（N<=100），第二行包含N个数(每个数不超过1000，空格分开)。

输出描述:

每组数据输出一个表示最大的整数。

解答：

 # include <iostream>
 # include <vector>
 using namespace std;
 int main(){
vector <string> array;
int n;
cin>>n;
for (int i=0;i<n;i++){
    string num;
    cin>>num;
    array.push_back(num);   
}
for(int m=0;m<n-1;m++){
    int g=0;
    for(int j=0;j<n-m-1;j++){
            string x;
    x=array[j];
    string s1,s2;
    s1=array[j]+array[j+1];
    s2=array[j+1]+array[j];
    if(s1<s2){
        array[j]=array[j+1];
        array[j+1]=x;
        g=1; 
    }
}
if(g==0)break;
    }
for(int y=0;y<n;y++){
    cout<<array[y];
}
return 0;
 }