C/.NET在不同情况下的最佳排序算法

查看此网站: Sorting Comparisons with Animtations

简短回答:快速排序

更长的答案: 上面的站点将通过一些漂亮的动画向您展示每个算法的优点和缺点。

简短的答案是没有最好的全方位排序(但你知道,因为你说了80%的时间:),但快速排序(或3路快速排序)可能是最好的通用算法,你可以使用。

它是默认情况下用于.NET中列表的算法,因此您可以调用 .Sort 如果你所拥有的已经在一个列表中。

如果你想看看如何实现这个,我在上面指出的网站上有伪代码。

你想整理什么?是否有任何理由不使用:

List<T>.Sort() ? 

我确信这使用了Quicksort,您不必担心会出现任何编码错误。可以实现IComparable来更改要排序的内容。

如果你所有的数据都不在内存中…嗯,你要去参加合并排序之类的比赛。

BubbleSort和InsertionSort是O(n^2),MergeSort和QuickSort是O(nlogn)。您可以使用list中的sort()方法来实现快速排序,也可以尝试实现它并使其适应您的需要。下面是一个基本实现: 快速排序

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

从 http://yadiragarnicabonome.com/sorting-arrays/

尝试快速排序: http://www.codeproject.com/KB/recipes/QuickSort_gen.aspx