В дополнение к другим ответам, это хуже, чем простое перемешивание Фишера-Йейтса, потому что это слишком медленно. Алгоритм qsort равен O (n * log (n)), число Фишера-Йейтса равно O (n).
В Википедии имеется более подробная информация о том, почему этот тип "случайного воспроизведения" обычно не работает так же хорошо, как метод Фишера-Йейтса :
Сравнение с другими тасовками
Алгоритмы
Суета Фишера-Йейтса довольно
эффективный; действительно, его асимптотическое время
и сложность пространства являются оптимальными.
В сочетании с качественным объективным
источник случайных чисел, это также
гарантированно производить непредвзято
Результаты. По сравнению с некоторыми другими
решения, оно также имеет преимущество
что, если только часть полученного
нужна перестановка, может быть
остановился на полпути, или даже
остановился и перезапустился несколько раз,
генерируя перестановку
по мере необходимости. На высоком уровне
языки программирования с быстрым
встроенный алгоритм сортировки,
альтернативный метод, где каждый элемент
из набора, который нужно перетасовать, назначается
случайное число и набор тогда
отсортировано по этим номерам, май
быть быстрее на практике
необходимо], несмотря на то, что хуже
асимптотическая сложность времени (O (n log n)
против O (n)). Как Фишер-Йейтс
в случайном порядке, этот метод также даст
объективные результаты, если правильно
реализовано, и может быть более терпимым
определенных видов смещения в случайном
номера. Тем не менее, необходимо соблюдать осторожность
чтобы убедиться, что назначенный случайный
числа никогда не дублируются, так как
алгоритмы сортировки вообще не будут
элементы порядка случайным образом в случае
галстук. Вариант вышеуказанного метода
который видел некоторое использование в языках
которые поддерживают сортировку с
пользовательские функции сравнения
перемешать список, отсортировав его
функция сравнения, которая возвращает
случайные значения. Однако это не
всегда работать: с рядом
используемые алгоритмы сортировки, результаты
в конечном итоге смещен из-за внутреннего
асимметрия в сортировке
осуществление. [7]
Ссылка на здесь :
еще одна вещь, когда писал это
статья, которую я экспериментировал с различными
версии методов и обнаружены
еще один недостаток в оригинальной версии
(переименован мной в shuffle_sort). я был
неправильно, когда я сказал «это хорошо возвращается
перетасованный массив каждый раз, когда это
называется.»
Результаты не очень хорошо перемешаны
все. Они предвзяты. Плохо. Тот
означает, что некоторые перестановки (т.е.
упорядочения) элементов более вероятны
чем другие. Вот еще один фрагмент
код, чтобы доказать это, снова заимствовано из
обсуждение группы новостей:
N = 100000
A = %w(a b c)
Score = Hash.new { |h, k| h[k] = 0 }
N.times do
sorted = A.shuffle
Score[sorted.join("")] += 1
end
Score.keys.sort.each do |key|
puts "#{key}: #{Score[key]}"
end
Этот код
перемешивает 100000 раз массив из трех
элементы: a, b, c и записи, сколько
раз каждый возможный результат был
достигнуты. В этом случае есть только
шесть возможных заказов, и мы должны
получил каждый около 16666,66 раз. Если
мы попробуем непредвзятую версию shuffle
(shuffle или shuffle_sort_by),
результат, как и ожидалось:
abc: 16517
acb: 16893
bac: 16584
bca: 16568
cab: 16476
cba: 16962
Конечно,
Есть некоторые отклонения, но они
не должен превышать нескольких процентов
ожидаемое значение, и они должны быть
разные каждый раз, когда мы запускаем этот код.
Можно сказать, что распределение
даже.
Хорошо, что произойдет, если мы используем
метод shuffle_sort?
abc: 44278
acb: 7462
bac: 7538
bca: 3710
cab: 3698
cba: 33314
Это не
равномерное распределение на всех. Опять?
Он показывает, как метод сортировки является предвзятым, и подробно объясняет, почему это так. В конце концов он ссылается на Coding Horror :
Давайте посмотрим на правильный
Алгоритм Кнута-Фишера-Йейтса.
for (int i = cards.Length - 1; i > 0; i--)
{
int n = rand.Next(i + 1);
Swap(ref cards[i], ref cards[n]);
}
Вы видите разницу? Я пропустил
это первый раз. Сравните свопы
для колоды из 3 карт:
Naïve shuffle Knuth-Fisher-Yates shuffle
rand.Next(3); rand.Next(3);
rand.Next(3); rand.Next(2);
rand.Next(3);
Наивное перемешивание
в результате получается 3 ^ 3 (27) возможных колод
комбинации. Это странно, потому что
mathemатики говорят нам, что есть
действительно только 3! или 6 возможных
комбинации из трех карточных колод. в
KFY shuffle, мы начинаем с начальной
ордер, своп с третьей позиции
с любой из трех карт, затем поменяйте местами
снова со второй позиции с
оставшиеся две карты.