排序算法——冒泡排序
目录
🍉基本思想
🌰实例：
实现思路：
代码实现：
🍒优化
优化思路：
代码实现：
🥝算法性能分析:
空间复杂度：
时间复杂度：
稳定性：
🍍规则
🍉基本思想
冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后，依次比较相邻元素的值，若发现逆序（前者大于后者）就进行交换，使值较大的元素逐渐从前向后移动。
🌰实例：
原始数组：3 , 9 ，-1 , 10 ,20
实现思路：
第一趟排序：
（1）3, -1, 9, 10, 20
（2）3，-1, 9, 10, 20
（3）3，-1, 9，10, 20
（4）3，-1, 9，10, 20
第二趟排序：
（1）-1 , 3, 9, 10, 20
（2）-1, 3, 9, 10, 20
（3）-1, 3, 9, 10, 20
第三趟排序：
（1）-1, 3, 9, 10, 20
（2）-1, 3, 9, 10, 20
第四趟排序：
（1）-1, 3, 9, 10, 20
代码实现：
public static void main(String[] args) { int arr[]={3,9,-1,10,20}; int temp=0; for (int count=0;count<arr.length-1;count++){ for (int i=0;iarr[i+1]){ temp=arr[i+1]; arr[i+1]=arr[i]; arr[i]=temp; } } System.out.println("第"+(count+1)+"趟排序后的数组为："+Arrays.toString(arr)); } }运行结果：
🍒优化
优化思路：
因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说明序列有序，因此要在排序过程中设置一个标志flag，来判断元素是否进行过交换，从而减少不必要的比较。
代码实现：
public static void main(String[] args) { int arr[]={3,9,-1,10,20}; int temp=0; boolean flag=false;//标识变量，表示是否进行过交换 for (int count=0;count<arr.length-1;count++){ for (int i=0;i arr[i + 1]) { temp = arr[i + 1]; arr[i + 1] = arr[i]; arr[i] = temp; flag = true; } } if (flag==false){ break; }else { flag=false;//重置flag，进行下次判断 } System.out.println("第"+(count+1)+"趟排序后的数组为："+Arrays.toString(arr)); } }运行结果：
🥝算法性能分析:
空间复杂度：
仅使用了常数个辅助单元，因而空间复杂度为O（1）
时间复杂度：
- 当初始序列为顺序排列时，只需要遍历一趟，且没有元素交换，因此最好情况下的时间复杂度为O（n）
- 当初始序列为逆序排列时，就要遍历n-1趟，因此最坏情况下的时间复杂度为O(n^2）
平均时间复杂度为O（n^2）
稳定性：
冒泡排序是一个稳定的排序算法。
（所谓稳定的排序算法，是指当原始数据中存在多个相同的值时，在排序后，这些值的相对位置不变。）
🍍规则
- 一共进行数组元素个数-1次大的循环
- 每一趟排序的次数在逐渐的减少
- 如果我们发现在某趟排序中，没有发生过元素交换，就可以提前结束冒泡排序（即优化）
