排序–冒泡排序
- 2019 年 10 月 20 日
- 笔记
1、什么是冒泡排序?
就是把一个无序数组内的元素，从头开始，两两比较并交换位置，直到把最大（最小）的一位放置在队尾
2、代码原理：
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。
3、代码实现
public class ArrSort { public static void main(String[] args) { int[] arr={3,9,-1,10,20}; int temp=0; for (int j=0;j<arr.length-1;j++){ //第i遍 for (int i=0;i<arr.length-1-j;i++){ if (arr[i]>arr[i+1]){ //左边元素比右边大就交换位置 temp=arr[i]; arr[i]=arr[i+1]; arr[i+1]=temp; } } System.out.println("第"+j+"次排序"); System.out.println(Arrays.toString(arr)); } } }
4、优化
按照上述的代码，每次排序都要进行arr.length-1轮，但是有可能前面几轮就已经达到排序好的效果，后面做的就是无用功
如图第二轮已经达到排序完成的效果，怎么优化？
加一个判定条件，如果没有发生元素的交换，就说明已经排序完成了
public class ArrSort { public static void main(String[] args) { int[] arr={3,9,-1,10,20}; int temp=0; //设置一个开关 boolean flag=false; for (int j=0;j<arr.length-1;j++){ //第一遍 for (int i=0;i<arr.length-1-j;i++){ if (arr[i]>arr[i+1]){ //发生元素交换就置为true，这一轮完成后再判断 flag=true; temp=arr[i]; arr[i]=arr[i+1]; arr[i+1]=temp; } } if (flag){ //说明发生了元素交换，继续进行下一轮 System.out.println("第"+j+"次排序"); System.out.println(Arrays.toString(arr)); flag=false; //再把flag置为初始值 }else{ //没有进行元素交换，就跳出循环条件，排序完成 System.out.println("排序结束"); break; } } } }
5、时间复杂度
由上述代码可发现，冒泡排序是用了双层for循环，所以O（n^2）
