Создание быстрой сортировки с использованием рекурсии и обобщений

Question

Я хочу спросить о родовом классе сортировки, который я создал. Я использовал много разных концепций, которые я выучил в этом году, и объединил его в хороший класс, который я могу использовать для сортировки чего угодно (при условии, что если это класс, у класса есть метод 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);
            }
        }


    }

У меня только один вопрос: я использовал быструю сортировку в Интернете, а затем преобразовал ее в собственные шаблоны. Я понимаю, как работает настоящая сортировка. Я просто хочу знать, почему я не должен что-то возвращать. Я немного смущен. Я вижу, что это на самом деле переключение значений списков, но мне интересно, как он получает доступ к списку, который я отправил. Потому что там, где я это называю, я могу просто сделать это

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

Так что я просто использую оригинальный список, и он будет иметь A, B и C в поле со списком.

Если кто-нибудь может объяснить это, я был бы очень признателен!

EDIT:

 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

Это потому, что List<T> является ссылочным типом .

Существует два вида типов в C #: ссылочные типы и типы значений. Переменные ссылочных типов хранят ссылки на свои данные (объекты), в то время как переменные типов значений напрямую содержат их данные. В ссылочных типах две переменные могут ссылаться на один и тот же объект; следовательно, операции с одной переменной могут повлиять на объект, на который ссылается другая переменная. В случае типов значений каждая переменная имеет свою собственную копию данных, и операции с одной переменной не могут влиять на другую (кроме случаев, когда переменные параметров in, ref и out; см. Модификатор параметров in, ref и out). ).

В вашем примере переменная toSort и приватное поле Sort.toSort ссылаются на один и тот же список.

Answer 2

Если вы манипулируете коллекцией, переданной в качестве параметра, то она будет манипулироваться для каждого класса, который может получить доступ к одному и тому же экземпляру коллекции, поэтому вам не нужно возвращать новую потерянную.

Чтобы узнать больше о ссылочных и типах значений, пожалуйста, прочитайте: Типы значений Типы ссылок

Если вы хотите взглянуть на то, как .net framework помогает вам в сортировке коллекций, прочитайте здесь

Answer 3

Причина, по которой это работает, заключается в том, что вы делаете сортировку на месте . Копия списка не производится, и все изменения вносятся в исходный список, который вы передали по типу ссылки . То же самое работает с массивами и любым другим проходом по ссылочному типу.

Если бы я мог предложить сделать ваш код немного быстрее и чище, используйте стандартные статические методы, например:

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

Answer 4

У вас есть конструктор класса, который ожидает список в качестве параметра, и сортирует этот список.

В основном этот код:

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

Теперь List<T> является ссылочным типом, что означает, что если вы передадите его как параметр другому коду, который его модифицирует, вызывающий код увидит измененный список.