冒泡排序作为一种交换排序方法，可以实现降序和升序。
优化：去除排序完成后的,轮数空转时间（bubblingSortx方法）
/** * 冒泡算法，用于排序: 9 8 7 6 5 4 3 2 1 比较轮数，每一轮比较次数，每一次将相邻的两个数进行比较。 第一轮: 第1次：8 9 7 6 5 4 3 2 1 2：8 7 9 6 5 4 3 2 1 3：8 7 6 9 5 4 3 2 1 4: 8 7 6 5 9 4 3 2 1 5: 8 7 6 5 4 9 3 2 1 6：8 7 6 5 4 3 9 2 1 7：8 7 6 5 4 3 2 9 1 8: 8 7 6 5 4 3 2 1 9 ①.1轮比较，获得最大数(位置固定)。 ②.N个数，比较N-1轮(因最小的数,最后一次的上一次已确定,无需再比较) ③.每轮比较次数，第i轮比较，n-i ④.思路：从开头进行排序，依次对相邻的两个元素进行比较，大的值后移(此值下次作为比较的前元素)，每次确定一个比较的最大值移到最后，下一次比较的长度将减1. ⑤.规则：N个元素进行排序，总共N-1轮，第一轮比较N-1次；第二轮,比较N-2次；第i轮比较N-i次。 注:因计算机计数从0开始,所以轮数和次数都减1，也可从1开始。< "小于"其实已经减1 算法： 双层循环，外循环控制轮数，内循环控制每轮的次数 * */
代码如下(可删除，count1st和count两个多余日志参数)：
package com.ts.w;
/**
* 冒泡排序
* @author tskk
* @version 2015-6-30 11:01:54
* */
public class BubblingSort {
public static void main(String[] args) {
System.out.println("***排序最坏情况***");
int [] preArray = {9,8,7,6,5,4,3,2,1};
System.out.println("预比较数为:"+"9 8 7 6 5 4 3 2 1");
bubblingSort(preArray);
System.out.println();
int [] preArray1 = {9,8,7,6,5,4,3,2,1};
System.out.println("预比较数为1:"+"9 8 7 6 5 4 3 2 1");
bubblingSortx(preArray1);
System.out.println();
System.out.println("***排序非最坏情况***");
int [] preArray2 = {3,2,1,4,5,6,7,8,9};
System.out.println("预比较数为2:"+"3 2 1 4 5 6 7 8 9");
bubblingSort(preArray2);
System.out.println();
int [] preArray3 = {3,2,1,4,5,6,7,8,9};
System.out.println("预比较数为3:"+"3 2 1 4 5 6 7 8 9");
bubblingSortx(preArray3);
}
public static int[] bubblingSort(int [] num){
if(num == null){
return null;
}
int numLen = num.length;
int temp = 0;
int count = 0;
int count1st = 0;
for(int i = 0; i < numLen - 1; i++){//比较轮数
for(int j = 0;j < numLen - i - 1; j++){
if(num[j] > num[j + 1]){//此处调整为小于,修改后,可做降序排序
temp = num[j];
num[j] = num[j + 1];
num[j + 1] = temp;
count++;
}
}
count1st++;
}
System.out.println("bubblingSort比较轮数为:"+count1st);
System.out.println("bubblingSort比较次数为:"+count);
System.out.print("bubblingSort比较结果为:");
for(int i = 0; i < numLen; i++){
System.out.print(" "+num[i]);
}
return num;
}
/**
* 优化：去除排序完成后的,轮数空转时间
* */
public static int[] bubblingSortx(int [] num){
if(num == null){
return null;
}
int numLen = num.length;
int temp = 0;
int count = 0;
int count1st = 0;
int count2nd = 0;
for(int i = 0; i < numLen - 1; i++){//比较轮数
count2nd = 0;//每轮从0开始
for(int j = 0;j < numLen - i - 1; j++){
if(num[j] > num[j + 1]){//此处调整为小于,修改后,可做降序排序
temp = num[j];
num[j] = num[j + 1];
num[j + 1] = temp;
count++;
count2nd++;//如果,某轮,没有交换发生(count2nd=0),说明:此时,排序已完成
}
}
count1st++;
if(count2nd == 0){
break;
}
}
System.out.println("bubblingSortx比较轮数为:"+count1st);
System.out.println("bubblingSortx比较次数为:"+count);
System.out.print("bubblingSortx比较结果为:");
for(int i = 0; i < numLen; i++){
System.out.print(" "+num[i]);
}
return num;
}
}
输出结果为：
***排序最坏情况*** 预比较数为:9 8 7 6 5 4 3 2 1 bubblingSort比较轮数为:8 bubblingSort比较次数为:36 bubblingSort比较结果为: 1 2 3 4 5 6 7 8 9 预比较数为1:9 8 7 6 5 4 3 2 1 bubblingSortx比较轮数为:8 bubblingSortx比较次数为:36 bubblingSortx比较结果为: 1 2 3 4 5 6 7 8 9 ***排序非最坏情况*** 预比较数为2:3 2 1 4 5 6 7 8 9 bubblingSort比较轮数为:8 bubblingSort比较次数为:3 bubblingSort比较结果为: 1 2 3 4 5 6 7 8 9 预比较数为3:3 2 1 4 5 6 7 8 9 bubblingSortx比较轮数为:3 bubblingSortx比较次数为:3 bubblingSortx比较结果为: 1 2 3 4 5 6 7 8 9
注：一般排序并非，最坏排序，所有，以上以节省5次空转。
优化测试演示：冒泡优化测试(1百万元素排序)
