首页 > 代码库 > 《冒泡排序》算法设计之二
《冒泡排序》算法设计之二
冒泡排序过程
1.首先比较相邻的两个元素,如果前面数据大于后面数据的话,就将这两个数进行交换,依次推,直到完成第N-1个记录与第N个记录交换为止(第一趟起泡)。
2.然后再进行第二趟气泡。由第一趟气泡,可知末尾是最大数,所以第二趟之比较前N-1个数
3.第三趟…… 比较N-2个数
...................................................................................
冒泡分析
通过上述的过程分析,可以知道冒泡就好比一个倒置的三角形。
第一次气泡,比较N次
第二次气泡,比较N-1次
.....................
如图三角形所示
代码分析
由上面分析的冒泡过程,我们在代码实现上也就简单多了。
1.有一个前后两个数交换的过程。
2.有一个交换次数递减的过程
代码实现
<span style="font-family:SimSun;font-size:18px;"> /// <summary> /// 冒泡排序法实现过程 /// </summary> /// <param name="a">数组a用来保存要排序的数字</param> /// <param name="n">数组元素的个数</param> void BubbleSort(int[] a, int n) { int i,j,c; //外层循环,用来辅助,每次递减的次数 for(i=0;i<n;i++) { //里层循环用来做前后两个数的交换 for(j=1;j<n-i;j++) { //两个数交换的过程 if(a[j-1]>a[j]) { //引入第三者,做辅助 c = a[j - 1]; a[j - 1] = a[j]; a[j] = c; } } } }</span>
代码分析,上面的代码也可以做优化,因为如果在一次循环过程中,都没有经过交换的话,那么我们可以知道,此次排序就已经完成了,就不用接着在进行比较判断了,因此我们可以设置一个标志位,来进行判断。
<span style="font-family:SimSun;font-size:18px;"> static void BubbleSort(int[] a, int n) { int i,j,c; bool flag; //外层循环,用来辅助,每次递减的次数 for(i=0;i<n;i++) { flag = false;//设置一个标志位,默认值为false //里层循环用来做前后两个数的交换 for(j=1;j<n-i;j++) { //两个数交换的过程 if(a[j-1]>a[j]) { //引入第三者,做辅助 c = a[j - 1]; a[j - 1] = a[j]; a[j] = c; flag = true; //如果发生交换的话,标志位就为true } } //在此来判断标志位,如果为false的话,证明没有进行交换,因此就已经排序好了,可以直接停止过程了 if (!flag) break; } }</span>
如果明白了冒泡排序的本质后,对于代码也就好实现的多了,要记住上述倒置的三角形,明白两点。
1.比较次数在较少
2.前后做比较
因此上述的代码我们也可以用while语句写,其实都是一样的
<span style="font-family:SimSun;font-size:18px;"> //优化后的冒泡算法 static void BubbleSort2(int []a,int n) { int j; bool flag; int c; //标志位 flag =true ; while(flag) { flag =false ; for(j=1;j<n;j++) { if(a[j-1]>a[j]) { c = a[j - 1]; a[j - 1] = a[j]; a[j] = c; flag = true; } } //次数递减 n--; } }</span>
学习心得
网上这种排序的代码很多,只要你能够理解本质,应用起来也就不费事了。但是理解本质的前提是需要做大量的写写画画的操作。别人的东西,永远是别人的,所以我们要通过研究来化为己有,能够做到为我所用。
《冒泡排序》算法设计之二
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。