冒泡排序,即一个无序的数组中,经过处理的数组后面的元素比前一个大。
int[] arr = new int[]{6, 2, 1, 3, 5, 4};
判断条件
arr[j] < arr[j + 1]
要做到这个,在程序中实现需要通过循环外加一个临时变量来处理
if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;
}
考虑到数组里的元素顺序发生变化,一般一次完整下来无法达到目的,数组 arr 一个完整循环排序下来的结果是
[2, 1, 3, 5, 4, 6]
显然1和2,5和4还不能满足,所以需要一个外层循环来处理这个问题
for (int i = 0; i < arr.length; i++) {for (int j = 0; j < arr.length - 1; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}
}
至此,一个简单的冒泡排序结束。
看一下哪里可以有优化的地方
从循环次数入手
发现外层循环总共30次。循环次数多意味着计算量大,消耗cpu高
减少外层循环次数
外层循环第一次排序后的数组依次为
[2, 6, 1, 3, 5, 4]
[2, 1, 6, 3, 5, 4]
[2, 1, 3, 6, 5, 4]
[2, 1, 3, 5, 6, 4]
[2, 1, 3, 5, 4, 6]
即6个元素遍历了5次,有一次不用循环
for (int i = 0; i < arr.length-1; i++) {for (int j = 0; j < arr.length - 1; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}
}
这次循环次数为25次,(30-25)/30*100≈17%,即提升了 17%。
鉴于第一次外层循环结束后,数组最后一个值是最大的,接下来下来只需要对前面的5个元素进行比较
内层循环在现有的基础上减少外层循环次数
在上面优化的基础上,在外层循环的基础上数组后面的大小都是已经固定的。接下来每次外循环下来内循环只需要对数组未进行正常排序的进行处理即可。
for (int i = 0; i < arr.length -1; i++) {int len = arr.length - 1 -i;for (int j = 0; j < len; j++) {// 5 > 3if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}
}
这次循环次数为15次,(30-15)/30*100=50%,即相对原始算法提升了 50%,相对于第一次优化后 (25-15)/25=40%,即提升了40%。
这是这两种都无法解决重复判断的问题
把内循环的判断提到 for 循环条件上
代码如下
for (int i = 0; i < arr.length -1; i++) {int len = arr.length - 1 -i;for (int j = 0; j < len && arr[j] > arr[j + 1]; j++) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}
}
这次循环次数为6次,解决了重复循环的问题,(30-6)/30*100=80%,即相对原始算法提升了 80%,相对于第二次优化后 (15-6)/15=60%,即提升了60%。