快速排序算法的问题

Question

我正在使用C#实现快速排序算法，但是我遇到了一个奇怪的问题，在随机数上执行该算法10次中，有2-3次排序结果错误。

也就是说，这段代码大概可以将10个例子中的7个进行排序，但是为什么？我无法确定问题出在哪里，你能帮我吗？

  public void quicksort(int[] data, int first, int n)
   { 
       int pivotIndex, n1, n2;
       if (n > 1)
       {
           pivotIndex= partition(data, first, n);
           n1 = pivotIndex-first;
           n2 = n -n1 -1;
           quicksort(data, first, n1);
           quicksort(data, pivotIndex+ 1, n2);
       }
   }

   private int partition(int[] data, int first, int n)
   {
       int t;
       int pivot= data[first], tooBigIndex=first+1, tooSmallIndex=first+n-1;
       while (tooBigIndex<= tooSmallIndex)
       {
        while( (tooBigIndex < n) && (data[tooBigIndex] <= pivot) )
                tooBigIndex++;
       while (data[tooSmallIndex] > pivot) 
            tooSmallIndex--;
           if (tooBigIndex< tooSmallIndex) 
           {
            t = data[tooBigIndex];
            data[tooBigIndex] = data[tooSmallIndex];
            data[tooSmallIndex] = t;
            tooSmallIndex--;
            tooBigIndex++;
           }
       }
       t= data[0];
       data[0]= data[tooSmallIndex] ;
       data[tooSmallIndex]=t;
       return tooSmallIndex;

   }
}

- Lisa

---

你是否总是在相同的随机数集合上得到错误的排序结果？如果是，请贴出该集合。另外，quicksort(..)方法中的“int n”参数是什么？ - VoodooChild

int n，指的是我正在操作的数组的长度。 - Lisa

Answer 1

我很惊讶你发布的代码竟然能够正常工作，甚至能够终止运行。下面是测试代码：

(tooBigIndex < n) &&

应该清晰明了

(tooBigIndex < first + n) &&

并且在这些行中的索引：

   t= data[0];
   data[0]= data[tooSmallIndex];
   data[tooSmallIndex]=t;

应该是first，而不是0（这使得第一行无用，因为你可以省略它，在第三行使用pivot代替t，但这是一个冗余，另外两个是可怕的错误;-)。

我认为这就是所有的错误，但我只在随机数组上进行了测试;-)。

- Alex Martelli

Answer 2

如果这是一个作业问题，您应该标记为作业问题，这样我们可以更好地针对帮助（多次提示正确方向而不是直接解决）。

如果这不是作业，您应该考虑使用IComparable接口和Array.sort()。对于提供IComparable接口的整数，您应该能够仅使用以下内容：

int[] valArray = new int[6] { 1, 5, 2, 6, 9, 7 };
Array.Sort (valArray);                            // <-- This is all you need.
String s = "";
foreach (int val in valArray)
    s += "," + val;
MessageBox.Show (s.Substring(1));

这会导致：

1,2,5,6,7,9

我相信它在内部使用了快速排序算法。重新发明轮子是一个坏主意，虽然可以用于教育目的，但如果意图只是为了能够对数组进行排序，那么请使用语言提供的功能，节省自己的精力。

- paxdiablo

---

这不是作业，但我需要代码用于我的项目。 - Lisa

为什么要重新发明轮子呢？如果你正在使用C#语言，就好好用它吧。不要胡乱尝试，那只会让人感到疯狂。 :-) - paxdiablo

我的项目是关于教授排序算法的。我不会重新发明任何东西。所以，我需要制作自己的排序方法，我可以控制绘制和等待的位置等等。 - Lisa