本文先介绍排序算法，然后具体写冒泡排序。
目录
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<arr.length-1;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<arr.length-1-1;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<arr.length-1-2;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<arr.length-1-3;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<arr.length-1;i++){
for(int j=0;j<arr.length-1-i;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<i;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<arr.length-1;i++){
for(int j=0;j<arr.length-1-i;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<arr.length-1;i++){
for(int j=0;j<arr.length-1-i;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秒。
后面会继续写选择排序、插入排序等排序算法的内容。分类排序部分写完之后再给出一些题目练习^_^加油加油
