Java 实现冒泡排序

冒泡排序：

就是按索引逐次比较相邻的两个元素，如果大于/小于(取决于需要升序排还是降序排)，则置换，否则不做改变

这样一轮下来，比较了n-1次，n等于元素的个数；n-2, n-3 ... 一直到最后一轮，比较了1次

所以比较次数为递减：从n-1 到 1

那么总的比较次数为：1+2+3+...+(n-1),  以等差公式计算：(1+n-1)/2*(n-1) ==> n/2*(n-1) ==> (n^2-n) * 0.5

用大O表示算法的时间复杂度：O(n^2) ,  忽略了系数0.5和常数-n

public class BubbleSort {
	public static void main(String[] args) {
		int len = 10;
		int[] ary = new int[len];
		Random random = new Random();
		for (int j = 0; j < len; j++) {
			ary[j] = random.nextInt(1000);
		}
	
		System.out.println("-------排序前------");
		for (int j = 0; j < ary.length; j++) {
			System.out.print(ary[j] + " ");
		}
		/*
		 * 升序， Asc1和Asc2优化了内部循环的比较次数，比较好
		 * 总的比较次数：
		 * 		Asc1、Asc2：(1+n-1)/2*(n-1) ==> n/2*(n-1) ==> n*(n-1)/2 ==>(n^2-n)/2 
		 * 		Asc： n^2-n
		 */
//		orderAsc(ary);
//		orderAsc2(ary);
		orderAsc1(ary);
		
		//降序，只需要把判断大小于 置换一下
		
	}
	
	static void orderAsc(int[] ary) {
		int count = 0;//比较次数
		int len = ary.length;
		for (int j = 0; j < len; j++) {//外层固定循环次数
			for (int k = 0; k < len - 1; k++) {//内层固定循环次数
				if (ary[k] > ary[k + 1]) {
					ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//一步交换
					/* 交换两个变量值
					 * a=a+b
					 * b=a-b
					 * a=a-b
					 */
				} 
				count++;
			}
		}
		System.out.println("\n-----orderAsc升序排序后------次数：" + count);
		for (int j = 0; j < len; j++) {
			System.out.print(ary[j] + " ");
		}
	}
	
	static void orderAsc1(int[] ary) {
		int count = 0;//比较次数
		int len = ary.length;
		for (int j = 0; j < len; j++) {//外层固定循环次数
			for (int k = len - 1; k > j; k--) {//内层从多到少递减比较次数
				if (ary[k] < ary[k - 1]) {
					ary[k] = ary[k - 1] + (ary[k - 1] = ary[k]) * 0;//一步交换
				} 
				count++;
			}
		}
		System.out.println("\n-----orderAsc1升序排序后------次数：" + count);
		for (int j = 0; j < len; j++) {
			System.out.print(ary[j] + " ");
		}
	}

	static void orderAsc2(int[] ary) {
		int count = 0;//比较次数
		int len = ary.length;
		for (int j = len - 1; j > 0; j--) {//外层固定循环次数
			/*
			 * k < j; 总的比较次数=(n^2-n)/2
			 */
			for (int k = 0; k < j; k++) {//内层从多到少递减比较次数
				if (ary[k] > ary[k + 1]) {
					ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//一步交换
				}
				count++;
			}
		}
		System.out.println("\n-----orderAsc2升序排序后------次数：" + count);
		for (int j = 0; j < len; j++) {
			System.out.print(ary[j] + " ");
		}
	}
}

-------排序前------
898 7 862 286 879 660 433 724 316 737 
-----orderAsc1升序排序后------次数：45
7 286 316 433 660 724 737 862 879 898