首页 > 代码库 > 算法分析之冒泡排序

算法分析之冒泡排序

冒泡排序是一个基本的排序算法,基本思路是比较相邻两个数字的大小,根据升序还是降序的需要进行交换,完成一趟后,最大或最小的数字就会被交换到最后一行,因为最后一个数字已经是最大或者最小的数字所以不再进行比较,在进行下一趟的比较,直到所有的数字有序。

代码:

void Bubblesort1(a[],n)

{

        int i,j,temp:

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

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

                   if(a[j-1]>a[j])//前面的大于后面的就进行交换,说明是升序排序

                  {

                       temp=a[j-1];

                       a[j-1]=a[j];

                       a[j]=temp;

                   }

}  

上面是基本的冒泡排序算法,还可以对其进行优化,设置一个标记flag,如果有一趟没有进行交换,说明排序已经完成,改变flag的值

代码:

void Bubblesort2(a[],n)

{

         int i,j;

         bool flag=true;

         while(flag)

         {

               flag=false;

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

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

                   {

                         swap(a[i-1],a[i]);

                         flag=true;

                   }

                n--;

          }

}

上面的优化是对多余的趟数进行优化,还有别的优化方式,比如一行数字后面的数字是有序的,只需要对前面的数字进行排序就好了,可以记录下来第一趟改变的位置,后面的数字是有序的自然不会交换,然后只需要对从开始到该位置的数字进行排序就好了,之后也如此每次记录改变的位置对之前的数字进行排序,知道改变的位置成为第一个数字说明排序已经完成。

代码:

void Bubblesort3(a[],n)

{

        int i,f,k;

        k=n;

        while(k>0)

        {

             f=k;

             k=0;

             for(i=1;i<f;i++)

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

                 {

                    swap(a[i-1],a[i]);

                    k=i;

                  }

          }

}

冒泡排序是一种效率低下的算法,数据少时可以使用,数据多的时候最好采用别的排序算法。

参考:http://blog.csdn.net/morewindows/article/details/6657829

算法分析之冒泡排序