java 冒泡排序

思路

1. 将序列当中的左右元素，依次比较，保证右边的元素始终大于左边的元素；（ 第一轮结束后，序列最后一个元素一定是当前序列的最大值；）
2. 对序列当中剩下的n-1个元素再次执行步骤1。
3. 对于长度为n的序列，一共需要执行n-1轮比较

时间复杂度

最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

代码

1import java.util.Arrays;
2
3/**
4 * 冒泡排序
5 * @author remainsu
6 * @version 1.0 2019-05-29
7 */
8public class BubbleSort {
9
10    /**
11     * 排序方法
12     * @param arr 要排序的数组
13     * @return toString 方便输出
14     */
15    public static String bubbleSort(int[] arr) {
16
17        int tmp;
18        //int count = 0;
19        // 冒泡次数
20        for(int a=0; a<arr.length-1; a++ ) {
21            
22            //count = a+1;
23            boolean flag = false;
24            // 比较未移动的
25            for(int b=0; b<arr.length-a-1; b++ ) {
26                // 后面的小于前面的，则互换位置
27                if(arr[b+1] < arr[b]) {
28                    tmp = arr[b];
29                    arr[b] = arr[b+1];
30                    arr[b+1] = tmp;
31                    
32                    //有数据移动，则状态标位true
33                    flag = true;
34                }
35            }
36            //没有数据移动，即数组已经有序，直接退出
37            if(!flag) break;
38        }
39        
40        //System.out.println("冒泡的次数："+ count);
41        return Arrays.toString(arr);
42    }
43    
44    public static void main(String[] args) {
45        
46        int[] arr = {111, 3, 5, 52, 74, 312, 75, 3, 764, 3, 2111, 7, 31};
47        //int[] arr = {1,2,10,3,4,5,6,7,8,9};
48        
49        System.out.println("排序后的数组："+ bubbleSort(arr));
50    }
51    

参考

1. https://blog.csdn.net/hellozhxy/article/details/79911867