首页 > 代码库 > 冒泡的实现即优化

冒泡的实现即优化

2024-07-03 12:09:20   227人阅读

冒泡排序：

　　设数组长为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。切这个位置之后的数据必定已经有序了，记录下这个位置，则第二次遍历时从数组头部位置遍历到该位置即可。

       


联系
我们