最快的安全排序算法实现

本文介绍了最快的安全排序算法实现的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

I spend some time implementing a quicksort algorithm in C#. After finishing I compared the speed of my implementation and C#'s Array.Sort-Method.

我只是比较了处理随机int数组的速度。

I just compare speed working on random int arrays.

这是我的实现方式：

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; } } }

性能（随机排序时） int []，长度为100000000）： -我的算法：14.21秒 --.Net Array< int>。排序：14.84秒

Performance (when sorting an random int[] with length of 100000000):    - my algorithm: 14.21 seconds    - .Net Array<int>.Sort: 14.84 seconds

有人知道如何更快地实现我的算法吗？ 还是有人可以提供更快的实现（不需要是快速排序！），我的运行速度会更快吗？

Does anyone know how to implement my algorithm even faster? Or can anyone provide a faster implementation (need not be a quicksort!) which my run faster?

注意： －请不要使用使用多个内核/处理器来提高性能的算法 －仅有效的C＃源代码

Note:    - please no algorithms which use multiple cores/processors to improve perrformance    - only valid C# source code

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

I will test the performance of the provided algorithms within a few minutes if I'm online.

编辑： 您认为对值小于8的零件使用理想的分拣网络会提高性能吗？

Do you think using a ideal sorting network for parts containing less than 8 value would improve performance?

推荐答案

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

Does anyone know how to implement my algorithm even faster?

通过将代码转换为使用指针，可以节省10％的执行时间。

I was able to shave 10% off the execution time by converting your code to use pointers.

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; } } }