我的快速排序算法仅适用于第一个索引作为枢轴

Question

我已经开始研究排序算法，并让 Quicksort 使用激活方法作为主元的第一个索引。

现在，如果我尝试使用随机索引或最后一个索引，它要么什么都不做，要么只对后半部分进行排序。 A Video 说明我的意思。

我的代码：

    class Quicksort : Sortalgorithm
{
    int ActivationMethod = -1;

    Random rand = new Random();

    /// <summary>
    /// The Constructor for the Quicksort Algorithm
    /// </summary>
    /// <param name="arr">The Array to sort</param>
    /// <param name="Actv">Activation Method: 0=First; 1=Last; 2=Random</param>
    /// <param name="del">The Delay for the Algorithm between each sort</param>
    /// <param name="sound">Wether Sound should be played</param>
    /// <param name="gui">The Instance of the GUI</param> 
    public Quicksort(int[] arr, int Actv, int del, bool sound, gui gui) : base(del, sound, gui)
    {
        if (arr.Length < 5)
        {
            throw new Exception("Array has too few Entries");
        }
        ActivationMethod = Actv;
        toSort = arr; // Is A Global Array from the inherited Class
    }

    protected override int sort()
    {
        if (token.IsCancellationRequested) return 2; // To Properly Cancel a Sort
        return qsort(getPivot(), toSort.Length-1);
    }

    /// <summary>
    /// The Quicksort Recursive Logic. Both Params are needed for the "sub-array"
    /// </summary>
    /// <param name="start">StartIndex for the Current Array</param>
    /// <param name="end">EndIndex for the Current Array</param>
    /// <returns></returns>
    private int qsort(int start, int end)
    {
        if (start < end)
        {
            if (token.IsCancellationRequested) return 2; // To Properly Cancel a Sort
            int pivot = partition(start, end); //get the pivot
            qsort(start, pivot); // do the same for the frist part (smaller or equal to pivot)
            qsort(pivot + 1, end); //and now for the second part (the largen than pivot)
        }
        return 1;
    }

    /// <summary>
    /// The Partitioning Logic for The Array. Both Params are needed for the "sub-array"
    /// </summary>
    /// <param name="start">StartIndex for the Current Array</param>
    /// <param name="end">EndIndex for the Current Array</param>
    /// <returns></returns>
    private int partition(int start, int end)
    {
        int pivot = toSort[start]; //Depending on Activiation Method
        int swapIndex = start;
        for (int i = start + 1; i <= end; i++)
        {
            if (toSort[i] < pivot) //Sort the Index Accrodingly
            {
                if (token.IsCancellationRequested) return 2; // To Properly Cancel a Sort
                swapIndex++;
                swap(i, swapIndex); // Is A Method inherited from a Class
            }
        }
        swap(start, swapIndex);
        return swapIndex;
    }

    /// <summary>
    /// Get The Pivot returning on the Declared Activation Method in the Construcor
    /// </summary>
    /// <returns>PivotIndex</returns>
    private int getPivot()
    {
        switch (ActivationMethod)
        {
            case 0:
                return 0;
            case 1:
                return toSort.Length - 1;
            case 2:
                return rand.Next(0, toSort.Length - 1);
            default:
                throw new Exception("No Activationmethod Defined");
        };
    }
}

我已经被这个问题困扰了很长一段时间，任何帮助将不胜感激

Answer 1

你的逻辑有问题。

你做到了qsort(getPivot(), toSort.Length-1);

在顶层 select 枢轴，然后在 partition() 中

int pivot = toSort[start];

那是行不通的：qsort 的第一个参数是从哪里开始排序，因此在顶层除了零之外的任何内容都会阻止部分输入参与排序。

相反，需要为每个分区 select 编辑主元，因此必须在 partition():

内进行

private int partition(int start, int end)
    {
        int pivot = toSort[getPivot(start, end)]; //Depending on Activiation Method

然后必须修改 getPivot() 以根据所需的枢轴 start 和 end 在计算枢轴索引在适当范围内时考虑参数 select离子法

我的快速排序算法仅适用于第一个索引作为枢轴

My Quicksort Algorithm only works with First Index as the Pivot

c#

sorting

quicksort