Алгоритмы сортировки обычно работают путем определения функции сравнения. Алгоритмы будут повторно сравнивать два элемента в последовательности для сортировки и менять их местами, если их текущий порядок не соответствует желаемому порядку. Различия между алгоритмами главным образом связаны с поиском наиболее эффективного способа, который возможен в данных обстоятельствах для выполнения всех сравнений.
В процессе проведения всех этих сравнений одни и те же два элемента в последовательности необходимо сравнивать более одного раза! Используя нечисловые данные, чтобы сделать это проще, допустим, у вас есть элементы со значениями «Red» и «Apple». Случайный компаратор выбирает «Apple» в качестве большего элемента при первом сравнении. Позже, если случайный компаратор выберет «Красный» в качестве большего элемента, и этот процесс продолжается, вы можете оказаться в ситуации, когда алгоритм никогда не завершает .
В основном вы получаете счастливчиков , и ничего не происходит. Но иногда нет. .Net довольно хорош в том, что он не просто работает вечно и защищает от этого, но он (и должен! ) создает исключение, когда эти охранники обнаруживают непоследовательное упорядочение.
Конечно, правильный способ справиться с этим в общем случае - это перетасовка Кнута-Фишера-Йейтса.
Кроме того, стоит упомянуть, что бывают случаи, когда простой Фишер-Йейтс не подходит. Одним из примеров является необходимость рандомизации последовательности неизвестной длины ... скажем, вы хотите случайным образом переставить данные, полученные из сетевого потока, не зная, сколько данных находится в потоке, и передать эти данные как можно быстрее работнику нить в другом месте.
В этой ситуации вы не можете идеально рандомизировать эти данные. Не зная длины потока, у вас не будет достаточно информации, чтобы правильно выполнить перемешивание, и даже если вы это сделаете, вы обнаружите, что длина настолько велика, что делает невозможным хранение всего этого в ОЗУ или даже на диске. Или вы можете обнаружить, что поток не будет завершен в течение нескольких часов, но ваш рабочий поток должен начать работать намного раньше. В этом случае вы, скорее всего, согласитесь (и понимаете, что это «установление» важно) для алгоритма, который загружает буфер адекватной длины, рандомизирует буфер, подает примерно половину буфера в рабочий поток, а затем повторно -Заполняет пустую часть буфера, чтобы повторить процесс. Даже здесь вы, вероятно, используете Knuth-Fisher-Yates для шага, который рандомизирует буфер.