Appearance
冒泡排序可能是我们学过的第一种排序方式，相信最简单的冒泡排序大家都会写，但是学习算法不单单是学习固定的解决思路，我们可以发散思维，尝试优化固有的算法逻辑。
传统冒泡排序
java
public class BubbleSort {
private BubbleSort() {}
public static <E extends Comparable<E>> void sort(E[] data) {
for (int i = 0; i < data.length - 1; i++) {
for (int j = 0; j < data.length - i - 1; j++) {
if (data[j].compareTo(data[j + 1]) > 0) {
swap(data,j,j+1);
}
}
}
}
private static <E extends Comparable<E>> void swap(E[] data, int j, int i) {
E tem = data[i];
data[i] = data[j];
data[j] = tem;
}
public static void main(String[] args) {
Integer[] arr = new Integer[]{6,2,8,1,5,3,9};
sort(arr);
for (Integer a : arr) {
System.out.println(a);
}
}
}测试数据
java
public static void main(String[] args) {
Random random = new Random();
// 1.随机生成数据
int number = 10; // 生成数据的数量
Integer[] arr = new Integer[number];
for (int i = 0; i < number; i++) {
arr[i] = random.nextInt(number);
}
// 2.打印生成的数据
System.out.print("排前：");
for (Integer a : arr) {
System.out.print(a + " ");
}
System.out.println();
// 3.排序
double startTime = System.nanoTime(); // 排序时间用纳秒
BubbleSort.sort(arr);
double time = System.nanoTime() - startTime;
System.out.println("排序耗时："+time/1000000+"毫秒");
System.out.print("排序后：");
for (Integer a : arr) {
System.out.print(a + " ");
}
}测试结果：
java
排前：5 2 3 4 8 3 6 6 1 0
排序耗时：0.0206毫秒
排序后：0 1 2 3 3 4 5 6 6 8顺序数据下的冒泡排序改进
如果传入的是一个已经排好的数组，那么我们可以判断下，如果一整个循环都没有触发swap操作说明当前数组已经是排好序的数组
java
public static <E extends Comparable<E>> void sort2(E[] data) {
for (int i = 0; i < data.length - 1; i++) {
boolean isSwap = false;
for (int j = 0; j < data.length - i - 1; j++) {
if (data[j].compareTo(data[j + 1]) > 0) {
swap(data, j, j + 1);
isSwap = true;
}
}
if (!isSwap) {
break;
}
}
}测试
java
public static void main(String[] args) {
Random random = new Random();
int number = 10000; // 生成数据的数量
Integer[] arr = new Integer[number];
for (int i = 0; i < number; i++) {
arr[i] = random.nextInt(number);
}
double startTime = System.nanoTime();
BubbleSort.sort(arr);
double time = System.nanoTime() - startTime;
System.out.println("-----------随机数据-----------");
System.out.println("sort排序耗时："+time/1000000+"毫秒");
Integer[] arr2 = new Integer[number];
for (int i = 0; i < number; i++) {
arr2[i] = random.nextInt(number);
}
double startTime2 = System.nanoTime();
BubbleSort.sort2(arr2);
double time2 = System.nanoTime() - startTime2;
System.out.println("sort2排序耗时："+time2/1000000+"毫秒");
Integer[] arr3 = new Integer[number];
for (int i = 0; i < number; i++) {
arr3[i] = i;
}
double startTime3 = System.nanoTime();
BubbleSort.sort(arr3);
double time3 = System.nanoTime() - startTime3;
System.out.println("-----------顺序数据-----------");
System.out.println("sort排序耗时："+time3/1000000+"毫秒");
Integer[] arr4 = new Integer[number];
for (int i = 0; i < number; i++) {
arr4[i] = i;
}
double startTime4 = System.nanoTime();
BubbleSort.sort2(arr4);
double time4 = System.nanoTime() - startTime4;
System.out.println("sort2排序耗时："+time4/1000000+"毫秒");
}测试结果：
java
-----------随机数据-----------
sort排序耗时：792.3422毫秒
sort2排序耗时：659.3763毫秒
-----------顺序数据-----------
sort排序耗时：202.025毫秒
sort2排序耗时：0.2661毫秒测试结果分析
对于顺序数据，sort2相当于只经历过一次i循环，也就是最外层只循环了一次。对于随机数据，排序速度反而慢了下拉，因为每次交换都需要给isSwap赋值，速度自然慢了下来。
排序再优化
记录一轮交换后的最终索引，通过观察发现这个索引后的数字都是有序的，那么以后就不用比较这个索引后面的数字，即内层循环的边界是前面所说的最终索引。当这个最终索引为0的时候（即前面没有数字的时候）排序就结束了。
还是举个例子说明一下。来看下面这张图，第一行是原数组数据，按常规逻辑，第一次只能确定20的位置，但实际上我们可以肯定当12和13交换后，12之后的所有数据不需要再进行判断了，后面的数据都是顺序的了。
java
public static <E extends Comparable<E>> void sort3(E[] data) {
for (int i = 0; i < data.length - 1; i++) {
int lastSwappedIndex = 0;
for (int j = 0; j < data.length - i - 1; j++) {
if (data[j].compareTo(data[j + 1]) > 0) {
swap(data, j, j + 1);
lastSwappedIndex = j + 1;
}
}
i = data.length - lastSwappedIndex;
}
}测试
java
public static void main(String[] args) {
Random random = new Random();
int number = 10000; // 生成数据的数量
Integer[] arr = new Integer[number];
for (int i = 0; i < number; i++) {
arr[i] = random.nextInt(number);
}
double startTime = System.nanoTime();
BubbleSort.sort(arr);
double time = System.nanoTime() - startTime;
System.out.println("-----------随机数据-----------");
System.out.println("sort排序耗时："+time/1000000+"毫秒");
Integer[] arr2 = new Integer[number];
for (int i = 0; i < number; i++) {
arr2[i] = random.nextInt(number);
}
double startTime2 = System.nanoTime();
BubbleSort.sort3(arr2);
double time2 = System.nanoTime() - startTime2;
System.out.println("sort3排序耗时："+time2/1000000+"毫秒");
Integer[] arr3 = new Integer[number];
for (int i = 0; i < number; i++) {
arr3[i] = i;
}
double startTime3 = System.nanoTime();
BubbleSort.sort(arr3);
double time3 = System.nanoTime() - startTime3;
System.out.println("-----------顺序数据-----------");
System.out.println("sort排序耗时："+time3/1000000+"毫秒");
Integer[] arr4 = new Integer[number];
for (int i = 0; i < number; i++) {
arr4[i] = i;
}
double startTime4 = System.nanoTime();
BubbleSort.sort3(arr4);
double time4 = System.nanoTime() - startTime4;
System.out.println("sort3排序耗时："+time4/1000000+"毫秒");
}测试结果
java
-----------随机数据-----------
sort排序耗时：632.484毫秒
sort3排序耗时：258.515毫秒
-----------顺序数据-----------
sort排序耗时：276.1275毫秒
sort3排序耗时：0.2397毫秒