不同场景下C#/.NET的最佳排序算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/262431/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Best sorting algorithms for C# / .NET in different scenarios
提问by Dan Esparza
What are the best algorithms for sorting data in C#?
在 C# 中排序数据的最佳算法是什么？
Is there one sorting algorithm that can handle 80% of sorts well?
是否有一种排序算法可以很好地处理 80% 的排序？
Please give code examples if applicable.
如果适用，请给出代码示例。
采纳答案by CubanX
Check out this site:
Sorting Comparisons with Animations
查看此站点：
使用动画进行排序比较
Short answer: Quick Sort
简答：快速排序
Longer answer: The above site will show you the strengths and weaknesses of each algorithm with some nifty animations.
更长的答案：上面的站点将通过一些漂亮的动画向您展示每种算法的优点和缺点。
The short answer is there is no best all around sort (but you knew that since you said 80% of the time :) ) but Quick Sort (or 3 Way Quick Sort) will probably be the best general algorithm you could use.
简短的回答是没有最好的排序（但你知道，因为你说 80% 的时间:)）但是快速排序（或三向快速排序）可能是你可以使用的最好的通用算法。
It is the algorithm used by default for Lists in .Net, so you can just call .Sortif what you have is already in a list.
它是 .Net 中列表默认使用的算法，因此.Sort如果您拥有的内容已经在列表中，您就可以调用。
There is pseudo-code on the website I pointed you to above if you want to see how to implement this.
如果您想了解如何实现这一点，我在上面指出的网站上有伪代码。
回答by Manu
回答by Keltex
What are you trying to sort? Is there any reason not to use:
你想排序什么？有什么理由不使用：
List<T>.Sort() ?
I'm sure this uses QuickSort and you don't have to worry about making any coding errors. You can implement IComparable to change what you want to sort on.
我确定这使用了 QuickSort，您不必担心出现任何编码错误。您可以实现 IComparable 来更改要排序的内容。
If all your data doesn't fit in memory... well the you're off to the races with Merge sort or something along those lines.
如果您的所有数据都不适合内存......那么您就可以使用 Merge sort 或类似方法进行竞赛了。
回答by Yadira Garnica
The Bubblesort and the Insertionsort are O(n^2), the Mergesort and the Quicksort are O(nlogn). You can use Sort() method from List, that implements Quicksort, or also you can try implement it and adapt it to yours needs. Here is a basic implementation: Quicksort
冒泡排序和插入排序是 O(n^2)，合并排序和快速排序是 O(nlogn)。您可以使用实现 Quicksort 的 List 中的 Sort() 方法，或者您也可以尝试实现它并根据您的需要进行调整。这是一个基本实现：Quicksort
//O(nlogn)
public static void QuickSort(int[] array, int init, int end)
{
if (init < end)
{
int pivot = Partition(array, init, end);
QuickSort(array, init, pivot-1);
QuickSort(array, pivot + 1, end);
}
}
//O(n)
private static int Partition(int[] array, int init, int end)
{
int last = array[end];
int i = init - 1;
for (int j = init; j < end; j++)
{
if (array[j] <= last)
{
i++;
Exchange(array, i, j);
}
}
Exchange(array, i + 1, end);
return i + 1;
}
private static void Exchange(int[] array, int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
