快速排序算法的问题

Question

我正在使用C#中的快速排序算法,但是我面临一个奇怪的问题,即在随机数执行算法的10次中,我得到了2或3个错误的排序答案.

我的意思是:这个代码可以排序大约7个例子中的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第三行 - 但这是一个冗余,另外两个是可怕的错误;-).

我认为这是所有的错误,但我只测试了随机数组;-).