首页 > 代码库 > 让算法会说话之冒泡排序
让算法会说话之冒泡排序
转载请注明出处: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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。