快速排序不正确

本文关键字：不正确 快速排序 | 更新日期: 2023-09-27 18:11:29

对不起，我知道快速排序上有很多问题，但其中有一个我找不到的错误。

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

而不是明显的正确顺序。

快速排序不正确

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

结账http://en.wikipedia.org/wiki/Quicksort#Choice_of_pivot

在quicksort的早期版本中通常会选择分区作为枢轴元件。不幸地这会在已经排序的数组上导致最坏的情况，即相当常见的用例。这个问题很容易通过选择为枢轴选择一个随机索引，选择分区或(特别是对于较长的分区(选择的中值枢轴分区的第一个、中间和最后一个元素。

只需将您的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。

问题是将pivot计算为index，然后将其与sort数组值进行比较，而在最外层的while循环中修改sort数组。Pivot应该是最外层的初始值，而循环指向sort数组索引，稍后将其与该值进行比较，而不是与基于索引的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);
    }
}
相关文章：