После того, как Джон уже рассмотрел теорию , вот реализация:
function shuffle(array) {
var tmp, current, top = array.length;
if(top) while(--top) {
current = Math.floor(Math.random() * (top + 1));
tmp = array[current];
array[current] = array[top];
array[top] = tmp;
}
return array;
}
Алгоритм - O(n), тогда как сортировка должна быть O(n log n). В зависимости от накладных расходов на выполнение кода JS по сравнению с собственной функцией sort() это может привести к заметной разнице в производительности , которая должна увеличиваться с размерами массива.
В комментариях к ответу Бобобо я заявил, что рассматриваемый алгоритм может не давать равномерно распределенные вероятности (в зависимости от реализации sort()).
Мой аргумент заключается в следующем: алгоритм сортировки требует определенного числа c сравнений, например, c = n(n-1)/2 для Bubblesort. Наша функция случайного сравнения делает результаты каждого сравнения одинаково вероятными, то есть есть 2^c одинаково вероятных результатов. Теперь каждый результат должен соответствовать одной из n! перестановок записей массива, что делает невозможным равномерное распределение в общем случае. (Это упрощение, поскольку фактическое число необходимых сравнений зависит от входного массива, но утверждение все еще должно сохраняться.)
Как указал Джон, само по себе это не является причиной для предпочтения Фишера-Йейтса использованию sort(), поскольку генератор случайных чисел также сопоставит конечное число псевдослучайных значений с перестановками n!. Но результаты Фишера-Йейтса должны быть еще лучше:
Math.random() создает псевдослучайное число в диапазоне [0;1[. Поскольку JS использует значения с плавающей запятой двойной точности, это соответствует 2^x возможным значениям, где 52 ≤ x ≤ 63 (мне лень найти фактическое число). Распределение вероятностей, сгенерированное с помощью Math.random(), перестанет вести себя хорошо, если число атомных событий будет того же порядка.
При использовании Фишера-Йейтса соответствующим параметром является размер массива, который никогда не должен приближаться к 2^52 из-за практических ограничений.
При сортировке с использованием функции случайного сравнения функция в основном заботится только о том, является ли возвращаемое значение положительным или отрицательным, поэтому это никогда не будет проблемой. Но есть и аналогичный: поскольку функция сравнения хорошо себя ведет, 2^c возможные результаты, как указано, одинаково вероятны. Если c ~ n log n, то 2^c ~ n^(a·n), где a = const, что делает, по крайней мере, возможным, что 2^c имеет ту же величину, что и (или даже меньше) n! и, таким образом, приводит к неравномерному распределению, даже если алгоритм сортировки где отобразить на перестановки равномерно. Если это окажет какое-либо практическое влияние, мне не под силу.
Настоящая проблема заключается в том, что алгоритмы сортировки не гарантируют равномерное отображение на перестановки. Легко видеть, что Mergesort делает то, что симметрично, но рассуждения о чем-то вроде Bubblesort или, что более важно, о Quicksort или Heapsort, нет.
Суть: пока sort() использует Mergesort, вы должны быть достаточно безопасными, за исключением угловых случаев (по крайней мере, я надеюсь, что 2^c ≤ n! это угловой случай), если нет все ставки сняты.