冒泡排序
学习目标：掌握冒泡排序算法的原理和思想
一、前提知识
排序算法概念、时间复杂度。可前往此网址 排序算法学习01_算法基础介绍阅读
二、冒泡排序介绍
冒泡排序是属于交换排序中的一种简单的排序，它会重复地走访要排序的数列，比较时，一次比较两个元素，如果符合条件则交换，每经历一次重复访问，数列中所有元素都会接近自己的位置，且必然有一个元素是已经排列完的。
该算法名字的由来也是因为这个，在一次排列中，所有元素慢慢靠近自己的位置，就像水底下的气泡逐渐往上冒一样
三、冒泡排序设计思想
通过介绍我们了解，冒泡排序每要排序一次时都会重复走访要排序的元素也就是说
- 需要控制两个循环，最里层的循环用来实现访问要排序的元素，最外层则是一个决定重复执行几次
比较时一次比较两个元素，则
- 只需要一个临时变量来辅助交换
每进行一次重复访问，数列中最后一个元素肯定是最大/最小的，那么
- 我们就不需要再判断到已经排序好的后面的元素了
四、冒泡排序实例
要求对以下这个数列进行递增排序：{3，2，5，1，7，9，8}
package com.migu.sortingAlgorithm;
/**
*冒泡排序
*/
public class BubbleSort {
public static void main(String[] args) {
int a[] = {3,2,5,1,7,9,8};
// 数列有7个元素，那么根据冒泡算法该数列需要重复执行6次，即可让所有元素都排序到所规定位置，所以对其-1
for(int i = 0;i < a.length-1;i++){
// 为什么(a.length-1)，我们这是通过数组的来比较，在比较时是通过数组索引+1。只需判断到倒数第二位，即可得到倒数第一位
// 否则数组越界会产生ArrayIndexOutOfBoundsException
// 不需要再判断已经排序好的元素了，所以可以减去-i
for(int j = 0;j < (a.length-1)-i;j++){
if(a[j] > a[j+1]){
int temp = a[j]; // 建立临时变量来辅助操作，保存谁都可以，达成交换目的即可
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
for(int i : a){
System.out.printf("%d ",i);
}
}
}
在这里插入图片描述
五、冒泡排序的优化
通过介绍我们了解，冒泡排序会重复访问要排序数列，那么如果它某一次在重复访问时，并没有产生排序，那就说明，该数列已是有序的，不需要再对他进行重复的排序。所以我们可以加一个标记
package com.migu.sortingAlgorithm;
/**
*冒泡排序优化
*/
public class BubbleSort {
public static void main(String[] args) {
int a[] = {3,2,5,1,7,9,8};
boolean flag = true; // 用于标记
for(int i = 0;i < a.length;i++){
for(int j = 0;j < (a.length-1)-i;j++){
if(a[j] > a[j+1]){
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
flag = false; // 当在某一次循环中，并没有执行到此代码，则可以提前结束排序
}
}
if(flag == false){
flag = true; // 再次置位true，来看看下一次循环是否还变成false，如果没有则Over
}else {
break;
}
}
// 遍历排序后的循环
for(int i : a){
System.out.printf("%d ",i);
}
}
}
六、冒泡排序的时间复杂度
讨论一个算法的时间复杂度，一般都是看最坏的情况：
通过代码可直接看出，冒泡排序算法的时间复杂度为O(n^2)
如果你看不出来的话，试想当数组的元素为1000个时，里层的循环是否要重复遍历1000次，则1000^2为100万，就算慢慢减去已遍历完的值，最坏的情况是否大概需要执行50多万次。
如果运气好到爆棚的话，就是线性阶了也就是O(n)，不过你觉得在实际开发中可能吗~~~~
七、总结
使用冒泡排序算法每进行一次重复访问排序时，数列中所有元素都会逐渐接近自己所需处的位置【朝数列末尾靠近】，且必然有一个元素是已经排列完的
