冒泡的实现及优化

冒泡排序：

　　设数组长为N。以升序为例。

1 比较相邻的2个前后的数据，如果前面数据大于后面的数据，则2个数据交换
2 这样对数组的第0个数据到第N-1个数据进行遍历，则最大的数据会沉到数组的第N-1个位置。
3 N = N-1，如果N != 0 就执行第二步。

1 void Bubble_Sort( int a[],  int N )
2 {
3        int i,  j;
4        
5        for( i = 0; i < N;  ++i )
6              for( j = 1; j < N-i; ++j )
7                  if( a[j-1] > a[j]  )
8                        swap( a[j-1], a[j] );      
9 }

下面对其进行优化：

设置一个标志，如果某一趟遍历发生了交换则为true，如果没发生交换则为false。如果某一趟遍历没发生交换，则表明已经排好序了。

 1 void Bubble_Sort( int a[],  int N )
 2 {
 3        bool flag = true;
 4        int  i;
 5        int  k = n;
 6        while( flag )
 7       {
 8              flag = false;
 9              for(  i = 1;  i < k; ++i )
10                   if( a[i-1] < a[i] )
11                   {
12                         swap( a[i-1], a[i] );
13                         flag = true;
14                   }
15              --k;
16       }  
17 }

再进行进一步优化：

如果100个数据，前10个无序，后90个有序且都大于前10个数据。那么在第一趟遍历时最后发生交换的位置必定小于10。且这个位置之后的数据必定已经有序了，记录下这个位置，则第二次遍历时从数组头部位置遍历到该位置即可。

 1 void bubble_sort( int* a, int  n )
 2 {
 3     int i;
 4     int flag;
 5     int k;
 6     int temp;
 7     
 8     flag = n;
 9     while( flag > 0 )
10     {
11         k = flag;
12         flag = 0;
13         for( i = 1; i < k; ++i )
14         {
15             if( a[i-1] > a[i] )
16             {
17                 temp = a[i-1];
18                 a[i-1] = a[i];
19                 a[i] = temp;
20                 flag = i;
21             }
22         }
23         k = flag;
24     }
25     
26 }

View Code