本文先介绍排序算法，然后具体写冒泡排序。
目录
1.排序算法简介
2.常见的排序算法分类如下图：
3.冒泡排序：
1.介绍：
2.动态图解
3.举例
4.小结冒泡排序规则
5.冒泡排序代码
6.优化
7.优化后时间
代码：
运行结果：
1.排序算法简介
排序也称为排序算法。排序是将一组数据依据指定的顺序进行排列的过程。
分类：
内部排序：将需要处理的所有数据都加载到内存中进行排序。外部排序：数据量过大（比如10亿个数据），无法全部加载到内存中，就需要借助外部存储（文件、磁盘等）进行排序。先加载一部分，排序完之后再加载另外一部分进行排序，排序完再合并。
2.常见的排序算法分类如下图：
稳定性口诀：
选泡插，快归堆希桶计基，不稳稳稳不稳稳，不稳不稳稳稳稳
3.冒泡排序：
1.介绍：
数组中n个元素，从数组第一个元素开始到最后一个元素，依次比较相邻元素的值，如果如果左端元素大于右端元素就交换它们的位置，使得较大的元素在右边。这样数组最右端的元素就是数组中的最大元素。一轮之后就找到了n个元素中的最大元素，浮到整个数组最后一个位置。接着对左边n-1个元素也这样交换，找到这n-1个元素中的最大值，浮到整个数组的倒数第二个位置。依此类推。直到整个数组有序排列。
冒泡排序就是用相邻交换的方式把大的元素换到右边。
2.动态图解
3.举例
比如原始数组为：3，9，-1，10，20
第一趟排序：
（1）3，9，-1，10，20将3和9比较，不用交换
（2）3，-1，9，10，20将9和-1比较，要交换
（3）3，-1，9，10，20将9和10比较，不用交换
（4）3，-1，9，10，20将10和20比较，不用交换
第二趟排序：
（1）-1，3，9，10，20将3和-1比较，要交换
（2）-1，3，9，10，20将3和9比较，不用交换
（3）-1，3，9，10，20将9和10比较，不用交换
第三趟排序：
（1）-1，3，9，10，20将-1和3比较，不用交换
（2）-1，3，9，10，20将3和9比较，不用交换
第四趟排序：
（1）-1，3，9，10，20将-1和3比较，不用交换
由于5个数据中四个数据已经确定顺序，所以不需要第五趟排序。
4.小结冒泡排序规则
①数组元素个数为n，就一共进行n-1次大循环
②每一趟排序的次数逐渐减少
③如果我们发现在某趟排序中没有发生一次交换，可以提前结束冒泡排序，也就是冒泡排序的优化。
5.冒泡排序代码
package com.xjj.sort;
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int arr[]={3,9,-1,10,20};
BubbleSort(arr);
}
//为了例子写的原始写法，用于找规律
public static void BubbleSort1(int []arr){
int temp=0;
//第一趟排序
for(int j=0;j if(arr[j]>arr[j+1]){ temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } System.out.println("第1趟排序后的结果："+Arrays.toString(arr)); //第二趟排序 for(int j=0;j if(arr[j]>arr[j+1]){ temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } System.out.println("第2趟排序后的结果："+Arrays.toString(arr)); //第3趟排序 for(int j=0;j if(arr[j]>arr[j+1]){ temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } System.out.println("第3趟排序后的结果："+Arrays.toString(arr)); //第4趟排序 for(int j=0;j if(arr[j]>arr[j+1]){ temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } System.out.println("第4趟排序后的结果："+Arrays.toString(arr)); } //由于上面的一段代码在重复，只有可以arr.length-1后面减去的数字不同，正好是i，用for循环包括起来 //于是有了冒泡排序的代码 public static void BubbleSort(int []arr){ int temp=0; for(int i=0;i for(int j=0;j if(arr[j]>arr[j+1]){ temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } System.out.println("第"+(i+1)+"趟排序后的结果"+ Arrays.toString(arr)); } } //达到效果的另一种写法 public static void BubbleSort3(int []arr){ int temp=0; for(int i=arr.length-1;i>0;i--){ for(int j=0;j if(arr[j]>arr[j+1]){ temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } System.out.println("第"+(arr.length-i)+"趟排序后的结果"+ Arrays.toString(arr)); } } } 运行结果： 6.优化 因为在排序过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行过交换，那么说明这个序列是有序的。既然有序那后面还需要在一轮一轮比较吗？不需要吧。所以我们可以在排序过程中设置一个标注flag判断元素是否进行过交换，减少不必要的比较。 优化后代码： package com.xjj.sort; import java.util.Arrays; public class BubbleSort { public static void main(String[] args) { int arr[]={3,9,-1,10,20}; BubbleSort4(arr); } //用于优化冒泡排序代码 public static void BubbleSort4(int []arr){ int temp=0; boolean flag=false;//标识变量，表示是否进行过交换 for(int i=0;i for(int j=0;j if(arr[j]>arr[j+1]){ flag=true; temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } System.out.println("第"+(i+1)+"趟排序后的结果"+ Arrays.toString(arr)); if(!flag){//也就是flag为false，在一趟排序中一次交换都没有发生 break; } else{ flag=false;//重置flag进行下一次判断，不然flag还是true的话到!flag时就是直接false，不会break了 } } } } 运行结果： 可以看到优化后，排序趟数减少了 再使得数组中原本就有序：1，2，3，4，5 运行结果： 一趟就可以，是不是感觉效率高多了！ 7.优化后时间 插入段记录时间的代码。排序前记一次时间，排序后记一次时间。 然后输出元素的代码就先注释掉。 代码： package com.xjj.sort; import java.text.SimpleDateFormat; import java.util.Arrays; import java.util.Date; public class BubbleSort { public static void main(String[] args) { int arr[]={3,9,-1,10,20}; BubbleSort4(arr); //测试时间 int[] arr2=new int[80000]; for(int i=0;i<80000;i++){ arr2[i]=(int)(Math.random()*80000);//生成一个【0，80000】之间的随机数 } Date date1=new Date(); SimpleDateFormat simpleDateFormat=new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str=simpleDateFormat.format(date1); System.out.println("排序前的时间为："+date1Str); BubbleSort4(arr2); Date date2=new Date(); String date2Str=simpleDateFormat.format(date2); System.out.println("排序后的时间为："+date2Str); } //用于优化冒泡排序代码 public static void BubbleSort4(int []arr){ int temp=0; boolean flag=false;//标识变量，表示是否进行过交换 for(int i=0;i for(int j=0;j if(arr[j]>arr[j+1]){ flag=true; temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } // System.out.println("第"+(i+1)+"趟排序后的结果"+ Arrays.toString(arr)); if(!flag){//也就是flag为false，在一趟排序中一次交换都没有发生 break; } else{ flag=false;//重置flag进行下一次判断，不然flag还是true的话到!flag时就是直接false，不会break了 } } } } 运行结果： 80000个元素，优化后的冒泡排序运行时间8秒。 后面会继续写选择排序、插入排序等排序算法的内容。分类排序部分写完之后再给出一些题目练习^_^加油加油 精彩链接
发表评论