一、算法描述
冒泡排序：比如在一个长度为N的无序数组中，在第一趟从第一个数据开始遍历，遇到比他大的(小的）,就交换位置，直到最大的（最小的）排到最后。第二趟找出倒二大的，N-1趟之后，数组有序。
二、算法分析
三种方法实现
1、暴力穷举-------- 没什么好说的
2、比如数组2 1 3 4 5 6 7 8 9，第一轮排序后变为1 2 3 4 5 6 7 8 9，后面所有排序都是白白浪费时间，所以，应该在数组已经有序了就停止排序，而判断的标志就是，某一趟排序没有交换。
3、比如数组6 5 2 3 1 4 7 8 9，第一轮排序后变为5 2 3 1 4 6 7 8 9，按照第前两种排序，第二轮排序将从第一个元素遍历到第n-1个元素，但其实从 ‘‘6‘’ 开始，数组后边已经有序，不需要载排序了，所以我们可以用一个变量记录下最后一个发生交换的位置，下一次遍历到这个数就可以了。
三、算法实现
- java实现代码：
package sort;
public class BubbleSort{
public static void main(String[] args) {
int[] arr = {8 , 4, 6, 2, 7, 3, 1, 9 ,5};
int[] result1 = bubbleSort1(arr);
show(result1);
int[] result2 = bubbleSort1(arr);
show(result2);
int[] result3 = bubbleSort1(arr);
show(result3);
}
/**
* 冒泡排序 从小到大排序 无优化
* @param arr
* @return
*/
public static int[] bubbleSort1(int[] arr) {
int n = arr.length;//长度
int temp = 0;//中间变量
for(int i = 0 ; i < n-1 ; i++) {
for(int j = 0 ; j < n-i-1 ; j++) {
//如果上边的泡泡更重(值更大)，则往下沉(交换)
if(arr[j]>arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
/**
* 冒泡排序 从小到大排序 优化一
* @param arr
* @return
*/
public static int[] bubbleSort2(int[] arr) {
int n = arr.length;//长度
int temp = 0;//中间变量
int count = 0;//计数器
for(int i = 0 ; i < n-1 ; i++) {
count = 0;//恢复为0
for(int j = 0 ; j < n-i-1 ; j++) {
//如果上边的泡泡更重(值更大)，则往下沉(交换)
if(arr[j]>arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
count++;//交换次数+1
}
}
if(count == 0) {//此轮排序无交换，数组已经有序
break;//退出循环
}
}
return arr;
}
/**
* 冒泡排序 从小到大排序 优化二
* @param arr
* @return
*/
public static int[] bubbleSort3(int[] arr) {
int n = arr.length;//长度
int temp = 0;//中间变量
int count = 0;//计数器
int k = n-1;//记录最后一次交换的位置,其后已经有序，初始值为n-1
int flag = 0;
for(int i = 0 ; i < n-1 ; i++) {
count = 0;//恢复为0
k = flag;
for(int j = 0 ; j < k ; j++) {
//如果上边的泡泡更重(值更大)，则往下沉(交换)
if(arr[j]>arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
count++;//交换次数+1
flag = j+1;
}
}
if(count == 0) {//此轮排序无交换，数组已经有序
break;//退出循环
}
}
return arr;
}
public static void show(int[] result) {
for(int i = 0 ; i < result.length ; i++) {
System.out.print(result[i]+" ");
}
System.out.println();
}
}
所有内容均个人编辑，如有错误，欢迎指正！
