Инверсия, сортировка и перемешивание массивов

Инверсия массива Для изменения порядка элементов в массиве на противоположный используется метод reverse. Этот метод изменяет порядок элементов в исходном массиве и возвращает ссылку на самого себя. var a = [1, 2, 3, 4, 5]; a.reverse(); alert(a); // 5,4,3,2,1 При этом пропуски в массиве сохраняются. var a = []; a[1] = 1; a[2] = 2; alert(a + ' : ' + [0 in a, 1 in a, 2 in a]); // ,1,2 : false,true,true a.reverse(); alert(a + ' : ' + [0 in a, 1 in a, 2 in a]); // 2,1, : true,true,false Сортировка элементов Метод sort сортирует элементы массива, изменяя порядок элементов в исходном массиве. sort принимает единственным аргументом функцию, сравнивающую элементы массива. Если функция сравнения не задана, то элементы сортируются в лексикографическом порядке. var a = ['d', 'b', 'a', 'e', 'c']; a.sort(); alert(a); // a,b,c,d,e Даже если отсортировать массив, состоящий только из чисел, они всё равно будут отсортированы как строки, а не как числа. var a = [4, 2, 10, 5, 30]; a.sort(); alert(a); // 10,2,30,4,5 Чтобы отсортировать массив чисел, необходимо передать методу sort функцию сравнения двух чисел. Функция, передаваемая методу sort, поочерёдно вызывается для различных пар элементов массива, и должна вернуть отрицательное число, если первый аргумент меньше второго, положительное число, если первый аргумент больше второго, и 0, если они равны. Таким образом код, сортирующий массив чисел будет выглядеть следующим образом. var a = [4, 2, 10, 5, 30]; a.sort(function(a, b) { return a - b; }); alert(a); // 2,4,5,10,30 С помощью callback-функции массивы можно сортировать по любому критерию. Например, отсортировать массив объектов по значению какого-либо свойства, или даже нескольких свойств. var a = [ {x: 4, y: 2}, {x: 3, y: 5}, {x: 1, y: 5}, {x: 3, y: 2}, {x: 4, y: 1} ]; a.sort(function(a, b) { // Сортируем по полю x, если оно одинаковое, то по полю y return (a.x - b.x) || (a.y - b.y); }); alert(a.map(function(a) { return 'x = ' + a.x + ', y = ' + a.y }).join('\n')); // x = 1, y = 5 // x = 3, y = 2 // x = 3, y = 5 // x = 4, y = 1 // x = 4, y = 2 Callback-функция обязательно должна возвращать число, в противном случае Internet Explorer выбросит ошибку, а остальные браузеры просто не отсортируют массив. Пропуски в массиве, равно как и элементы массива, равные undefined при сортировке не учитываются вовсе. Данные элементы просто оказываются в конце массива. var a = []; a[1] = 1; a[3] = undefined; alert(a); // ,1,, a.sort(function(a, b) { alert([a, b]); // Функция не будет вызвана ни разу, в массиве только один значащий элемент return 0; }); alert(a); // 1,,, Чтобы отсортировать массив в обратном лексикографическом порядке, достаточно после вызова sort без аргументов вызвать метод reverse. Для остальных типов сортировки придётся видоизменять callback-функцию. var a = [4, 2, 10, 5, 30]; a.sort(function(a, b) { return b - a; }); alert(a); // 30,10,5,4,2 Перемешивание элементов В JavaScript нет встроенных средств для перемешивания элементов массива. Самый популярный способ реализации перемешивания это вызов метода sort с callback-функцией, возвращающей случайное число. Array.prototype.shuffle = function() { return this.sort(function() { return 0.5 - Math.random(); }); }; Однако данный способ нельзя назвать эффективным, он переменшивает по разному в разных браузерах, но всегда очень неравномерно. Создадим тест: будем многократно перемешивать массив из десяти последовательных чисел от 0 до 9, и подсчитаем, сколько раз каждое из чисел окажется на первом месте. Array.prototype.shuffle = function() { return this.sort(function() { return 0.5 - Math.random(); }); }; var N = 10000, a = [], i; for (i = 0; i < 10; i++) { a[i] = 0; } for (i = 0; i < N; i++) { a[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9].shuffle()[0]]++; } alert(a); В Firefox результат теста будет сильно похож на 1860,1841,1223,704,633,613,409,255,1226,1236, т.е. чаще всего под нулевым индексом перемешанного массива будет нулевой же индекс исходного массива, а реже всего — седьмой. В IE и Safari результаты совсем другие, но не лучше: 471,890,855,1362,1090,1088,844,1252,1084,1064, тут нулевой индекс исходного массива будет гораздо реже оказываться под нулевым индексом в отсортированном массиве. В Opera разброс гораздо больше, но упорядоченнее: 2810,2861,1391,233,206,914,946,459,86,94. В Chrome похожая ситуация, но ещё хуже: 2868,2930,1962,1076,574,291,164,82,33,20. Вывод — использовать такое перемешивание очень неэффективно. Гораздо лучше перебрать все элементы и поменять их на произвольный с большим или равным индексом. Только перебирать элементы будем с конца массива, чтобы взятие случайного числа было проще. Array.prototype.shuffle = function() { for (var i = this.length - 1; i > 0; i--) { var num = Math.floor(Math.random() * (i + 1)); var d = this[num]; this[num] = this[i]; this[i] = d; } return this; } Предыдущий тест для такого способа будет давать для каждого индекса 1000 плюс-минус 40 повторений, что является, несомненно, более хорошим результатом. Более того, данный способ быстрее предыдущего в разных браузерах на 40-70%.