常见排序算法-----冒泡排序

时间复杂度：O(n^2)，最优时间复杂度：O(n)，平均时间复杂度：O(n^2)

最外层控制总共要找多少次最大值比如 5个数要找4个最大值最外层要循环四次

内层为找一次最大值需要循环的次数

 1 // 冒泡排序
 2     public void BubbleSortSolution(int[] arr) {
 3 
 4         for (int i = 0; i < arr.length-1; i++) {
 5             for (int j = 0; j < arr.length-1-i; j++) {
 6                 if(arr[j] > arr[j+1]){
 7                     int temp = arr[j];
 8                     arr[j] = arr[j+1];
 9                     arr[j+1] = temp;
10                 }
11             }
12         }
13 }

冒泡排序的改进算法

改进一添加标识符每次进入内循环之前将标识符设置为false 若内循环发生交换将标识符设置为true ，若不发生交换说明从当前位置开始一致到最后已经是有序的不需要在进行排序

 1 public void bubbleSort2(int[] arr) {
 2 
 3         for (int i = 0; i < arr.length - 1; i++) {
 4             boolean isSorted = true;
 5             for (int j = 0; j < arr.length - i - 1; j++) {
 6                 if (arr[j] > arr[j + 1]) {
 7                     int temp = arr[j];
 8                     arr[j] = arr[j + 1];
 9                     arr[j + 1] = temp;
10                     isSorted = false;
11                 }
12             }
13             if (isSorted) {
14                 break;
15             }
16         }
17     }

改进算法二

 1     public void bubbleSort3(int[] arr) {
 2         // 记录下最后一次交换的位置
 3         boolean flag = true;
 4         for (int i = 0; i < arr.length - 1 && flag; i++) {
 5             boolean isSorted = true;
 6             int laseChangeIndex = 0;
 7             int sortBorder = arr.length - 1;;
 8             for (int j = 0; j < sortBorder; j++) {
 9                 if (arr[j] > arr[j + 1]) {
10                     int temp = arr[j];
11                     arr[j] = arr[j + 1];
12                     arr[j + 1] = temp;
13                     isSorted = false;
14                     laseChangeIndex = j;
15                 }                
16             }
17             sortBorder = laseChangeIndex;
18             if (isSorted) {
19                 break;
20             }
21         }
22 
23     }