白話経典アルゴリズムシリーズの一つの泡の順序付けの3種類の実現.

ブロガー人http://blog.csdn.net/morewindows/article/details/6657829
 
 
バブルソートは、小さいものから大きいものへのソートの例として、非常に容易に理解され、実装される.
配列長をNとする.
1.隣接する前後の2つのデータを比較し、前のデータが後のデータより大きい場合、2つのデータを交換する.
2.このように配列の0番目のデータをN-1番目のデータに1回遍歴すると、最大のデータは配列のN-1番目の位置に「沈」する.
3.N=N-1で、Nが0でない場合は前の2つのステップを繰り返し、そうでない場合はソートが完了します.
 
定義に従ってコードを簡単に書きます.
[cpp] view plain copy print ?
//泡立ち順1  

void BubbleSort1(int a[], int n)  

{  

       int i, j;  

       for (i = 0; i < n; i++)  

              for (j = 1; j < n - i; j++)  

                     if (a[j - 1] > a[j])  

                            Swap(a[j - 1], a[j]);  

}  

//    1
void BubbleSort1(int a[], int n)
{
       int i, j;
       for (i = 0; i < n; i++)
              for (j = 1; j < n - i; j++)
                     if (a[j - 1] > a[j])
                            Swap(a[j - 1], a[j]);
}

次に最適化し、フラグを設定します.このフラグが交換された場合はtrue、そうでない場合はfalseです.明らかに交換が発生しなかった場合は、ソートが完了したことを示します.
[cpp] view plain copy print ?
  

 
 
 
  
 
   
 
    [cpp] view plain copy print ? 
   
 
  
 
  
 
   
//    2   
 
   
void BubbleSort2(int a[], int n)  
 
   
{  
 
   
       int j, k;  
 
   
       bool flag;  
 
   
  
 
   
       k = n;  
 
   
       flag = true;  
 
   
       while (flag)  
 
   
       {  
 
   
              flag = false;  
 
   
              for (j = 1; j < k; j++)  
 
   
                     if (a[j - 1] > a[j])  
 
   
                     {  
 
   
                            Swap(a[j - 1], a[j]);  
 
   
                            flag = true;  
 
   
                     }  
 
   
              k--;  
 
   
       }  
 
   
}  
 
  
 
 
 
 
//    2
void BubbleSort2(int a[], int n)
{
       int j, k;
       bool flag;

       k = n;
       flag = true;
       while (flag)
       {
              flag = false;
              for (j = 1; j < k; j++)
                     if (a[j - 1] > a[j])
                     {
                            Swap(a[j - 1], a[j]);
                            flag = true;
                     }
              k--;
       }
}
  
さらに   します.100 の の  があって、 の10 だけが   で、 ろの90 はすでに  が い、 の10 より きい  、  の   、  に  が  した  は ず10  であり、この  の のデータは ず  が っているので、この  を  して、2  は  の からこの  まで  すればよい.
[cpp] view plain copy print ? 
//  ち 3     
 void BubbleSort3(int a[], int n)   
  
{     
     int j, k;   
  
    int flag;     
        
  
    flag = n;     
     while (flag > 0)   
  
    {     
         k = flag;   
  
        flag = 0;     
         for (j = 1; j < k; j++)   
  
            if (a[j - 1] > a[j])     
             {   
  
                Swap(a[j - 1], a[j]);     
                 flag = j;   
  
            }     
     }   
  
}     
//    3
void BubbleSort3(int a[], int n)
{
	int j, k;
	int flag;
	
	flag = n;
	while (flag > 0)
	{
		k = flag;
		flag = 0;
		for (j = 1; j < k; j++)
			if (a[j - 1] > a[j])
			{
				Swap(a[j - 1], a[j]);
				flag = j;
			}
	}
}
  
バブルソートは    の いソート  であり、データ  が さい  に  することができる.データ  が    きい  は、 のソート  を いることが ましい.