C#合并排序性能 [英] C# merge sort performance

问题描述

请注意，这不是家庭作业.我只是想重温我的算法.我正在使用C#中的MergeSort，并且编写了一种可以基于泛型进行排序的递归方法:

just a quick note, this is not homework. I'm just trying to brush up on my algorithms. I'm playing around with MergeSort in C# and I've written a recursive method that can sort based on Generics:

class SortAlgorithms
{

    public T[] MergeSort<T> (T[] unsortedArray) where T : System.IComparable<T>
    {
        T[] left, right;
        int middle = unsortedArray.Length / 2;

        left = new T[middle];
        right = new T[unsortedArray.Length - middle];

        if (unsortedArray.Length <= 1)
            return unsortedArray;

        for (int i = 0; i < middle; i++)
        {
            left[i] = unsortedArray[i];
        }

        for (int i = middle; i < unsortedArray.Length; i++)
        {
            right[i - middle] = unsortedArray[i];
        }

        left = MergeSort(left);

        right = MergeSort(right);


        return Merge<T>(left, right);
    }

    private T[] Merge<T> (T[] left, T[] right) where T : System.IComparable<T>
    {
        T[] result = new T[left.Length + right.Length];

        int currentElement = 0;

        while (left.Length > 0 || right.Length > 0)
        {
            if (left.Length > 0 && right.Length > 0)
            {
                if (left[0].CompareTo(right[0]) < 0)
                {
                    result[currentElement] = left[0];
                    left = left.Skip(1).ToArray();
                    currentElement++;
                }
                else
                {
                    result[currentElement] = right[0];
                    right = right.Skip(1).ToArray();
                    currentElement++;
                }
            }
            else if (left.Length > 0)
            {
                result[currentElement] = left[0];
                left = left.Skip(1).ToArray();
                currentElement++;
            }
            else if (right.Length > 0)
            {
                result[currentElement] = right[0];
                right = right.Skip(1).ToArray();
                currentElement++;
            }
        }

        return result;
    }
}

这有效，但是速度很慢.我已经使用System.Diagnostic.StopWatch来检查Array.Sort(使用QuickSort算法)的性能，并与我的MergeSort进行比较，两者之间的差异是如此之大，以至于我想知道是否可能是我实现了这个错误.有任何评论吗?

This works but it is painfully slow. I've used System.Diagnostic.StopWatch to check performance against Array.Sort (which uses QuickSort algorithm) to compare against my MergeSort and the difference is so significant I'm wondering if maybe I'm implementing this wrong. Any comments?

推荐答案

我不是C#程序员，但是问题可能出在使用这样的语句吗?

I am not a C# programmer, but could the problem be the use of statements like this one?

left = left.Skip(1).ToArray();

这可以通过强制对基础数组进行深拷贝的方式来实现.如果是这样，这会将合并性能从O(n)降低到O(n ² )，立即将结果合并排序的性能从O(n log n)降低到O(n ² ).

This might be implemented in a way that forces a deep copy of the underlying array. If so, this would drop the performance of merge from O(n) to O(n²), immediately dropping the performance of the resulting merge sort from O(n log n) to O(n²).

(这是因为重复发生时间自

(This is because the recurrence changes from

T(1)= O(1)

T(1) = O(1)

T(n)≤ 2T(n/2)+ O(n)

T(n) ≤ 2T(n / 2) + O(n)

具有解T(n)= O(n log n)，以

which has solution T(n) = O(n log n), to

T(1)= O(1)

T(1) = O(1)

T(n)≤ 2T(n/2)+ O(n ² )

T(n) ≤ 2T(n / 2) + O(n²)

具有解决方案T(n)= O(n ² )的

.)

which has solution T(n) = O(n²).)

这篇关于C#合并排序性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！