Java算法之冒泡排序——BubbleSort
代码如下：
public static void main(String[] args) {
int[] arr = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
for (int i = 0; i < arr.length – 1; i++) {// 外层循环控制排序趟数
for (int j = 0; j < arr.length – 1 – i; j++) {// 内层循环控制每一趟排序多少次
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
冒泡排序的效率
通过观察arr数组可以看到，第一次排序时进行了9次比较，第二次排序时进行了8次比较，如此类推，直到最后一次进行比较。
对于10个数据项，就是9+8+7+6+5+4+3+2+1=45
一般来说，数组中有N个数据项，则第一次排序中有N-1次比较，第二次排序中有N-2次比较，以此类推。这样徐磊的求和公式如下
（N-1）+（N-2）+（N-3）+ … + 1 = N*(N-1)/2
当N为10时，N*(N-1)/2等于45(10*9)/2
这样算法作了约N*N次比较(忽略减1，不会有很大差异，特别是当N很大时)
因为两个值只有在需要是才会交换，所有见换的次数少于比较的次数。如果数据是随机的，那么大概有一半的数据需要交换，则交换次数为N*N/4(不过在最坏的情况下，即初始数据逆序时，每次比较都需要交换，也就是上面的案例代码)。
交换和比较操作册数都和N²成正比。由于常熟不算在大O表示法中，可忽略2和4，并且认为冒泡排序裕兴需要O(N²)时间级别。运行数据越多，就越能看出冒泡排序的速度是很慢的。
只要看到一个循环嵌套在另一个循环里，如冒泡排序等，就可以怀疑这个算法的运行时间为O(N²)级。外层循环执行N次，内部循环对于每一次外层循环都执行N次。这就意味着将大约需要执行N*N或者N²次某个基础操作。