为什么冒泡排序的最好情况是O的时间复杂度（N）(why is the time complexity

我按照书算法 2.2使用的评判推断冒泡排序的时间复杂度在最好的情况下。但得到的答复竟然是为O（n ^ 2）。

这里是我的推导，希望有人能帮助我找出错误的是：

public void bubbleSort(int arr[]) {
for(int i = 0, len = arr.length; i < len - 1; i++) {
    for(int j = 0; j < len - i - 1; j++) {
        if(arr[j + 1] < arr[j])
            swap(arr, j, j + 1);
    }
}

}

Statements                      cost    times
i = 0,len = arr.length          c1          1
i < len - 1                     c2          n
i++                             c3          n - 1
j = 0                           c4          n - 1
j < len - i - 1                 c5          t1(i=0) + t1(i=1) + ... + t1(i = n-2)
j++                             c6          t2(i=0) + t2(i=1) + ... + t2(i = n-2)
arr[j + 1] < arr[j]             c7          t3(i=0) + t3(i=1) + ... + t3(i = n-2)
swap(arr, j, j + 1)             c8          t4(i=0) + t4(i=1) + ... + t4(i = n-2)

T（N）= C1 + C2N + C3（N - 1）+ C4（N - 1）+ c5t5 + c6t6 + c7t7 + c8t8 = C1 + C2N + C3（N - 1）+ C4（N - 1）+ C5 [T1（I = 0）+ T1（I = 1）+ ... + T1（I = N-2）] + C6 [T2（I = 0）+ T2（I = 1）+ ... + T2 （I = N-2）] + C7 [T3（I = 0）+ T3（I = 1）+ ... + T3（I = N-2）] + C8 [T4（I = 0）+ T4（ I = 1）+ ... + T4（I = N-2）];

在最佳投，序列已经在排序前积极。然后T8是前人的精力0。

T（N）= C1 + C2N + C3（N - 1）+ C4（N - 1）+ C5 [T1（I = 0）+ T1（I = 1）+ ... + T1（I = N-2 ）] + C6 [T2（I = 0）+ T2（I = 1）+ ... + T2（I = N-2）] + C7 [T3（I = 0）+ T3（I = 1）+。 .. + T3（I = N-2）]

的时间复杂度是O（n ^ 2）

Answer 1:

你的实现

public void bubbleSort(int arr[]) {
    for(int i = 0, len = arr.length; i < len - 1; i++) {
        for(int j = 0; j < len - i - 1; j++) {
            if(arr[j + 1] < arr[j])
                swap(arr, j, j + 1);
        }
    }
}

缺乏是否有在内部循环的任何交换，断裂出外部循环，如果没有的控制。

该控制使得可能的是，最好的情况下（一个已排序阵列）为O（n）中，由于再有在内部循环没有互换当它运行在第一时间。

public void bubbleSort(int arr[]) {
    boolean swapped = true;
    for(int i = 0, len = arr.length; swapped && i < len - 1; i++) {
        swapped = false;
        for(int j = 0; j < len - i - 1; j++) {
            if(arr[j + 1] < arr[j]) {
                swap(arr, j, j + 1);
                swapped = true;
            }
        }
    }
}

Answer 2:

我不知道你有什么计数。在一般情况下，当你在谈论比较排序算法，你应该算进行的比较的数量。冒泡排序被认为是这样的。在这种情况下，你提出的算法是O（n ^ 2）。

如果算上交换数目的O（1），或者甚至可以说O（0）。然而罕见分析冒泡排序这样的。

不过你可以很容易提高泡到最好的情况下得到O（N）。通过引入一个标志例如swap_was_made 。如果其在内部月底假for就可以完成。上最好的情况下，将削减的复杂性O（N）（一个内for循环）。在公平的均匀分布的情况下，它减少的预期或平均复杂度为O（N ^ 2/2）......但是，请仔细检查我上我可能是错的。这里没有做数学题。