冒泡排序(时间复杂度分析)_冒泡排序时间复杂度怎么计算

冒泡排序:

public static void bubbleSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }
        for(int e = arr.length-1; e > 0; e--) {
            for(int i = 0; i < e; i++) {
                if(arr[i] > arr[i+1]) {
                    swap(arr, i, i+1);
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

冒泡排序一共要进行(n-1)次循环,每一次循环都要进行当前n-1次比较
所以一共的比较次数是:
(n-1) + (n-2) + (n-3) + … + 1 = n*(n-1)/2;
所以冒泡排序的时间复杂度是 O(n²)