博客

什么是冒泡排序

这里引用一下百度百科上的定义：

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

冒泡排序在实际工作中用的并不多，多是面试题中会遇到。

下面用java代码来实现：

基本写法

为了看到后面优化后的效果，我加了count 和 num l两个变量来分布统计外循环和内循环的次数

/**
	 * 原始的冒泡排序
	 * @param values
	 */
	public static void bubbleSort(int[] values) {
   
		System.out.println("排序前：" + Arrays.toString(values));
		int tmp;// 循环外创建变量，减少垃圾产生，提高性能
		int count = 0;// 比较了多少趟
		int num = 0; // 比较次数
		// 外层循环，n 个元素，最多需要 n -1 趟循环
		for(int i = 0; i < values.length -1 ; i++) {
   
			count ++;
			// 内层循环， 每一次都从开始两个元素开始两两比较到最后
			for (int j = 0; j < values.length - 1; j++) {
   
				if(values[j] > values[j + 1]) {
   
					tmp = values[j];
					values[j] = values[j + 1];
					values[j + 1] = tmp;
				}
				num ++;
			}
		}
		System.out.println("排序后：" +  Arrays.toString(values));
		System.out.println("比较趟数："+count + ",比较次数：" + num);
	}

优化后写法

/**
	 * 优化了比较次数的冒泡排序
	 * @param values
	 */
	public static void bubbleSort2(int[] values) {
   
		System.out.println("排序前：" + Arrays.toString(values));
		int tmp; // 循环外创建变量，减少垃圾产生，提高性能
		int count = 0;// 比较了多少趟
		int num = 0; // 比较次数
		// 外层循环，n 个元素，最多需要 n -1 趟循环
		for(int i = 0; i < values.length -1</