首页 > 代码库 > 让算法会说话之冒泡排序

让算法会说话之冒泡排序

转载请注明出处:http://blog.csdn.net/ruoyunliufeng/article/details/25972987

冒泡排序:它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。


一.冒泡排序算法以及优化

1.常用代码

/***************************************************************
*版权所有 (C)2014,公司名称。
*
*文件名称:冒泡排序法
*内容摘要:无
*其它说明:无
*当前版本:V1.0
*作   者:若云流风
*完成日期:2014.5.15
***************************************************************/
#include <stdio.h>

#define N  7

void disp(void);

int a[N]={5,0,7,1,9,11,12};

/*排序函数*/
void BubbleSort(void)  
{  
       int i, j,temp;  
       for (i = 0; i < N-1; i++)             //比较N轮,每一轮比较出最大的那个数(大的数向右移)
	   {
		   
		   printf("\n\n新一轮:        ");

              for (j = 1; j < N - i; j++)   //每一轮比较的次数
			  {
                     if (a[j - 1] > a[j])   //如果左面数比右面的数大,则交换位置(右移)
					 {
					      temp=a[j];
						  a[j]=a[j-1];
						  a[j-1]=temp;

					 }
					 disp();                //不管是否交换都进行打印,方便优化
			  }   
	   }	  
}  

/*输出函数*/
void disp(void)
{
     int i;

     printf("\n排序结果: \n");
	 for(i=0;i<N;i++)
	 {
		printf("%d", a[i]);
		printf("  ");
	 }
	
}

int main(void)
{
	BubbleSort();

	return 0;

}


2.优化一

/***************************************************************
*版权所有 (C)2014,公司名称。
*
*文件名称:冒泡排序法
*内容摘要:无
*其它说明:无
*当前版本:V1.1
*作   者:若云流风
*完成日期:2014.5.16
***************************************************************/
#include <stdio.h>

#define N  7

void disp(void);

int a[N]={5,0,7,1,9,11,12};

/*排序函数*/
void BubbleSort2()  
{  
       int j, k,temp;  
       bool flag;  
  
       k = N;  
       flag = true;  
       while (flag)                           //利用标志位判断是否进行下一轮
       {  
              flag = false; 
			  printf("\n\n新一轮:        ");
              for (j = 1; j < k; j++)
			  {
                     if (a[j - 1] > a[j])     //在比较中引入标志位,如果这一轮有比较才会进行下一轮
                     {  
					      temp=a[j];
						  a[j]=a[j-1];
						  a[j-1]=temp;
						  flag = true;
                     }  
					 disp();
			  }
              k--;  
       }  
} 

/*输出函数*/
void disp(void)
{
     int i;

     printf("\n排序结果: \n");
	 for(i=0;i<N;i++)
	 {
		printf("%d", a[i]);
		printf("  ");
	 }
	
}

int main(void)
{
	BubbleSort2();
   // disp();
	return 0;

}


3.优化二(最终)

/***************************************************************
*版权所有 (C)2014,公司名称。
*
*文件名称:冒泡排序法
*内容摘要:无
*其它说明:无
*当前版本:V1.2
*作   者:若云流风
*完成日期:2014.5.16
***************************************************************/
#include <stdio.h>

#define N  7

void disp(void);

int a[N]={5,0,7,1,9,11,12};

/*排序函数*/
//冒泡排序3
void BubbleSort3(void)
{
	int j, k,temp;
	int flag;
	
	flag = N;
	while (flag > 0)                         //引入标志位
	{
		k = flag;
		flag = 0;                            //清零标志位
		printf("\n\n新一轮:        ");
		for (j = 1; j < k; j++)
		{
			if (a[j - 1] > a[j])             //记录有比较时的标志,优化算法,减少空循环
			{
					      temp=a[j];
						  a[j]=a[j-1];
						  a[j-1]=temp;
				          flag = j;
			}
			disp();
		}
	}
}

/*输出函数*/
void disp(void)
{
     int i;

     printf("\n排序结果: \n");
	 for(i=0;i<N;i++)
	 {
		printf("%d", a[i]);
		printf("  ");
	 }
	
}

int main(void)
{
	BubbleSort3();
   // disp();
	return 0;

}


二.算法会说话

int a[N]={5,0,7,1,9,11,12};

1.常用程序

       这就是我们最常用的算法,数组要是N个数的话,要进行N-1轮,第i轮比较N-i次,如果左面的值比右面值大的话,进行位置互换。

2.优化一

        我们加入标志位,如果上一轮值都没有变化的话,那么我们就直接退出了,避免了第3轮以后的空循环。

3.优化二(最终)

          即使进行了优化一我们仍然可以看到第二轮和第三轮的空循环,尤其是第三轮。这次我们不但加入标志位,而且让标志位记录我们改变值时的位置,下次我们再循环就只循环这个值之前的数就可以了。

         例如:本数组第一轮循环,最后一次赋值flag是在a[2]>a[3]  (7>1)的时候,flag被复制为3,之后就再也没被赋值了(也就是说之后的顺序都是正确的)所以下次,只需要排前三个了。所以下一轮就只有两个结果(消除多余的空循环)。


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