使用递归和泛型创建快速排序

Question

我想问一下我创建的通用排序 class。我使用了今年学到的很多不同的概念，并将它们组合成一个很好的 class，我可以用它来对任何东西进行排序（当然，如果它是 class，那么 class 有一个 CompareTo 方法)

public class Sort<T> where T : IComparable<T>
    {
        private List<T> toSort;
        public Sort(List<T> sortList)
        {
            toSort = sortList;
            quickSort();
        }
        public void quickSort()
        {
            qSort(toSort, 0, toSort.Count - 1);
        }
        private void qSort(List<T> toSort, int left, int right)
        {
            //set the indexes
            int leftIndex = left;
            int rightIndex = right;

            //get the pivot
            var pivot = toSort[left + (right - left) / 2];
            while (leftIndex <= rightIndex)
            {
                //check left values
                while (toSort[leftIndex].CompareTo(pivot)<0)
                {
                    leftIndex++;
                }
                //check right values
                while (toSort[rightIndex].CompareTo(pivot) >0)
                {
                    rightIndex--;
                }
                //swap
                if (leftIndex <= rightIndex)
                {
                    var tmp = toSort[leftIndex];
                    toSort[leftIndex] = toSort[rightIndex];
                    toSort[rightIndex] = tmp;

                    //move towards pivot
                    leftIndex++;
                    rightIndex--;
                }
            }
            //continues to sort left and right of pivot
            if (left < rightIndex)
            {
                qSort(toSort, left, rightIndex);
            }
            if (leftIndex < right)
            {
                qSort(toSort, leftIndex, right);
            }
        }


    }

我只有一个问题，我用的quickSort是从网上弄来的，然后自己改成泛型的。我了解实际排序的工作原理。我只是想知道，为什么我不需要 return 一些东西。我有点困惑。我看到它实际上是在切换列表的值，但我想知道它是如何访问我发送的列表的。因为在我调用它的地方我可以这样做

List<string> toSort = new List<string> { "C", "B", "A" };
                Sort<string> sort = new Sort<string>(toSort);
                cbxAlphabet.DataSource = toSort;

所以我只使用原始列表，组合框中将有 A、B 和 C。

如果有人能解释一下，我将不胜感激！

编辑：

 public static class Sort<T> where T : IComparable<T>
    {
        public static void quickSort(List<T> sortList)
        {
            qSort(sortList, 0, sortList.Count - 1);
        }
        private static void qSort(List<T> toSort, int left, int right)
        {
            //set the indexes
            int leftIndex = left;
            int rightIndex = right;

            //get the pivot
            var pivot = toSort[left + (right - left) / 2];
            while (leftIndex <= rightIndex)
            {
                //check left values
                while (toSort[leftIndex].CompareTo(pivot)<0)
                {
                    leftIndex++;
                }
                //check right values
                while (toSort[rightIndex].CompareTo(pivot) >0)
                {
                    rightIndex--;
                }
                //swap
                if (leftIndex <= rightIndex)
                {
                    var tmp = toSort[leftIndex];
                    toSort[leftIndex] = toSort[rightIndex];
                    toSort[rightIndex] = tmp;

                    //move towards pivot
                    leftIndex++;
                    rightIndex--;
                }
            }
            //continues to sort left and right of pivot
            if (left < rightIndex)
            {
                qSort(toSort, left, rightIndex);
            }
            if (leftIndex < right)
            {
                qSort(toSort, leftIndex, right);
            }
        }


    }

Answer 1

您有一个 class 构造函数，它期望列表作为参数，并且正在对该列表进行排序。

基本上是这个代码：

private List<T> toSort;
public Sort(List<T> sortList)
{
    toSort = sortList;
    quickSort();
}

现在，List<T> 是一个引用类型，这意味着如果您将它作为参数传递给修改它的其他代码，调用代码将看到修改后的列表。

Answer 2

因为List<T>是一个Reference Type.

There are two kinds of types in C#: reference types and value types. Variables of reference types store references to their data (objects), while variables of value types directly contain their data. With reference types, two variables can reference the same object; therefore, operations on one variable can affect the object referenced by the other variable. With value types, each variable has its own copy of the data, and it is not possible for operations on one variable to affect the other (except in the case of in, ref and out parameter variables; see in, ref and out parameter modifier).

在您的示例中，变量 toSort 和私有字段 Sort.toSort 都引用完全相同的列表。

Answer 3

如果您操作一个作为参数传递的集合，那么每个 class 能够访问该集合的同一实例的集合都会被操作，这就是为什么您真的不需要 return一个新的丢失。

要了解有关引用和值类型的更多信息，请阅读： Value Types Reference Types

如果您想了解 .net 框架如何帮助您对集合进行排序，请阅读 here

Answer 4

之所以有效，是因为您正在进行 in-place 排序。没有制作列表的副本，所有更改都是在您 通过引用类型 传递的原始列表上进行的。同样的事情适用于数组和引用类型的任何其他传递。

如果我可以建议使用通用静态方法使您的代码更快更简洁一些，如下所示：

public static class SortMethods
{
    public static <T> List<T> QuickSort(this List<T> toSort) where T : IComparable<T>
    {
        QuickSort(toSort, 0, toSort.Count - 1);
        return toSort;
    }
    private static <T> void QuickSort(this List<T> toSort, int left, int right) where T : IComparable<T>
    {
        // perform quick sort
    }
}

然后您可以通过以下两种方式之一调用它：

list.QuickSort();
SortMethods.QuickSort(list);

使用递归和泛型创建快速排序

Creating a quick sort using recursion and generics

c#

sorting

generics

quicksort

icomparable