冒泡排序，你真的会吗？

数据结构与算法，想必大家是处于既快乐又痛苦的感觉

快乐在于做出题目后的喜悦

痛苦在于绞尽脑汁却无可奈何

今天说的是冒泡排序

冒泡排序可以说是非常基础了

但是开始学的时候，好像很快就明白了原理

但过了一段时间又给忘记了

不知道你们会不会有这样一种感觉呢？

其实就是没有真正的理解

大家都知道，冒泡排序的时间复杂度为O² 其实就是两次循环就行了

我们不能死记硬背

思路是这样的

按从大到小排列的话，找到最大的。下次循环就不需要看最大元素了

所以大循环是递减的

小循环跟随大循环递增

以arr表示某个数组

for(int i=arr.length-1;i>0;i--){         for(int j=0;jarr[j+1]){             //交换                 //int temp=arr[j];                 //arr[j]=arr[j+1];                 //arr[j+1]=temp;  }         }}         12345678910

其实我认为核心的不是这个交换算法，而是for循环的终止条件

否则很容易出现数组越界

i>0，原先认为，应该是i>=0，其实最后一次循环是没有必要的

因为倒数第二小的元素已经找到后，剩下的元素必定是最小的，放在第一位

第二个j

之前我考虑到j+1会使得数组越界，但发现多虑了

因为j是随着i走的，i最大正好是数组最大下标 j

j最大是与i相差一个单位 j+1就与i相等，不会导致数组越界

有时我们应该关注这些细节的部分，这些细节部分，才是让我们真正成长的

冒泡可以在循环里加一个判断，当前面元素没有大于后面元素时，则跳出循环 不进行后面的比较了，稍微节省了些步骤

当然冒泡是比较初级的，但也是学习的基础，要好好学习。

public static void sort1_2(int[] arr) {         int c=0;         boolean flag=false;         for (int i = arr.length-1; i >0; i--) {             for (int j = 0; j arr[j+1]){                     flag=true;                     arr[j]^=arr[j+1];                     arr[j+1]^=arr[j];                     arr[j]^=arr[j+1];                 }             }             if(!flag){                 break;             }else {                 flag=false;             }         }         System.out.println(Arrays.toString(arr)+"  "+c);     }