logo标签列表

最快且安全的排序算法实现

c#algorithmsorting
6

我花了一些时间在C#中实现快速排序算法。在完成后，我比较了我的实现和C#的Array.Sort方法的速度。

我只比较了对随机整数数组的排序速度。

这是我的实现：

static void QuickSort(int[] data, int left, int right)
{
    int i = left - 1,
        j = right;

    while (true)
    {
        int d = data[left];
        do i++; while (data[i] < d);
        do j--; while (data[j] > d);

        if (i < j) 
        {
            int tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }
        else
        {
            if (left < j)    QuickSort(data, left, j);
            if (++j < right) QuickSort(data, j, right);
            return;
        }
    }
}

性能（对于长度为100000000的随机int[]进行排序）：
   - 我的算法：14.21秒
   - .Net Array<int>.Sort：14.84秒

有人知道如何更快地实现我的算法吗？
或者有人可以提供一个更快的实现（不一定是快速排序），以便运行更快吗？

注意：
   - 请勿使用利用多个核/处理器来提高性能的算法
   - 仅限有效的C#源代码

如果我在线，我将在几分钟内测试所提供的算法的性能。

编辑：
您认为对于包含小于8个值的部分使用理想的排序网络会提高性能吗？

4
当一个已经排好序的数组中，尝试重复计时。然后，再用仅有两个元素顺序错误的数组进行计时。 - Ian Ringrose
2
性能提升了4.3% - 你这么做是出于学术原因吗？ - flq
2
Ian关于已排序数组的观点是正确的。选择枢轴元素会导致最坏情况性能恶劣。话虽如此，加速快速排序还是相当简单的。使用类似MedianOfThree方法选择更好的枢轴，并为小分区使用更合适的排序算法即可。我假设您这样做是为了个人研究，因为使用系统库排序方法几乎总是正确的答案。 - Blastfurnace
3
我刚刚完成了一项任务：当尝试对一个已经排序的数组进行排序时，我的算法变得非常缓慢。 - raisyn
有人能帮我吗？我正在测试这个算法，对于样本数据[3,1,2]，它返回[2,1,3]。这是一个bug还是我做错了什么？我的调用代码：QuickSort(data, 0, data.Length); - Karpik
显示剩余7条评论
6个回答
8

对于短序列（约10项），二进制插入排序几乎总是最快的。由于分支结构简化，它通常比理想的排序网络更好。

双轴快速排序比快速排序更快。

如果您只需要对整数进行排序，则基数排序在长数组上可能仍然更快。

7

有人知道如何更快地实现我的算法吗？

通过将您的代码转换为使用指针，我能够将执行时间缩短10%。

    public unsafe static void UnsafeQuickSort(int[] data)
    {
        fixed (int* pdata = data)
        {
            UnsafeQuickSortRecursive(pdata, 0, data.Length - 1);
        }
    }

    private unsafe static void UnsafeQuickSortRecursive(int* data, int left, int right)
    {
        int i = left - 1;
        int j = right;

        while (true)
        {
            int d = data[left];
            do i++; while (data[i] < d);
            do j--; while (data[j] > d);

            if (i < j)
            {
                int tmp = data[i];
                data[i] = data[j];
                data[j] = tmp;
            }
            else
            {
                if (left < j) UnsafeQuickSortRecursive(data, left, j);
                if (++j < right) UnsafeQuickSortRecursive(data, j, right);
                return;
            }
        }
    }
10
这是否与标题中的“安全”要求不符？ - Gabe
@Gabe：在我发布之前，我也考虑过这一点。我并不确定“安全”是否与“稳定”同义。但是，考虑到快速排序不稳定，那可能已经没有什么意义了。我决定继续发布。 - Brian Gideon
1
我可能会让顶层函数在调用之前不需要左/右参数或进行一些边界检查。 - Dolphin
我用一些具有浮点数Weight字段的Edge类测试了代码，但它没有正确排序。你确定算法没问题吗？ - morteza khosravi
@mortezakhosravi：绝对不是。它基本上是从OP复制过来的，只是转换为使用不安全代码（顺便说一句，我建议不要这样做）。虽然那是很久以前的事情了，但我严重怀疑我是否充分分析过它，以验证算法是否正确。 - Brian Gideon
显示剩余3条评论
1

这对我来说更快、更简单。

