Использует ли метод Sort() в C# рекурсию?
Недавно я прочитал, что C# использует алгоритм быстрой сортировки для сортировки массива. Что я хотел бы знать, использует ли С# рекурсивный или итеративный подход?
Я нашел эту ссылку, и мне кажется, что они используют итеративный подход. Мне просто интересно, правда ли, что C# использует итеративную реализацию алгоритма QuickSort?
Ответы 1
Две вещи:
C# перешел от QuickSort к IntrospectiveSort, как показывает ваша ссылка. Вы можете увидеть комментарии и поддержку совместимости в исходном коде Sort.
Код, на который вы ссылаетесь, является рекурсивным. В конце цикла происходит рекурсивный вызов:
private void IntroSort(int lo, int hi, int depthLimit) { while (hi > lo) { int partitionSize = hi - lo + 1; if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold) { // ... InsertionSort(lo, hi); return; } // ... int p = PickPivotAndPartition(lo, hi); IntroSort(p + 1, hi, depthLimit); // <--- recursive call hi = p - 1; } }Следующая итерация цикла берет левый раздел, а рекурсивный вызов — правый раздел.
Спасибо за ваш ответ! Мне просто интересно, почему они используют рекурсивный подход? Я спрашиваю, потому что часто слышал и слушал, что рекурсия менее производительна, чем итеративный подход.
Рекурсия - это итерация, в любом случае это рекурсия..?
Извините, @flackoverstow, я не понимаю, что вы хотите сказать.
Мне следовало бы использовать @Learner - это было скорее ответом на их вопросы о производительности и т. д., рекурсия в любом случае является формой итерации; в итерации у вас есть тело цикла с управляющей переменной, в рекурсии у вас есть тело метода с управляющей переменной - по сути, они ничем не отличаются.
@flackoverstow, чтобы превратить эту рекурсию в просто итерацию, вам понадобится нечто большее, чем управляющая переменная: вам понадобится стек, чтобы отслеживать предыдущие состояния (включая состояние цикла, который уже там находится).
Возможно, это поможет объяснить мою точку зрения: итеративный подход с использованием стека и рекурсивный подход с использованием стека по сути ничем не отличаются. Таким образом, производительность, по сути, не будет отличаться; мы не обнаружим, что Sort() ускорился в 10 раз за счет отказа от используемого рекурсивного подхода
Рекурсивный вызов правого раздела происходит перед обратным циклом для обработки левого раздела.