一种使用二进制方法的快速气泡排序变体

Question

我一直在做一些面试问题的准备，在这个过程中，我想出了一个关于泡泡排序的小变体，它将我所学到的关于二进制搜索的知识融入到交换的内部循环中。因此，时间复杂度比O(n^2)减少了大约50%。我想我的问题是我是不是在泡泡那类事上浪费时间了？我应该学桶式的分类并完成它吗？

我一直在用下面的输入进行测试。

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;
  }

诉.

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实用程序或ORDER BY函数。当你需要抛出数据并有选择的时候，不要把它吸进你的记忆中去排序，先把它排序到更有效率的地方。
3. 合并排序。(供专家使用)在我的一生中，我确实两次需要写一种类型的东西，而前两种选择是不够的。两次都是同一个故事。由于一系列复杂的原因，过多的数据无法使用库例程，也不适合用于外部工具。因此，它必须是外部排序(即将中间文件保存在磁盘上的内存之外)。如果需要编写外部排序，合并排序是您的朋友。
4. 快排序。(当被想要的专家采访时)偶尔有人会问你类库到底是如何工作的。我会说，“有很多方法可以工作，但很长一段时间里，快速排序是标准的。你想让我展示它是如何工作的吗？”这通常是他们想要的答案。很少有人知道快速排序在很大程度上被timsort所取代。有能力深入挖掘的人会被告知：“在本世纪，平台开始向timsort方向发展。它是为Python发明的，被Java、Chrome和其他平台所采用。我需要了解一下它是如何工作的。”
5. 基类。(当被聪明的人采访时。)如果有人问你是否能比O(n log(n))更快地排序，你就需要知道这个问题。知道答案可能会让他们更加努力地工作，以证明他们的书呆子资历比你的好。这将是我不想和他们合作的一个标志。