unsafe static void Sort(int* a, int length)
{
    int negLength = length - 1;
    for (int i = 0; i < negLength; ++i)
    for (int n = i + 1; n < length; ++n)
    {
        int value = a[i];
        int next = a[n];
        if (value > next)
        {
            a[i] = next;
            a[n] = value;
        }
    }
}
1
一个更快的用于随机整数数组排序的算法是LSD基数排序：
    public static int[] SortRadix(this int[] inputArray)
    {
        const int bitsPerDigit = 8;
        const uint numberOfBins = 1 << bitsPerDigit;
        uint numberOfDigits = (sizeof(uint) * 8 + bitsPerDigit - 1) / bitsPerDigit;
        int d;
        var outputArray = new int[inputArray.Length];

        int[][] startOfBin = new int[numberOfDigits][];
        for (int i = 0; i < numberOfDigits; i++)
            startOfBin[i] = new int[numberOfBins];
        bool outputArrayHasResult = false;

        const uint bitMask = numberOfBins - 1;
        const uint halfOfPowerOfTwoRadix = PowerOfTwoRadix / 2;
        int shiftRightAmount = 0;

        uint[][] count = HistogramByteComponents(inputArray, 0, inputArray.Length - 1);

        for (d = 0; d < numberOfDigits; d++)
        {
            startOfBin[d][0] = 0;
            for (uint i = 1; i < numberOfBins; i++)
                startOfBin[d][i] = startOfBin[d][i - 1] + (int)count[d][i - 1];
        }

        d = 0;
        while (d < numberOfDigits)
        {
            int[] startOfBinLoc = startOfBin[d];

            if (d != 3)
                for (uint current = 0; current < inputArray.Length; current++)
                    outputArray[startOfBinLoc[((uint)inputArray[current] >> shiftRightAmount) & bitMask]++] = inputArray[current];
            else
                for (uint current = 0; current < inputArray.Length; current++)
                    outputArray[startOfBinLoc[((uint)inputArray[current] >> shiftRightAmount) ^ halfOfPowerOfTwoRadix]++] = inputArray[current];

            shiftRightAmount += bitsPerDigit;
            outputArrayHasResult = !outputArrayHasResult;
            d++;

            int[] tmp = inputArray;       // swap input and output arrays
            inputArray = outputArray;
            outputArray = tmp;
        }
        return outputArrayHasResult ? outputArray : inputArray;
    }
    [StructLayout(LayoutKind.Explicit)]
    internal struct Int32ByteUnion
    {
        [FieldOffset(0)]
        public byte byte0;
        [FieldOffset(1)]
        public byte byte1;
        [FieldOffset(2)]
        public byte byte2;
        [FieldOffset(3)]
        public byte byte3;

        [FieldOffset(0)]
        public Int32 integer;
    }
    public static uint[][] HistogramByteComponents(int[] inArray, Int32 l, Int32 r)
    {
        const int numberOfBins = 256;
        const int numberOfDigits = sizeof(ulong);
        uint[][] count = new uint[numberOfDigits][];
        for (int i = 0; i < numberOfDigits; i++)
            count[i] = new uint[numberOfBins];

        var union = new Int32ByteUnion();
        for (int current = l; current <= r; current++)    // Scan the array and count the number of times each digit value appears - i.e. size of each bin
        {
            union.integer = inArray[current];
            count[0][union.byte0]++;
            count[1][union.byte1]++;
            count[2][union.byte2]++;
            count[3][((uint)inArray[current] >> 24) ^ 128]++;
        }
        return count;
    }

它在单个核心上以接近100兆Int32 /秒的速度运行-比Array.Sort()快约7倍，比单个核心上的Linq.OrderBy()快25倍，并且比6个核心上的Linq.AsParallel().OrderBy()快6倍。这个实现来自于nuget.org上的HPCsharp nuget包，该包还有用于排序uint[]、long[]和ulong[]数组的版本，以及MSD基数排序，它添加了float[]和double[]数组并且是原地排序。
最近添加到HPCsharp nuget包（开源且免费）中的另一个算法是并行混合归并排序，其中Array.Sort()作为递归的叶节点。该算法在32核AMD处理器上比Array.Sort()快40倍以上，并仍然是一种通用排序算法。 - DragonSpit
0

这个第一个（也可能是第二个）快速排序算法在对具有重复项的数组进行排序时会出现错误。我使用了this，它运行良好。

0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接