c# - 快速排序算法的问题

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;

   }
}

Answer 1

我很惊讶您发布的代码曾经 有效——甚至终止。测试:

(tooBigIndex < n) &&

应该清楚

(tooBigIndex < first + n) &&

以及行中的索引:

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

应该是 first，不是 0(使第一行无用，因为你可以省略它并使用 pivot 代替第三行中的 t -- 但这是多余的，另外两个是可怕的错误；-)。

我认为这就是所有错误，但我只在随机数组上测试过；-)。