共计 1431 个字符，预计需要花费 4 分钟才能阅读完成。
冒泡排序的时间用大 O 表示法是 O(N^2).
传统的冒泡排序：
/**
* @param total 要排序的数组长度
*/
public void sort(int total){
int num[];
if(total <= 0){
System.out.println(“ 请输入大于 0 的正整数 ”);
}else{
num = new int[total];
for (int i = 0 ; i < total; i++){
// 生成随机 1 到 100 之间的数
Random ra =new Random();
num[i] = ra.nextInt(100)+1;
}
System.out.println(“ 要排序的数组为：” + Arrays.toString(num));
int sum = 0;
int out,in;
for (out = total – 1; out > 1; out–){
for (in = 0 ; in < out; in++){
sum ++;
if(num[in] > num[in+1]){
int temp = num[in];
num[in] = num[in+1];
num[in+1] = temp;
}
}
}
// 最原始的冒泡排序
for(int i = 0; i < total -1 ; i ++){
for (int j = 0 ; j < total -1 ; j++){
sum ++;
if(num[j] > num[j+1]){
int temp = num[j];
num[j] = num[j+1];
num[j+1] = temp;
}
}
}
System.out.println(“ 排序完成的数组为：” + Arrays.toString(num));
System.out.println(“ 总共用次数：” + sum);
}
}
优化过后的冒泡排序：
/**
* @param total 要排序的数组长度
*/
public void sort(int total){
int num[];
if(total <= 0){
System.out.println(“ 请输入大于 0 的正整数 ”);
}else{
num = new int[total];
for (int i = 0 ; i < total; i++){
// 生成随机 1 到 100 之间的数
Random ra =new Random();
num[i] = ra.nextInt(100)+1;
}
System.out.println(“ 要排序的数组为：” + Arrays.toString(num));
/** 核心算法：
* 双重循环，外层循环用于控制排多少次序。
* 内层循环从第一位开始一直往后比较，内层循环一次后，可以将最大的数至于末尾。
* 外层循环让内层循环继续排没有排序过的数组，排序过的不用再排。
*/
int sum = 0;
int out,in;
for (out = total – 1; out > 1; out–){
for (in = 0 ; in < out; in++){
sum ++;
if(num[in] > num[in+1]){
int temp = num[in];
num[in] = num[in+1];
num[in+1] = temp;
}
}
}
System.out.println(“ 排序完成的数组为：” + Arrays.toString(num));
System.out.println(“ 总共用次数：” + sum);
}
}
大家对比可以发现，就是外层循环的时候有点变化，其他的代码都是一模一样的。
那么优化后的算法能快多少呢。我们都以数组长度为 10 来计算：
传统冒泡排序：9×9=81 步，
优化后的冒泡排序：9+8+7+6+5+4+3+2=44 步。
因为优化后的冒泡排序，每排完一次，最后一个数已经是最大的，就不需要再比较了。
