Aaron学习笔记

少壮不努力,长大没饭吃!
posts - 4, comments - 13, trackbacks - 0, articles - 37

冒泡排序以及改进

Posted on 2009-03-24 15:02 赞劲小子 阅读(766) 评论(1)  编辑 收藏 引用 所属分类: 算法设计与分析
#include "iostream.h"
/**
  *冒泡排序
   冒泡排序(Bubble Sorting)的基本思想是:设待排序n个元素存放在数组a[n]中,无序区范围
   初始为(a(0),a(1),a(2),,a[n-1]),冒泡排序方法是在当前无序区内,从最上面的元素a[0]开
   始,对每两个相邻的元素a[i+1]和a[i](i=0,1,,n-1)进行比较,且使值较小的元素换至值较大
   的元素之上(若a[i]>a[i+1],则a[i]和a[i+1]的值互换),这样经过一趟冒泡排序后,假设最后下移
   的元素为a[k],则无序区中值较大的几个元素到达下端并从小到大依次存放在a[k+1],a[k+2],a[n-1]中,
   这样无序区范围变为(a[0],a[1],a[2],,a[k])。在当前无序区内进行下一趟冒泡排序。这个过
   程一直到某一趟排序中不出现元素交换的动作,排序结束。整个排序过程最多执行n-1遍。这种排序
   方法是通过相邻元素之间的比较与交换,使值较小的元素逐渐从后部移向前部(从下标较大的单元
   移向下标较小的单元),就象水底下的气泡一样逐渐向上冒。故称为冒泡排序法。
*
*/

void bubble(int array[], int size);

int main(){
    
int array[10= {7,6,8,5,10,9,2,4,3,1};
    bubble(array,
10);
    
for(int i = 0; i < 10; i++)
        cout 
<< array[i] << ' ';
    
return 0;
}


void bubble(int array[], int size){
    
for(int pass = 0; pass < size - 1 ; pass++ )
        
for(int j = 0 ; j < size - 1; j++)
        
{
            
int temp;
            
if(array[j] > array[j + 1]){
                temp 
= array[j];
                array[j] 
= array[j+1];
                array[j
+1= temp;
            }

        
        }

}
改进后的冒泡排序
改进思想:比如用冒泡排序将4、5、7、1、2、3这6个数排序。在该列中,第二趟排序结束后,数组已排好序,但计算机此时并不知道已经反排
好序,计算机还需要进行一趟比较,如果这一趟比较,未发生任何数据交换,则知道已排序好,可以不再进行比较了。因而第三趟比较还需要
进行,但第四、五趟比较则是不必要的。为此,我们可以考虑程序的优化。
    为了标志在比较中是否进行了,设一个布尔量flag。在进行每趟比较前将flag置成true。如果在比较中发生了数据交换,则将flag置为false,在
一趟比较结束后,再判断flag,如果它仍为true(表明在该趟比较中未发生一次数据交换)则结束排序,否则进行下一趟比较。
#include "iostream.h"
void bubble(int array[], int size);

int main(){
    
int array[10= {7,6,8,5,10,9,2,4,3,1};
    bubble(array,
10);
    
for(int i = 0; i < 10; i++)
        cout 
<< array[i] << ' ';
    
return 0;
}


void bubble(int array[], int size){
    
bool tag;
    
for(int pass = 0; pass < size - 1; pass++ )
    
{
        tag 
= true;
        
for(int j = 0 ; j < size - 1; j++)
        
{

            
int temp;
            
if(array[j] > array[j + 1]){
                temp 
= array[j];
                array[j] 
= array[j+1];
                array[j
+1= temp;
                tag 
= false;
            }

        }

        
if(tag == true)
            
return ;
     }

}


Feedback

# re: 冒泡排序以及改进  回复  更多评论   

2012-04-19 20:06 by 英文名
英文名www.ie10.net

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理