Quicksort没有正确排序

Question

尝试从Quicksort的实现中学习,我无法找出为什么它没有正确排序.

使用此序列:

6,7,12,5,9,8,65,3

它返回:

3,5,7,8,9,65,12,6

它似乎有些不同,但不是全部.我错过了什么？

这是我的代码:

 static void Main(string[] args)
        {
            QuickSort qs = new QuickSort();

           int[] arr = new int[] { 6, 7, 12, 5, 9, 8, 65, 3 };

            foreach (int l in arr)
            {
                Console.Write(l + ", ");
            }

            int left = 0;
            int right = arr.Count() - 1;

            int[] arrr = qs.DoQuickSort(ref arr, left, right);
            Console.WriteLine("Sorted List: ");
            foreach (int i in arrr)
            {
                Console.Write(i + " ");
            }



            Console.ReadLine();
        }

   public int Partition(int[] array, int left, int right, int PivotIndex)
    {
    int pivValue = array[PivotIndex];

    array = Swap(ref array, PivotIndex, right);

    int storeIndex = left;

    for (int i = PivotIndex; i < right-1; i++)
    {
        if (array[i] <= pivValue)
        {
            array = Swap(ref array, i, storeIndex);
            storeIndex = storeIndex + 1;
        }
    }

    array = Swap(ref array, storeIndex, right);

    return storeIndex;
}

public int[] Swap(ref int[] arr, int first, int second)
{
    int temp = arr[first];
    arr[first] = arr[second];
    arr[second] = temp;

    return arr;
}

public int[] DoQuickSort(ref int[] array, int left, int right)
{
    if (right > left)
    {
        int PivIndex = (left + right) / 2;
        int newPivIndex = Partition(array, left, right, PivIndex);
        DoQuickSort(ref array, left, newPivIndex - 1);
        DoQuickSort(ref array, newPivIndex + 1, right);
    }

    return array;
}

Answer 1

你要求被交给鱼,还是被教导如何钓鱼？

学习如何调试自己的程序,而不是依靠其他人为你做,这是一项将来很好地为你服务的技能.

当面对这个问题,我会做的第一件事就是标记的代码注释指示语义的每段代码的目的:

// Choose a pivot halfway along the portion of the list I am searching.
int PivIndex = (left + right) / 2; 
// Partition the array so that everything to the left of the pivot
// index is less than or equal to the pivot, and everything to
// the right of the pivot is greater than or equal to the pivot.
int newPivIndex = Partition(array, left, right, PivIndex); 
// Recursively sort each half.
DoQuickSort(ref array, left, newPivIndex - 1); 
DoQuickSort(ref array, newPivIndex + 1, right); 

好的,现在,在这里的某个地方有一个错误. 哪里？开始列出您认为是真实的事实,并为每个事实写一个断言.编写自己的帮助方法,如AllLessThan,它可以为您验证断言.

// Choose a pivot halfway along the portion of the list I am searching.
int PivIndex = (left + right) / 2;

int pivotValue = array[PivIndex];
// Partition the array so that everything to the left of the pivot
// index is less than or equal to the pivot, and everything to
// the right of the pivot is greater than or equal to the pivot.
int newPivIndex = Partition(array, left, right, PivIndex); 
Debug.Assert(array[newPivIndex] == pivotValue);
Debug.Assert(AllLessThanOrEqual(array, left, newPivIndex, pivotValue));
Debug.Assert(AllGreaterThanOrEqual(array, newPivIndex, right, pivotValue));
// Recursively sort each half.
DoQuickSort(ref array, left, newPivIndex - 1); 
Debug.Assert(IsSorted(array, left, newPivIndex));
DoQuickSort(ref array, newPivIndex + 1, right); 
Debug.Assert(IsSorted(array, left, right));

现在当你再次运行这个程序时,你的一个断言被违反的那一刻,你会得到一个弹出的框来告诉你bug的本质是什么.继续这样做,用断言记录你的前置条件和后置条件,直到找到bug.

Answer 2

在您的Partition方法中,您有一个错误的循环范围:

for (int i = PivotIndex; i < right-1; i++)

应该成为:

for (int i = left; i < right; i++)

查看相关的维基百科文章,其中说:

function partition(array, left, right, pivotIndex)
     pivotValue := array[pivotIndex]
     swap array[pivotIndex] and array[right] // Move pivot to end
     storeIndex := left
     for i  from  left to right - 1 // left ? i < right  
         if array[i] ? pivotValue 
             swap array[i] and array[storeIndex]
             storeIndex := storeIndex + 1
     swap array[storeIndex] and array[right] // Move pivot to its final place
     return storeIndex

注意: left ? i < right