是否存在最差情况时间复杂度为n ^ 3的排序算法？

2 回答

• 1

  这是一个用C＃实现的：

  public void BadSort<T>(T[] arr) where T : IComparable
  {
      for (int i = 0; i < arr.Length; i++)
      {
          var shortest = i;
          for (int j = i; j < arr.Length; j++)
          {
              bool isShortest = true;
              for (int k = j + 1; k < arr.Length; k++)
              {
                  if (arr[j].CompareTo(arr[k]) > 0)
                  {
                      isShortest = false;
                      break;
                  }
              }
              if(isShortest)
              {
                  shortest = j;
                  break;
              }
          }
          var tmp = arr[i];
          arr[i] = arr[shortest];
          arr[shortest] = tmp;
      }
  }
  

  它基本上是一种非常天真的排序算法，再加上用最小值计算索引的不必要复杂的方法 .

  要点是这样的：

  • 对于每个索引

  • 从这一点向前找到元素

  • 与之后的所有其他元素相比，最终<=所有元素 .

  • 将此最短元素与此索引处的元素交换

  在最坏的情况下（降序排序的输入），最里面的循环（带比较）将被执行 O(n^3) 次，并且外循环的每次迭代都会将一个元素放入正确的位置，让你更接近完全排序 .

  如果你努力工作，你可能会找到一个几乎任何你想要的复杂性的排序算法 . 但是，正如评论者所指出的那样，希望永远不会碰到一个人 . 你真的要试着想出一个这么糟糕的东西 .

  回复于 2024-04-19T23:42:56+08:00
• 2

  这是一个优雅算法的例子，名为slowsort，运行于鈩鈩n^（log（n）/（2蓻）））任何正蓻：

  http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.116.9158&rep=rep1&type=pdf（第5条） .

  回复于 2024-04-19T23:42:56+08:00