我们知道一般的冒泡排序是指：
1、将一个数与它后面的那一个数进行比较，如果前面>后面，则两者交换位置。
2、对数组中的每一个数都进行这样的操作，一个循环下来最大的数值就会到达数组的最后面。
3、再将数组范围缩小一个（即再次比较时不看数组最后且最大的那个），再次循环上面的步骤。
（因为1，2，3，6，1在12循环后是1,2,3,1,6 如果不继续进行循环，则答案错误）
当数组的范围缩小到只剩下一个数的时候，那么数组就已经有序了，冒泡排序结束。
代码一：冒泡排序原始解决方案
public static void sortFunc1(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
for (int i = arr.length - 1; i > 0; i--) { //第一循环：在将数组最大的值放在最后的时候，逐渐缩小范围
for (int j = 0; j < arr.length - 1; j++) { //第二循环：判断当前数组范围中的每一个数的顺序是否正确
if (arr[j] > arr[j + 1]) {
swap(arr, j + 1, j);
}
}
}
}
虽然说到这儿冒泡排序就已经完成了，但是实际上这个算法还有很多可以优化的空间，简单举两个例子来说：
一、如果在某个循环中，数组已经排好序了，但是数组范围并没有缩小到1
首先应该明确什么时候数组是以及排好序了的：发现数组中所有的数值两两之间并不交换，就可以判断数组已经排好序了，或者数组大小缩减为1。
然后，这种情况如果出现，如果按照最初始的办法是还要继续进行第一循环判断的，这无疑是极大的时间浪费。
这时候我们可以设置一个判断符，判断在第二循环中是否存在这种排好序且数组范围没有缩小到1的情况出现。
代码二：优化代码
public static void sortFunc2(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
boolean flage = true;
while (flage) {
flage = false;
for (int i = arr.length - 1; i > 0; i--) {
for (int j = 0; j < arr.length - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j + 1, j);
flage = true;
}
}
}
}
} 整体思路就是添加一个flage判断符，每次循环都设置为false，如果一个循环中出现两个数之间交换的情况，那么就置为true，否则代表上一个循环中没有任何交换产生，数组已经排好序了，标志符置为false，结束循环
二、如果某个数组中前200是无序的，后10000是有序的，且都大于前200个数
虽然上一个算法以及在初始的基础上进行了优化，但是在遇到这种情况的时候依旧不能够很好的处理，因为我们只是判断了数组在第二循环中是否已经排好了序，并没有判断数组从哪一位开始是有序的。
所以这种情况我们应该解决的问题是：如何判断数组从某一位开始是有序的。
解决这个问题的方法和前一种方法其实是相差不多的，在循环之中，如果数组中的数值两两交换，则代表当下这两个数以前是无序的（如果要更精确一点的话，应该是这两个数的前一个数到数组第一个数可能无序，（比如1，2，3，6，1，8, 9,10在12循环后是1,2,3,1,6，8,9,10）），所以只需要在每次交换数值的时候记录下当前的位置，在进行下一次第一循环的时候从记录的位置开始。
代码三：进一步优化代码
public static void sortFunc3(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
int flage = arr.length - 1;
while(flage > 0) {
int end = flage;
flage = 0;
for (int j = 0; j < end; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j + 1, j);
flage = j; //记录所交换的两个数的前一个
}
}
}
}
附加swap()
public static void swap(int[] arr, int i, int j) {
arr[i] = arr[i]^arr[j];
arr[j] = arr[i]^arr[j];
arr[i] = arr[i]^arr[j];
}
京公网安备 11010502036488号