冒泡排序

简介

冒泡排序，经常出现在各类计算机教材关于排序算法的第一个，它是一种比较简单的排序算法。
冒泡排序的原理是不停的比较数组中相邻的两个元素，如果元素的顺序与所需顺序不同，则将其进行交换，然后索引向前移动一位，再进行比较，当数组中所有元素都不再需要交换时，数组就是有序状态了。
从原理中我们可以看到，这种算法能很快的得到数组中较大的元素。

• 假定数组a[]的第一个元素是a[0]，它与a[1]进行比较，a[0]>a[1],那么就交换a[0]与a[1]
• 交换后的a[1]与a[2]比较，重复过程，如果当 a[1]与a[i]交换之后，此时 a[i]< a[i+1]了，那么就不会再交换它们
• 接下来又会比较a[i+1]与a[i+2]，以此到最后，此轮循环结束，数组末尾的元素一定是最大值
• 每一轮循环都会得到一个在当前无序范围数组中的最大值存放到末尾
  这样的算法流程，看起来就像是一个最大的水泡在向上冒，因此称为冒泡排序法。

具体分析

动图演示

算法实现与分析

public class BubbleSort{

	public static void sort(Comparable[] a){
		//需要判断数组a的长度是否符合规范，此处省略	

		for(int i = 0; i < a.length; i++){
			//每次循环都会在末尾增加一个有序元素
			for(int j = 1; j < a.length-i ; j++){
				if(less(a[j],a[j-1])){
					exch(a,j,j-1);
				}
			}
		}
	}
}

根据程序可以看出，假定数组长度为N，在最好的情况下，即数组已经是有序时，需要~ N(N-1)/2次比较和0次交换，最坏情况下，在数组时反序时，每次比较都会对应一次交换，即需要 ~ N(N-1)/2次比较和~ N(N-1)/2次交换。 所以平均来说，冒泡排序需要 ~ N(N-1)/2次比较和 ~ N(N-1)/4次交换；

---

参考

• 冒泡排序

赏

谢谢你请我吃糖果

支付宝

微信

• 本文作者： xczll
• 本文链接： https://xczllgit.github.io/2020/04/19/algorithm/2020-04-19-bubbleSortion/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！