冒泡排序||Bubble Sort
自我学习总结之冒泡排序(bubble sort)
what？
这个算法的名字由来是因为越小/大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”
摆原理
1、从第一个元素开始，比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。此时，最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后排好的元素。
4、重复以上步骤，知道所有元素有序。
假如现有数组：int[] array = new int[] {
9,8,7,6,5,4,3,2,1,0};
经过冒泡排序：
第0次排序:9 8 7 6 5 4 3 2 1 0
第1次排序:8 7 6 5 4 3 2 1 0 9
第2次排序:7 6 5 4 3 2 1 0 8 9
第3次排序:6 5 4 3 2 1 0 7 8 9
第4次排序:5 4 3 2 1 0 6 7 8 9
第5次排序:4 3 2 1 0 5 6 7 8 9
第6次排序:3 2 1 0 4 5 6 7 8 9
第7次排序:2 1 0 3 4 5 6 7 8 9
第8次排序:1 0 2 3 4 5 6 7 8 9
第9次排序:0 1 2 3 4 5 6 7 8 9
在0和1次排序之间详细过程为：
第0_0次排序:9 8 7 6 5 4 3 2 1 0
第0_1次排序:8 9 7 6 5 4 3 2 1 0
第0_2次排序:8 7 9 6 5 4 3 2 1 0
第0_3次排序:8 7 6 9 5 4 3 2 1 0
第0_4次排序:8 7 6 5 9 4 3 2 1 0
第0_5次排序:8 7 6 5 4 9 3 2 1 0
第0_6次排序:8 7 6 5 4 3 9 2 1 0
第0_7次排序:8 7 6 5 4 3 2 9 1 0
第0_8次排序:8 7 6 5 4 3 2 1 9 0
第0_9次排序:8 7 6 5 4 3 2 1 0 9
上代码
public void bubbleSort(int[] array) {
for (int i = 0; i < array.length-1; i++) {
for (int j = 0; j < array.length-i-1; j++) {
if (array[j]>array[j+1]) {
int temp = array[j];array[j] = array[j+1];array[j+1] = temp;}}}
｝
时间复杂度
百度百科上说的很好，直接引进来：
稳定性
当比较的两个数相等时，不会发生交换，所以相等的两个数相对顺序没变，所以冒泡排序是一种稳定排序算法。
优化
假如初始数组就是有序的，但是按照上述代码我们还是要比较n-1次，针对这个问题我们进行优化。
解决方案：
1、设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。
2、这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。
优化后代码：
public static void Sort(int[] array) {
boolean flag;// 是否交换的标志for (int i = 0; i < array.length - 1; i++) {
flag = false;// 每次遍历标志位都要先置为false，才能判断后面的元素是否发生了交换for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;flag = true;//只要有发生了交换，flag就置为true}}if (!flag) break; // 判断标志位是否为false，如果为false，说明后面的元素已经有序，就直接return}}