本文主要是介绍冒泡排序和局部冒泡排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
冒泡排序
冒泡排序(Buble Sort)作为一种简单的排序算法,比较容易理解,所以初学算法时候对冒泡排序理解清楚对于以后学习更加复杂的算法会有不小的帮助,所以学习一下冒泡排序还是非常有必要的.
冒泡排序大致想法就是:从第一个开始比较相邻两个元素的值,如果它们的顺序不符合要求就换过来.直到最后一个元素,将最大或者最小的元素沉底.
冒泡排序具体运作可以分为以下几步(以由小到大排列为例):
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
冒泡排序的动画演示如下
下面是Java的冒泡排序:
public class BubbleSort{public static void main(String[] args){int score[] = {9,4,5,6,8,3,2,7,10,1};for (int i = 0; i < score.length -1; i++){ //最多做n-1趟排序for(int j = 0 ;j < score.length - 1 - i; j++){ //对当前无序区间score[0......length-i-1]进行排序(j的范围很关键，这个范围是在逐步缩小的,建议大家写成score.length-1-i这样比较容易理解每趟比较结束后j的范围)if(score[j] > score[j + 1]){ //把大的值交换到后面int temp = score[j + 1];score[j + 1] = score[j];score[j] = temp;}} System.out.print("第" + (i + 1) + "次排序结果：");for(int a = 0; a < score.length; a++){System.out.print(score[a] + "\t");}System.out.println(""); }System.out.print("最终排序结果：");for(int a = 0; a < score.length; a++){System.out.print(score[a] + "\t");}}}
看到这张图,首先,来看冒泡的特点,观察每次排序最后一个数,就是我们需要沉底的数,每趟比较结束后都将本趟比较中最大的数排到本趟的最后.
其次,我们要知道,冒泡排序的比较次数非常的多,一共比较n(n-1)/2次.
局部冒泡排序
public class PartBubbleSort{public static void main(String[] args){int score[] = {9,4,5,6,8,3,2,7,10,1};for (int i = 0; i < score.length -1; i++){ //最多做n-1趟排序if(score[i]>score[i + 1]){int j = 0;int temp = 0;j = i + 1;while(j > 0 && score[j] < score[j - 1]){temp=score[j];score[j]=score[j - 1];score[j - 1] = temp;j--; }}System.out.print("第" + (i + 1) + "次排序结果：");for(int a = 0; a < score.length; a++){System.out.print(score[a] + "\t");}System.out.println(""); }System.out.print("最终排序结果是：");for(int a = 0; a < score.length; a++){System.out.print(score[a] + "\t");}}}
注：测试所用数据均为随机产生的32 位非负整数，由于测试程序的统计量不是运行时间, 所以表1 中的测试结果不依赖于具体计算机的软、硬件等环境因素, 而仅与算法有关。(表摘自点击打开链接)
由上图可见，局部冒泡法的平均移动次数等于冒泡法，但是局部冒泡法的平均比较次数小于冒泡法。
这篇关于冒泡排序和局部冒泡排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
