-8

可以说我有一个通用列表。

IList<T> list;

我需要对项目进行排序，但我不能使用 .NET 方法，Sort因为大多数集合都没有。由于我不提前知道类型是什么，我该如何对项目进行排序？

public void Sort(IList<T> list) {
}
4

4 回答 4

2

为了能够对列表中某种类型的项目进行排序，它们必须具有可比性，因此对于 .NET，您将不得不假设T实现IComparable<T>。现在您可以比较项目，只需实现排序算法即可，例如：

两者都是 O(n*log(n)) 但对于面试我会坚持合并排序，因为我发现它更容易实现。我认为这里选择一个的重点是不要建议完全简单的运行时间不好的东西，例如Bubble sort。

于 2013-03-10T17:23:03.663 回答
2

您可以使用快速排序实现：

static void QuickSort<T>(List<T> a, int left, int right) where T : IComparable<T>
{
    int i = left, j = right;
    T pivot = a[(left + right) / 2];
    while (i <= j)
    {
        while (a[i].CompareTo(pivot) < 0)
            i++;
        while (a[j].CompareTo(pivot) > 0)
            j--;
        if (i <= j)
        {
            T temp = a[i];
            a[i++] = a[j];
            a[j--] = temp;
        }
    }
    if (left < j)
        QuickSort(a, left, j);
    if (i < right)
        QuickSort(a, i, right);
}

这就是List.Sort()正在做的事情。

于 2013-03-10T17:25:18.900 回答
1

有关大量排序算法的信息，请参见Wikipedia 。

只要它们之间有顺序，您就不需要知道类型。您可以通过要求T成为IComparable.

于 2013-03-10T17:23:11.727 回答
1

好的，这实际上是两个问题：如何比较两个元素以查看它们应该处于什么顺序，以及如何将它们按顺序排列。

要比较两个元素，您可以要求调用者传入一些东西来进行比较，或者使用Comparer.Default为您创建一个。

要将元素按顺序排列，我建议实施快速排序。

于 2013-03-10T17:25:48.650 回答