小编One*_*o12的帖子

据我所知,算法的复杂性是排序时执行的最大操作数.因此,冒泡排序的复杂性应该是算术级数(从1到n-1)的总和,而不是n ^ 2.以下实现计算比较次数:

public int[] sort(int[] a) {
    int operationsCount = 0;
    for (int i = 0; i < a.length; i++) {
        for(int j = i + 1; j < a.length; j++) {
            operationsCount++;
            if (a[i] > a[j]) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
    System.out.println(operationsCount);
    return a;
}

具有10个元素的数组的输出为45,因此它是从1到9的算术级数之和.

那么为什么Bubble sort的复杂性是n ^ 2,而不是S(n-1)？