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

將一組元素兩兩相比較，直至該組元素順序?yàn)橛尚〉酱蟆?/p>

2.冒泡排序算法原理：

（1）從首位開始徙邻，比較相鄰的元素，如果第一個(gè)元素大于第二個(gè)元素畸裳，就交換兩者位置缰犁，直至結(jié)尾的最后一對。
（2）經(jīng)過（1）的動(dòng)作怖糊，此刻參與比較的元素中最大的一個(gè)排在了末尾帅容。
（3）將上述動(dòng)作中最后一位元素之前的元素再次進(jìn)行（1）（2）步驟，當(dāng)沒有一對元素再需要排序就結(jié)束（1）（2）（3）步驟伍伤。

3.簡單的事例：

首先定義一個(gè)數(shù)組：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;}//第五位和第六位排序；

結(jié)果：六個(gè)元素比了五次阅爽，數(shù)組結(jié)果a[6]={3,5,2,6,4,8};

第二趟排序：第一次排序的最大值不再參與路幸，此刻五個(gè)元素進(jìn)行比較。

           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;}//第四位和第五位排序百侧；

結(jié)果：五個(gè)元素比了四次砰识，數(shù)組a[6]={3,2,5,4,6,8};
同理可知接下來還需要3趟排序能扒，所以當(dāng)假設(shè)數(shù)組元素有n個(gè)時(shí)，需要(n-1)趟排序辫狼，第i趟排序中元素兩兩比較的次數(shù)為(n-i),(i>=1)初斑。

4.核心代碼：

（1）雙重循環(huán)實(shí)現(xiàn)即：

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

（2）遞歸實(shí)現(xiàn)即：

    void sort(int i,int n,int a[]){  //i初值為0膨处，n代表元素的個(gè)數(shù) 
          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.優(yōu)化算法

假設(shè)數(shù)組a[6]={7,2,3,4,5,6};
第一趟排序后將最大數(shù)據(jù)排到了最后见秤；
第二趟排序的時(shí)候會(huì)發(fā)現(xiàn)沒有出現(xiàn)相鄰兩數(shù)據(jù)交換的情況，接下來第三趟至第五趟都沒出現(xiàn)真椿；
所以由此可得出鹃答，當(dāng)某趟排序不會(huì)發(fā)生兩兩數(shù)據(jù)進(jìn)行交換時(shí)，該組數(shù)據(jù)的排序結(jié)束突硝。
優(yōu)化算法如下:

                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.應(yīng)用

題目：設(shè)有n個(gè)正整數(shù)测摔，將他們連接成一排，組成一個(gè)最大的多位整數(shù)解恰。

如:n=3時(shí)锋八，3個(gè)整數(shù)13,312,343,連成的最大整數(shù)為34331213。

如:n=4時(shí),4個(gè)整數(shù)7,13,4,246連接成的最大整數(shù)為7424613护盈。

輸入描述:

有多組測試樣例挟纱，每組測試樣例包含兩行，第一行為一個(gè)整數(shù)N（N<=100）黄琼，第二行包含N個(gè)數(shù)(每個(gè)數(shù)不超過1000樊销，空格分開)。

輸出描述:

每組數(shù)據(jù)輸出一個(gè)表示最大的整數(shù)脏款。

解答：

 # 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;
 }