0

抱歉，我知道有很多关于快速排序的问题，但是其中有一个我找不到的错误。

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

private static void QuickSort(int[]sort, int first, int last)
{
    int i = first;
    int j = last;
    int pivot = (i + j)/2;
    int temp;

    while(i <= j)
    {
        while(sort[i] < sort[pivot]){i++;}
        while(sort[j] > sort[pivot]){j--;}

        if(i <= j)
        {
            temp = sort[i];
            sort[i] = sort[j];
            sort[j] = temp;             
            i++;
            j--; 
        }

    }

    if(first < j)QuickSort(sort, first, j);
    if(last > i)QuickSort(sort, i, last);
}

看起来不错，但对这个数组进行排序

int[] sortMe = {2,5,6,4,8,9,6,3,21,2,5,4,8,9,6,5,46,6,3};

像这样：

2,2,3,4,3,4,5,5,6,6,5,6,6,8,8,9,9,21,46

而不是明显的正确顺序。

4

2 回答 2

2

我认为你的pivot选择是错误的。

查看http://en.wikipedia.org/wiki/Quicksort#Choice_of_pivot

在快速排序的早期版本中，分区的最左侧元素通常会被选为枢轴元素。不幸的是，这会导致已经排序的数组出现最坏情况，这是一个相当常见的用例。通过为枢轴选择随机索引、选择分区的中间索引或（特别是对于较长的分区）为枢轴选择分区的第一个、中间和最后一个元素的中值，这个问题很容易解决。

只需将您的更改 int pivot = (i + j)/2;为int pivot = first;

    static void Main(string[] args)
    {
        int[] sortMe = { 2, 5, 6, 4, 8, 9, 6, 3, 21, 2, 5, 4, 8, 9, 6, 5, 46, 6, 3 };
        QuickSort(sortMe, 0, sortMe.Length - 1);

        foreach (var item in sortMe)
            Console.Write(item + " ");
    }

    private static void QuickSort(int[] sort, int first, int last)
    {
        int i = first;
        int j = last;
        int pivot = first;
        int temp;

        while (i <= j)
        {
            while (sort[i] < sort[pivot]) { i++; }
            while (sort[j] > sort[pivot]) { j--; }

            if (i <= j)
            {
                temp = sort[i];
                sort[i] = sort[j];
                sort[j] = temp;
                i++;
                j--;
            }

        }

        if (first < j) QuickSort(sort, first, j);
        if (last > i) QuickSort(sort, i, last);
    }

输出将是；

2 2 3 3 4 4 5 5 5 6 6 6 6 8 8 9 9 21 46

这是一个DEMO.

于 2013-04-29T06:24:26.257 回答
1

问题是您正在计算pivot，index然后将其与sort数组值进行比较，而您正在修改sort最外层while循环内的数组。Pivot应该是指向sort数组索引的最外层while循环的初始值，稍后将其与该值进行比较，而不是与sort基于索引的数组进行比较。

你的方法应该是：

public static void Quicksort(int[] sort, int first, int last)
{
    int i = first, j = last;
    int pivot = sort[(first + last) / 2]; //change here

    while (i <= j)
    {


        while (sort[i] < pivot) //Change here
        {
            i++;
        }

        while (sort[j] > pivot) //Change here
        {
            j--;
        }

        if (i <= j)
        {
            // Swap
            int tmp = sort[i];
            sort[i] = sort[j];
            sort[j] = tmp;

            i++;
            j--;
        }
    }

    // Recursive calls
    if (first < j)
    {
        Quicksort(sort, first, j);
    }

    if (i < last)
    {
        Quicksort(sort, i, last);
    }
}
于 2013-04-29T06:23:26.310 回答