如何让这个 Dual Pivot Quicksort 变得更好/更快

Question

标题已经说过了，我问的是如何使我的代码更快或更好。现在我遇到的问题是我的 Dual Pivot Quicksort 比普通的 Quicksort 慢得多，而且也不能处理大数。现在我只是要输入方法的代码，但如果你愿意，我也可以 post Main 方法，所以你可以看到我的输入。

public static List<int> sort(List<int> input, bool start)
{
    if (input.Count > 1)
    {
        int LP = input[0];
        int RP = input[input.Count - 1];
        List<int> lessLP = new List<int>();
        List<int> greatRP = new List<int>();
        List<int> betweenLPRP = new List<int>();
        if (LP > RP)
        {
            int sp = LP;
            LP = RP;
            RP = sp;
        }

        for (int i = 1; i < input.Count - 1; i++)
        {
            if (input[i] < LP)
            {
                lessLP.Add(input[i]);
            }

            else if (input[i] > RP)
            {
                greatRP.Add(input[i]);
            }

            else if (input[i] >= LP & input[i] <= RP)
            {
                betweenLPRP.Add(input[i]);
            }
        }
        List<int> end = new List<int>();

        lessLP = sort(lessLP, false);
        greatRP = sort(greatRP, false);
        betweenLPRP = sort(betweenLPRP, false);
        input.Clear();

        foreach (var x in lessLP)
        {
            end.Add(x);
        }
        lessLP.Clear();
        end.Add(LP);
        foreach (var x in betweenLPRP)
        {
            end.Add(x);
        }
        betweenLPRP.Clear();
        end.Add(RP);
        foreach (var x in greatRP)
        {
            end.Add(x);
        }
        greatRP.Clear();
        return end;
    }
    return input;
}

感谢您的帮助。顺便说一句，很抱歉未注释的代码

编辑：好的，经过一些反馈，我尝试获取此代码 https://cs.stackexchange.com/questions/24092/dual-pivot-quicksort-reference-implementation 作为 c# 工作。

但现在每次我运行这段代码都会收到 WhosebugException

        public static void quicksort(ref int[] arr, int left, int right)
        {
            if (right > left)
            {
                if (arr[left] > arr[right]) swap(ref arr, left, right);
                int p = arr[left], q = arr[right];

                int l = left + 1, g = right - 1, k = 1; 
                while(k <= g)
                {
                    if (arr[k] < p)
                    {
                        swap(ref arr, k, l);
                        l++;
                    }

                    else if (arr[k] >= q)
                    {
                        while (arr[g] > q && k < g) g--;
                        swap(ref arr, k, g);
                        g--;
                        if(arr[k] < p)
                        {
                            swap(ref arr, k, l);
                            l++;
                        }
                    }
                    k++;
                }
                l--; g++;

                swap(ref arr, left, l);
                swap(ref arr, right, g);
                quicksort(ref arr, left, l - 1);
                quicksort(ref arr, l + 1, g - 1);
                quicksort(ref arr, g + 1, right);
            }
        }

        public static void swap(ref int[] arr, int i, int j)
        {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }

Answer 1

您在翻译该参考中的代码时有错别字。

这一行：

int l = left + 1, g = right - 1, k = 1;

您拥有的最后一个 1（一个）应该是 l（小写 L）。

顺便说一句，由于数组在 c# 中定义为引用类型，因此 arr 参数上的 ref 修饰符是不必要的。仅当您希望从方法内（如 arr = new ... 中）替换整个参数并将该更改反映在调用者中时才需要这样做。这适用于 quicksort 和 swap。这里，ref 只会降低代码的效率。

另一个小问题是引用的代码（和你的代码）在调用 swap 时使用相同的 i 和 j 参数时效率低下 - 但不影响有效性, 只有速度。

如何让这个 Dual Pivot Quicksort 变得更好/更快

How can this DualPivot Quicksort be made better / faster

c#

quicksort