使用二进制方法的更快的冒泡排序变体

Question

我一直在做一些面试问题的准备工作，并在此过程中提出了一个关于冒泡排序的小变体，它将我学到的关于二进制搜索的内容整合到内部循环中进行交换。因此，时间复杂度比O（n ^ 2）大约减少50％。我想我的问题是我是在浪费我的时间与Bubble排序？我应该学习Bucket Sort并完成它吗？

我一直在测试以下输入。

int[] nums = { 9878, 1, 4, 8, 5, 7, 88, 1, 54, 2, 2, 9878, 5, 7, 3, 11, 1, 4, 8, 5, 7, 88, 1, 54, 2, 2, 5, 7, 3, 11 };

public static int[] sortWBinary(int[] ar)
{
      var swapped = true;
      for (int i = 0; i < ar.Length && swapped; i++)
      {
          swapped = false;
          for (int k = i, j = ar.Length - 1; k < ar.Length - i - 1 && j > 0; k++, j--)
          {
              if (ar[k] > ar[k + 1])
              {
                  var temp = ar[k];
                  ar[k] = ar[k + 1];
                  ar[k + 1] = temp;
                  swapped = true;
              }

              if (ar[j - 1] > ar[j])
              {
                  var temp = ar[j - 1];
                  ar[j - 1] = ar[j];
                  ar[j] = temp;
                  swapped = true;
              }

          }
      }

      return ar;
  }

VS.

public static int[] sortWoBinary(int[] ar)
{
    var swapped = true;
    for (int i = 0; i < ar.Length && swapped; i++)
    {
        swapped = false;
        for (int k = 0; k < ar.Length - i - 1; k++)
        {
            if (ar[k] > ar[k + 1])
            {
                var temp = ar[k];
                ar[k] = ar[k + 1];
                ar[k + 1] = temp;
                swapped = true;
            }
        }
    }
    return ar;
}

Answer 1

要进行排序，请了解O(n log(n))和O(n^2)之间的区别，并知道如果您有足够的数据来关注您正在做的事情，您总是希望使用前者。

以下是您应该能够谈论的所有类型的排序。如果我正在采访你，我只关心你知道前两个。在告诉你如何写它之后我可能会要求你实现第三个，但我不在乎你是否知道它。

1. 无论您的图书馆是什么。任何不知道首先达到目标的程序员都会对他们的代码库造成危险，因此不应该被雇用。
2. 外部排序工具，例如Unix sort实用程序或SQL中的ORDER BY函数。当你需要抛出数据并做出选择时，不要将它吸入内存中进行排序，先将它排序到更高效的地方。
3. 合并排序。 （对于专家来说。）在我的生命中，我需要写两次，而前两个选项是不够的。这两次都是同一个故事。由于一系列复杂的原因，使用库例程的数据太多，而不适合外部工具。所以它必须是一个外部排序（即中间文件保留在磁盘上的内存）。如果您需要编写外部排序，合并排序是您的朋友。
4. 快速排序。 （当受到想法专家的采访时。）偶尔有人会问你图书馆的排序是如何运作的。我会说，“它有很多方法可以使用，但很长一段时间内，快速排序是标准。你要我展示它是如何工作的吗？”这通常是他们想要的答案。很难找到一个知道quicksort很大程度上被timsort取代的人。有人可以进一步深入挖掘，并告诉他们，“在这个世纪，平台已经走向了时尚。它是为Python发明的，已被Java，Chrome和其他平台采用。我将不得不查看它是如何工作的。 “
5. 基数排序。 （当被smartasses采访时。）如果有人问你是否能比O(n log(n))排序更快，你需要知道这个。知道答案可能会让他们更加努力地表明他们的书呆子证书比你的更好。这将是我希望与他们合作的标志。