最快的安全排序算法实现
我花了一些时间在C＃中实现快速排序算法。 完成后，我比较了我的实现速度和C＃的Array.Sort-Method。
我只是比较了随机int数组的速度。
这是我的实现：
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); 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 .Sort：14.84秒
有谁知道如何更快地实现我的算法？
或者任何人都可以提供更快的实施（不一定是快速排序！），我跑得更快？
注意：
– 请不要使用多核/处理器来提高性能的算法
– 只有有效的C＃源代码
如果我在线，我会在几分钟内测试所提算法的性能。
编辑：
您是否认为对于包含少于8个值的零件使用理想的分拣网络可以提高性能？
有谁知道如何更快地实现我的算法？
通过将代码转换为使用指针，我能够节省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项）。 由于简化的分支结构，它通常比理想的分拣网络更好。
双枢轴快速排序比快速排序快。 链接的文章包含一个您可能适应的Java实现。
如果您只对整数进行排序，那么在长数组上基数排序可能会更快。
看看Shear Sort和Odd-Event Transposition排序： http ： //www.cs.rit.edu/~atk/Java/Sorting/sorting.html和http://home.westman.wave.ca/~rhenry / sort / 。
这里有剪切排序的C＃实现： http ： //www.codeproject.com/KB/recipes/cssorters.aspx 。
这些例子都是用Java编写的，但它非常接近C＃。 它们是并行的，因为它们在多个内核上运行得更快，但仍然应该非常快。
当对具有重复项的数组进行排序时，第一个（可能是第二个）快速排序算法会中断。 我用过这个 ，效果很好。
这是一个开源的Radix Sort实现，它比Array.Sort和Linq.OrderBy更快。
public static uint[] SortRadix(this uint[] inputArray) { int numberOfBins = 256; int Log2ofPowerOfTwoRadix = 8; uint[] outputArray = new uint[inputArray.Length]; uint[] count = new uint[numberOfBins]; bool outputArrayHasResult = false; uint bitMask = 255; int shiftRightAmount = 0; uint[] startOfBin = new uint[numberOfBins]; uint[] endOfBin = new uint[numberOfBins]; while (bitMask != 0) // end processing digits when all the mask bits have been processed and shifted out, leaving no bits set in the bitMask { for (uint i = 0; i < numberOfBins; i++) count[i] = 0; for (uint current = 0; current < inputArray.Length; current++) // Scan the array and count the number of times each digit value appears - ie size of each bin count[ExtractDigit(inputArray[current], bitMask, shiftRightAmount)]++; startOfBin[0] = endOfBin[0] = 0; for (uint i = 1; i < numberOfBins; i++) // Victor J. Duvanenko startOfBin[i] = endOfBin[i] = (uint)(startOfBin[i - 1] + count[i - 1]); for (uint current = 0; current < inputArray.Length; current++) outputArray[endOfBin[ExtractDigit(inputArray[current], bitMask, shiftRightAmount)]++] = inputArray[current]; bitMask <<= Log2ofPowerOfTwoRadix; shiftRightAmount += Log2ofPowerOfTwoRadix; outputArrayHasResult = !outputArrayHasResult; uint[] tmp = inputArray; // swap input and output arrays inputArray = outputArray; outputArray = tmp; } if (outputArrayHasResult) for (uint current = 0; current < inputArray.Length; current++) // copy from output array into the input array inputArray[current] = outputArray[current]; return inputArray; }
在https://duvanenko.tech.blog/2018/05/23/faster-sorting-in-c/上使用基准测试
和nuget.org上的免费NuGet包（HPCsharp），源代码为
https://github.com/DragonSpit/HPCsharp
其中还有Merge Sort（串行和并行）实现。