冒泡排序是一种基础的交互排序，每一个元素根据自身大小，一点点地向着数组一侧移动。比如有数字无序数列{4,3,2,1}，按照从小到大的顺序排列。按照冒泡排序的思想， 我们要把相邻的元素两两比较， 当一个元素大于右侧相邻元素时， 交换它们的位置； 当一个元素小于或等于右侧相邻元素时， 位置不变。
思路：
通过两个元素相互比较，当元素大于右侧元素时，交换位置，通过一次循环就可以将最大的值移动到数组的最右端；这仅仅将最大的值移动到数组最右端，还有其他的元素并未排序，所以我们还需要从头开始进行比较，将其他元素进行排序，不考虑性能的情况下，还需要进行数组长度-1次的循环，也就是需要双循环。那么内循环用来进行元素比较并交互位置，外循环则是需要进行内循环的次数。
冒泡排序.gif
**** 算法
/**
* 此排序是一种稳定排序，值相等的元素并不会打乱原本的顺序。
* @param arr
*/
private static void sort_1(int[] arr){
int count = 0;
for (int i = 0; i < arr.length - 1 ; i++) {
for (int j = 0; j < arr.length - 1; j++) {
System.out.println("外层循环i:"+i+" 内层循环j:"+j);
System.out.println("比较元素的位置: ["+j+"] vs ["+(j + 1)+"]");
int temp = 0;
if (arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
count = count +1;
System.out.println("数组:"+ Arrays.toString(arr));
}
}
System.out.println("循环次数:"+count);
}
控制台：
数组:[4, 3, 2, 1]
外层循环i:0 内层循环j:0
比较元素的位置: [0] vs [1]
数组:[3, 4, 2, 1]
外层循环i:0 内层循环j:1
比较元素的位置: [1] vs [2]
数组:[3, 2, 4, 1]
外层循环i:0 内层循环j:2
比较元素的位置: [2] vs [3]
数组:[3, 2, 1, 4]
外层循环i:1 内层循环j:0
比较元素的位置: [0] vs [1]
数组:[2, 3, 1, 4]
外层循环i:1 内层循环j:1
比较元素的位置: [1] vs [2]
数组:[2, 1, 3, 4]
外层循环i:1 内层循环j:2
比较元素的位置: [2] vs [3]
数组:[2, 1, 3, 4]
外层循环i:2 内层循环j:0
比较元素的位置: [0] vs [1]
数组:[1, 2, 3, 4]
外层循环i:2 内层循环j:1
比较元素的位置: [1] vs [2]
数组:[1, 2, 3, 4]
外层循环i:2 内层循环j:2
比较元素的位置: [2] vs [3]
数组:[1, 2, 3, 4]
循环次数:9
**** 算法2
算法1时可以再优化的，观察算法1的日志，我们可以发现经过第一轮的排序后，最大值4移动到数组最右端；进行第二轮的排序，因为4已经是最大的值了，没必要再跟其前面的值比较了，所以这部分可以优化，也就是每一轮排序后会出现一个有序区域，有序区域的就不必比较了。也就是内层循环要去除有序区域，也就是j < arr.length - i - 1
private static void sort_1(int[] arr){
int count = 0;
for (int i = 0; i < arr.length - 1 ; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
System.out.println("外层循环i:"+i+" 内层循环j:"+j);
System.out.println("比较元素的位置: ["+j+"] vs ["+(j + 1)+"]");
int temp = 0;
if (arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
count = count +1;
System.out.println("数组:"+ Arrays.toString(arr));
}
}
System.out.println("循环次数:"+count);
}
控制台：
数组:[4, 3, 2, 1]
外层循环i:0 内层循环j:0
比较元素的位置: [0] vs [1]
数组:[3, 4, 2, 1]
外层循环i:0 内层循环j:1
比较元素的位置: [1] vs [2]
数组:[3, 2, 4, 1]
外层循环i:0 内层循环j:2
比较元素的位置: [2] vs [3]
数组:[3, 2, 1, 4]
外层循环i:1 内层循环j:0
比较元素的位置: [0] vs [1]
数组:[2, 3, 1, 4]
外层循环i:1 内层循环j:1
比较元素的位置: [1] vs [2]
数组:[2, 1, 3, 4]
外层循环i:2 内层循环j:0
比较元素的位置: [0] vs [1]
数组:[1, 2, 3, 4]
循环次数:6
**** 算法3
/**
* 数组举例：{7,1,2,3,4,5,6}
* 优化策略：减少循环比较趟数
* 增加一个标记(isSorted,默认是true),每次发生交换，说明目前数组还是无序的，isSorted置为false,
* 如果这趟循环没有发生交换，说明目前数组已经是有序的了，那么剩下的几趟排序都不需要执行了，提前结束。
* @param arr
*/
private static void sort_2(int[] arr){
for (int i = 0; i < arr.length - 1 ; i++) {
//数组有序标记位，默认为true,假设是有序的，发生交换就会标记为无序
boolean isSorted = true;
for (int j = 0; j < arr.length - i - 1; j++) {
int temp = 0;
if (arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
//因为有元素进行交换，数组不是有序的，标记为false
isSorted = false;
}
}
if (isSorted) break;
}
}
**** 算法4
/**
* 优化策略：减少每趟的循环次数
* 情景：每次循环后，右面的很多元素已经是有序的，算法还是会循环比较有序的元素
* 优化：定义无序数组的边界，每次比较到边界为止，不进行后面的比较了。
*/
private static void sort_3(int[] array){
// 最后一次交换的下标
int lastSwapIndex = 0;
// 无序数组的边界，每次比较比到这里为止
int arrBoundary = array.length - 1;
for (int i = 0; i < array.length - 1; i++) {
// 数组有序标记位，默认为true,假设是有序的，发生交换就会标记为无序
boolean isSorted = true;
for (int j = 0; j < arrBoundary; j++) {
if (array[j] > array[j + 1]) {
int temp = 0;
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
// 因为有元素进行交换，数组不是有序的，标记为false
isSorted = false;
// 最后一次交换元素的位置
lastSwapIndex = j;
}
}
// 把最后一次交换元素的位置赋值给无序数组的边界
arrBoundary = lastSwapIndex;
// 说明上面内层for循环中，没有交换任何元素，直接跳出外层循环
if (isSorted) {
break;
}
}
}
**** 算法5
/**
* 优化策略：减少内存开销
* 情景：每次循环都会创建temp这个变量
* 优化：通过异或操作来交换两个元素位置
*/
private static void sort_4(int[] array){
// 最后一次交换的下标
int lastSwapIndex = 0;
// 无序数组的边界，每次比较比到这里为止
int arrBoundary = array.length - 1;
for (int i = 0; i < array.length - 1; i++) {
// 数组有序标记位，默认为true,假设是有序的，发生交换就会标记为无序
boolean isSorted = true;
for (int j = 0; j < arrBoundary; j++) {
if (array[j] > array[j + 1]) {
array[j + 1] ^= array[j];
array[j] ^= array[j + 1];
array[j + 1] ^= array[j];
// 因为有元素进行交换，数组不是有序的，标记为false
isSorted = false;
// 最后一次交换元素的位置
lastSwapIndex = j;
}
}
// 把最后一次交换元素的位置赋值给无序数组的边界
arrBoundary = lastSwapIndex;
// 说明上面内层for循环中，没有交换任何元素，直接跳出外层循环
if (isSorted) {
break;
}
}
}
