快速排序算法

Question

这个算法好吗?我可以改进它吗？

 static void QuickSort(int[] a)
    {
        QuickSort(a, 0, a.Length - 1);
    }

    static void QuickSort(int[] a, int start, int end)
    {
        if (start >= end)
        {
            return;
        }

        int num = a[start];

        int i = start, j = end;

        while (i < j)
        {
            while (i < j && a[j] > num)
            {
                j--;
            }

            a[i] = a[j];

            while (i < j && a[i] < num)
            {
                i++;
            }

            a[j] = a[i];
        }

        a[i] = num;
        QuickSort(a, start, i - 1);
        QuickSort(a, i + 1, end);
    }

Answer 1

该算法不可读。通常，人们都记不起快速排序的细节，即使代码写得很完美，人们仍然很容易迷路。而且，快速排序有点棘手，在哪里设置枢轴点，有多个选择。有几个想法要分享：

1. 对于快速排序，它是非常经典的算法，更好的使代码易于阅读，如应用SRP -单责任原则，编写一个称为分区的小函数。
2. 编写一个名为swap()的小函数。
3. 另外，找到一个你喜欢的快速排序解决方案，然后写你自己的。使算法更具可读性，减少脑力挑战。
4. 至少编写一个测试用例来测试代码。

让我以我的实践为例:我所做的C#代码：

  public static void quickSort(int[] A, int left, int right)
    {
        if(left > right || left <0 || right <0) return; 

        int index = partition(A, left, right);

        if (index != -1)
        {
            quickSort(A, left, index - 1);
            quickSort(A, index + 1, right);
        }
    }

    private static int partition(int[] A, int left, int right)
    {
        if(left > right) return -1; 

        int end = left; 

        int pivot = A[right];    // choose last one to pivot, easy to code
        for(int i= left; i< right; i++)
        {
            if (A[i] < pivot)
            {
                swap(A, i, end);
                end++; 
            }
        }

        swap(A, end, right);

        return end; 
    }

    private static void swap(int[] A, int left, int right)
    {
        int tmp = A[left];
        A[left] = A[right];
        A[right] = tmp; 
    }

参考文献：

1. C#代码
2. 快速排序代码引用

Answer 2

虽然将递归算法转换为迭代形式(反之亦然)是建立字符的，但我不太担心迭代还是递归。

有几种方法可以改进此代码。

• 正如我在上一篇文章中说过的:为什么是数组？您可以更加通用，并对IList<int>进行排序。为什么是国家统计局？您可以对所有可以一致比较的事物集合进行排序，这将使排序算法更有用。
• start和end非常清楚。i，j和num不是。这段代码的读者应该如何理解它的功能呢？将num重命名为它是什么:支点。
• 递归快速排序有四个基本步骤：(1)确定我们是否已经排序，(2)选择一个枢轴，(3)分区和(4)递归。您的大部分算法都用于(3)。考虑将分区逻辑放在一个可以清楚地显示为正确的助手方法中。
• 请考虑向我们展示您的测试用例。
• 没有错误处理；如果数组为空怎么办？如果开始和结束都超出了界限呢？诸若此类。
• 考虑添加后条件断言。后置条件断言是一个Debug.Assert，它在返回之前记录方法确保的内容是真的。在您的例子中，后置条件是“数组从开始到结束排序”。因此，请断言；编写一些“已排序”的谓词并验证它是否有效。这将帮助您找到bug，如果有任何。这将帮助未来的代码读者理解它。它将帮助那些在未来修改代码的人理解在修改代码时需要避免中断的地方。
• 分区步骤也有一个后置条件；在分区之后，数组被划分为三个部分:枢轴之前的值小于或等于它，枢轴和枢轴之后的值大于它。声称这些条件得到了满足。

Answer 3

我试过你的算法

int[] data = new [] { 17, 20, 11, 8, 0, 1, 14, 9, 9, 15, 5, 12, 8, 11, 16, 11, 11, 9, 16, 18 };

但不起作用。它在外部循环中无限循环。

我可以这样做：

public static void QuickSort(int[] a)
{
  QuickSort(a, 0, a.Length - 1);
}

static void QuickSort(int[] a, int start, int end)
{
  if (start >= end)
  {
    return;
  }

  int num = a[start];

  int i = start - 1;
  int j = end + 1;

  while (true)
  {
    do
    {
      i++;
    } while (a[i] < num);

    do
    {
      j--;
    } while (a[j] > num);

    if (i >= j)
      break;

    Swap(a, i, j);
  }

  //a[i] = num;
  QuickSort(a, start, j);
  QuickSort(a, j + 1, end);
}

static void Swap(int[] a, int i, int j)
{
  if (i == j)
    return;

  int temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

看看这里有什么背景