<p>я сделал несколько измерений того, насколько случайны результаты этого случайного рода ...</p><p>моя техника состояла в том, чтобы взять небольшой массив [1,2,3,4] и создать все (4! = 24) его перестановки. затем я применил бы функцию перемешивания к массиву большое количество раз и посчитал, сколько раз генерируется каждая перестановка. хороший алгоритм перетасовки распределяет результаты довольно равномерно по всем перестановкам, в то время как плохой не приведет к такому равномерному результату.</p><p>используя приведенный ниже код, я протестировал firefox, opera, chrome, ie6/7/8.</p><p>
удивительно для меня, случайная сортировка и реальное перемешивание создали одинаково равномерное распределение. похоже, что (как многие и предполагали) основные браузеры используют сортировку слиянием. это, конечно, не означает, что не может быть браузера, который работает по-другому, но я бы сказал, что это означает, что этот метод случайной сортировки достаточно надежен для использования на практике.
</p><p><strong>правка:</strong> этот тест не правильно измерял случайность или ее отсутствие. смотрите другой ответ, который я написал.</p><p><strong>но с точки зрения производительности функция случайного выбора, предложенная кристофом, была явным победителем.</strong> даже для небольших четырехэлементных массивов реальное перемешивание выполнялось примерно в два раза быстрее, чем случайная сортировка!</p><pre> // функция перемешивания, опубликованная кристофом. var shuffle = function (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; } возвращаемый массив; }; // функция случайной сортировки var rnd = function () { return math.round (math.random ()) - 0.5; }; var randsort = function (a) { return a.sort (rnd); }; var permutations = function (a) { if (a.length == 1) { возвращает [a]; } else { var perms = []; для (var i = 0; i <a.length; i ++) { var x = a.slice (i, i + 1); var xs = a.slice (0, i) .concat (a.slice (i + 1)); var subperms = перестановки (xs); для (var j = 0 ; j <subperms. длина; j ++) { perms.push (x.concat (subperms [j])); } } возврат перми; } }; var test = function (a, iterations, func) { // init permutations var stats = {}; var perms = permutations (a); for (var i in perms) { stats ["" + perms [i]] = 0; } // много раз перемешиваем и собираем статистику var start = new date (); для (var i = 0; i <итерации; i ++) { var shuffled = func (a); stats ["" + shuffled] ++; } var end = new date (); // форматировать результат var arr = []; for (var i in stats) { arr.push (i + "" + stats [i] ); } return arr.join ("\ n") + "\ n\nвремя выполнения:" + ((конец - начало)/1000) + "секунды."; }; alert ("случайная сортировка:" + test ([1,2,3,4], 100000, randsort)); alert ("shuffle : "+ test ([1,2,3,4], 100000, shuffle)); </pre>

<p>интересно, что <strong> microsoft использовала ту же технику </strong> на своей странице случайного выбора браузера.</p><p>они использовали немного другую функцию сравнения:</p><pre><code>function randomsort(a,b) { return (0.5 - math.random()); } </code></pre><p>выглядит для меня почти так же, но <strong> <a href="http://www.robweir.com/blog/2010/02/microsoft-random-browser-ballot.html">оказалось, что это не так случайно ...</a> </strong></p><p>поэтому я снова сделал несколько тестов с той же методологией, которая использовалась в связанной статье, и действительно - оказалось, что метод случайной сортировки дал неверные результаты. новый тестовый код здесь:</p><pre><code>function shuffle(arr) { arr.sort(function(a,b) { return (0.5 - math.random()); }); } function shuffle2(arr) { arr.sort(function(a,b) { return (math.round(math.random())-0.5); }); } function shuffle3(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; } var counts = [ [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0] ]; var arr; for (var i=0; i<100000; i++) { arr = [0,1,2,3,4]; shuffle3(arr); arr.foreach(function(x, i){ counts[x][i]++;}); } alert(counts.map(function(a){return a.join(", ");}).join("\n")); </code></pre>

<p>это взлом, конечно. на практике алгоритм с бесконечной петлей маловероятен. если вы сортируете объекты, вы можете перебрать массив координат и сделать что-то вроде:</p><pre><code>for (var i = 0; i < coords.length; i++) coords[i].sortvalue = math.random(); coords.sort(usesortvalue) function usesortvalue(a, b) { return a.sortvalue - b.sortvalue; } </code></pre><p>(а затем повторите их снова, чтобы удалить sortvalue)</p><p>все еще взломать хотя. если вы хотите сделать это красиво, вы должны сделать это трудным путем :)</p>

<p>прошло четыре года, но я хотел бы отметить, что метод случайного сравнения не будет правильно распределен, независимо от того, какой алгоритм сортировки вы используете.</p><p><strong>доказательство</strong></p><ol> <li>для массива элементов <code>n</code> существует в точности перестановка <code>n!</code> (то есть возможные тасования).</li> <li>каждое сравнение в случайном порядке - это выбор между двумя наборами перестановок. для случайного компаратора есть шанс 1/2 выбора каждого набора.</li> <li>таким образом, для каждой перестановки p вероятность оказаться с перестановкой p является дробью со знаменателем 2 ^ k (для некоторого k), поскольку она является суммой таких дробей (например, 1/8 + 1/16 = 3/16 ).</li> <li>для n = 3 существует шесть одинаково вероятных перестановок. таким образом, вероятность каждой перестановки равна 1/6. 1/6 не может быть выражена в виде дроби со степенью 2 в качестве знаменателя.</li> <li>поэтому сортировка монет никогда не приведет к справедливому распределению перемешиваний.</li> </ol><p>единственные размеры, которые могут быть правильно распределены, это n = 0,1,2.</p><hr><p>в качестве упражнения попробуйте нарисовать дерево решений различных алгоритмов сортировки для n = 3.</p><hr><p>в доказательстве есть пробел: если алгоритм сортировки зависит от согласованности компаратора и имеет неограниченное время выполнения с несовместимым компаратором, он может иметь бесконечную сумму вероятностей, которая может суммироваться до 1/6, даже если каждый знаменатель в сумме является степенью 2. попытайтесь найти один.</p><p>кроме того, если у компаратора есть фиксированный шанс дать любой ответ (например, <code>(math.random() < p)*2 - 1</code>, для константы <code>p</code>), приведенное выше доказательство имеет место. если компаратор вместо этого изменяет свои шансы на основе предыдущих ответов, возможно, будет возможно получить справедливые результаты. поиск такого компаратора для данного алгоритма сортировки может быть исследовательской работой.</p>

<p>если вы используете d3, есть встроенная функция тасования (с использованием fisher-yates):</p><pre><code>var days = ['lundi','mardi','mercredi','jeudi','vendredi','samedi','dimanche']; d3.shuffle(days); </code></pre><p>и вот майк подробно расскажет об этом:</p><p> <a href="http://bost.ocks.org/mike/shuffle/">http://bost.ocks.org/mike/shuffle/</a> </p>

<p>вот подход, который использует один массив:</p><p>основная логика:</p><li>начиная с массива из n элементов</li><li>удалить случайный элемент из массива и вставить его в массив</li><li>удалить случайный элемент из первых n - 1 элементов массива и вставить его в массив</li><li>удалить случайный элемент из первых n - 2 элементов массива и вставить его в массив</li><li>...</li><li>удалите первый элемент массива и вставьте его в массив</li><p>код:</p><pre><code>for(i=a.length;i--;) a.push(a.splice(math.floor(math.random() * (i + 1)),1)[0]); </code></pre>