谁能告诉我排序算法的大 O 时间？

塞奇A

我不太擅长记住所有不同的算法，所以我实现了一个，但我不确定如何为它计算 Big O 时间，因为有一个移动指针。

它不是很有效，或者至少有更好的分类。

它通过来回移动指针来对数组进行排序，从位置 0 开始向右移动，每次交换时返回一次，以查看左侧的元素是否也需要更改。

这是代码：

function countInversions(arr) {
  var count = 0;
  var i=0;

  while(i < arr.length) {
    // look behind
    if (i-1 >= 0 && arr[i-1] > arr[i]) {
      swap(arr, i, i-1);
      count++;
      i--;
      continue;
    }    
    // look ahead
    else if (arr[i] > arr[i+1]) { 
      swap(arr, i, i+1);
      count++;
      continue;
    }

    i++;
  }

  return count;
}

function swap(arr, i1, i2) {
  const temp = arr[i2];
  arr[i2] = arr[i1];
  arr[i1] = temp;
}

编辑：它看起来像一个“冒泡排序”。我仍然不确定大 o 是什么。

HmT

您的排序确实是冒泡排序，但只是您将小项目移到第一个而不是将大项目移到最后一个。

对于排序算法，复杂性通常用于更坏、最佳和平均情况。您的实现（冒泡排序）中最好的情况是数组已经排序并且复杂度为 O(n)。但最差和平均是O(n^2)

顺便说一句，我注意到您已经计算了交换操作的数量，只是想提一下您应该根据大 O 计算考虑循环的数量。然而，这完全取决于您的平台和要求，如果例如扫描阵列几乎不需要时间，但交换项目在您的平台上花费更多时间，那么计算交换是有道理的。

我还想对您的算法提出一些改进建议：

在将项目向左移动之前，您可以保存当前位置，一旦它稳定下来，只需向后移动并从之前的位置继续。请参阅下面的修改后的代码。

无论如何，时间复杂度不会改变，它仍然是 O(n^2) 但它只会给你一点改进。

function countInversions(arr) {
  var count = 0;
  var i=0;
  var old_i=-1;

  while(i < arr.length) {
    count++;
    // look behind
    if (i-1 >= 0 && arr[i-1] > arr[i]) {
      swap(arr, i, i-1);
      if (old_i<0)
        old_i=i;
      i--;
      continue;
    }    
    // look ahead
    else if (arr[i] > arr[i+1]) { 
      swap(arr, i, i+1);
      continue;
    }

    if (old_i>0){
      i=old_i;
      old_i=-1;
    }
    i++;
  }
  return count;
}

function swap(arr, i1, i2) {
  const temp = arr[i2];
  arr[i2] = arr[i1];
  arr[i1] = temp;
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。