冒泡排序应该是我大学里遇见的第一个排序算法,没记错的话应该还是C语言课上讲指针的时候老师给介绍的,当时因为心思完全没在学习上,还沉浸在高考结束的狂欢状态,想着进了大学就真的可以爱谁谁了,反正我是不要再努力读书了,看到黑板上老师写的什么i,j两层嵌套什么的,就一个感觉,真尼玛蛋疼,快下课吧.到后来直接连课都不去上了,想想当初还是挺二逼的.
我的另一位老师又曾经说过,你们啊,上课不听的话,可以,但是要记住我一句话:出来混迟早是要还的,你在学校里不听,除了这个校门你还是要补会来的.哎,这血淋淋的事实,老师你真是我的亲老师啊,不过幸好我大二的时候就深深的明白了这个道理,没有给自己出了学校再补回这些知识的机会,现在转眼也大三了,快要离开学校,现在的当务之急还是要把基础知识抓牢,尤其是在校招中举足轻重的算法与数据结构,所以打算把数据结构的知识以代码的形式重新温习一遍,这就算是第一篇吧,加油敖.
冒泡这个比喻还是比较形象的,我们的数据存储在数组里,数值比较小的元素就像小气泡一样上浮,打得数值则会沉降.其实冒泡排序就是一个多次遍历的过程,从第一个数字开始,依次跟相邻的下一个元素比较,进而交换位置,最大的一个数字先被确定在最后一位,之后就是第二大的数字被确定在倒数第二位,直到第一位排序结束,如果数组中元素的总数为n,那么则需要n-1次遍历.
上图就是一个冒泡排序的全过程.
好了下面我们直接上代码吧.
void bubble_Sort(int array[], int length){int i;int j;<span style="white-space:pre"></span>//i和j都是游标,这里用到了二层循环int temp;<span style="white-space:pre"></span>//temp是在两个数值交换的时候作为临时存储区域的for(i=0;i<length-1;i++){<span style="white-space:pre"></span>//因为数组是从0开始的,所以第二个条件应该是i<length-1,新手经常会写成i<lengthfor(j=0; j<length-(i+1); j++){if(array[j] > array[j + 1]){temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;}}}
以上是我们对冒泡排序的初步实现,我们现根据大O规则计算一下,算法的时间复杂度,观察可知以上代码的规模为n = 10,用到了两层循环嵌套的方式,可以很轻易的计算出执行的次数为 n * (n – 1 / 2),则时间复杂度为O(n^2).
优化:
我们的上一个算法还有没有优化的空间了呢?答案是肯定的.
假如我们要排序的数组为array = {0, 2, 1, 3, 4, 5, 6, 7, 8, 9},我们可以看到这里只有第二个位置的值2和第三个位置的值3是需要交换的,其他的部分已经都排序好了,不再需要比较和移动了,但是按我们上面代码的思路,会做很多无用功,我们可以增加一个flag标记变量来对它进行改进.
void bubble_Sort_Optimize(int array[], int length){int i;int j;int temp;bool flag = true;for(i=0;(i<length-1) && flag;i++){flag = false;for(j=0; j<length-(i+1); j++){if(array[j] > array[j + 1]){temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;flag = true;}}}}这个方法就是在第一层循环的判断循环结束条件上加上flag 即 (i<length – (i+1)) && flag,在每一次进入第二层循环的时候先把flag置为false,如果在这一次的遍历比较中,没有发生一次交换的话,那么flag的值在进入下一次循环之前就无法变回true,那么外层循环就会随之结束,这样,我们之前的无用功就不必在做了,这个解决方案虽然比第一个要更高效,但是时间复杂度仍然是O(n^2).OK,今天的冒泡排序就复习到这里了,谢谢大家.
，人生的成功不过是在紧要处多一份坚持，
