两种不同的冒泡排序解决方案的时间复杂度

Question

我通过两种方式为Bubble排序提供了解决方案。每次都是从头到尾检查。另一个也在从头到尾进行检查，但是“两端”越来越小（-1）。因为我们可以确保在每个循环完成后对最后一个进行排序。

我认为，第一个的时间复杂度为O（n ^ 2），另一个的时间复杂度为O（nlogn）。是吗？

第一

var bubbleSort = function(array) {
    // Your code here.

    let changed = true;
    let temp;
    while(changed){
      changed = false
      for(let i=0 ; i<array.length-1 ; i++){
        if(array[i] > array[i+1]){
          temp = array[i+1];
          array[i+1] = array[i];
          array[i] = temp;
          changed = true;
        }
      }
    }
    return array;

};

秒

var bubbleSort = function(array) {
    // Your code here.
    let temp;

    for(let i=0 ; i<array.length-1 ; i++){
      for(let j=0 ; j<array.length-1-i ; j++){
        if(array[j]>array[j+1]){
          temp = array[j+1];
          array[j+1] = array[j];
          array[j] = temp;
        }
      }
    }
    return array;
};

Answer 1

在最坏的情况下和在平均情况下，气泡排序的两个版本均为O（n²）。

第一个版本，我称为“幼稚泡沫排序”，具有一个外部循环和一个内部循环。内循环迭代n-1次，外循环也迭代n-1次。这个事实可以证明是第二个版本（外部循环限于n-1个迭代）正确的事实的推论。因此，最坏的迭代次数是（n-1）*（n-1）= O（n²）。最好的运行时间是O（n），但是这种情况很少发生，以至于平均值仍然是O（n²）。

第二个版本，通常称为“气泡排序”，具有一个外部循环，其迭代n-1次，以及一个内部循环，其迭代n-1-i次。由于i平均约为n / 2，因此迭代次数约为n * n / 2 = O（n²）。没有短路，因此对于此版本的算法，这是最佳，最差和平均的情况。

这两种算法的平均情况都是O（n²），这是因为有关冒泡排序算法的一个基本事实：它在输入数组中每inversion执行一次交换。反转是一对索引，其元素顺序混乱。总共有（n选择2）= n *（n-1）/ 2对，平均其中一半将是反演。要看到这一点，请考虑如果一个数组具有k个反转，则该数组的反向具有（n选择2）-k个反转。因此，任何一个冒泡排序版本均进行平均n *（n-1）/ 4个交换，即O（n²）。