JavaScript学習メモ：配列のランダムソート_JavaScriptスキル

推奨読書: JavaScript 学習ノート Array Sum メソッド

JavaScript 学習ノートの配列を追加、削除、変更、確認します

JavaScript は、配列項目を並べ替えるための sort() メソッドと reverse() メソッドを提供します。しかし、多くの場合、これら 2 つの方法では、ポーカー ゲームのランダム シャッフルなど、実際のビジネスのニーズを満たすことができません。

この記事では、上記の例の効果を実現する方法と、配列のランダムな並べ替えに関する関連知識を学びましょう。

インターネットで配列のランダムソートに関する関連情報を調べたところ、Math.random() を見つけました。ブラウザ コントローラを開き、次のように入力します:

Math.random()

図からわかるように、Math.random() は 0 から 1 までの乱数を取得します。ご存知のとおり、sort() はパラメーターとして関数を呼び出すことができます。関数が値 -1 を返した場合、配列内の項目 a が項目 b よりも前にランク付けされていることを意味します。このようにして、Math.random() によってランダムに生成された数値を 0.5 と比較するランダム関数を作成できます。数値が 0.5 より大きい場合は -1 (a は b の前にランク付けされます) を返します。 1 を返します (b は a の前にランクされます):

function randomSort(a, b) {
return Math.random() > 0.5 ? -1 : 1;
}

例を見てみましょう:

var arr = [1,2,3,4,5,6,7,8,9];
arr.sort(randomSort);

このようにして、記事の冒頭の例の効果を実現できます。

前の方法は配列のランダムな並べ替えを実現しますが、新しい配列に送信される各要素の位置がランダムではないように常に感じられます。前の例と同様に、配列 arr 内の値 1 を持つ要素の元のキー値は 0 です。ランダムな並べ替え後、キー値 1 が 0 ～ 8 になる確率は同じです。次に、sort() メソッドが順番に比較するため、ここでは減少しています。

この現象に対処するには、次の再帰的方法を使用して対処できます。

function randomSort(arr, newArr) {
// 如果原数组arr的length值等于1时，原数组只有一个值，其键值为0
// 同时将这个值push到新数组newArr中
if(arr.length == 1) {
newArr.push(arr[0]);
return newArr; // 相当于递归退出
}
// 在原数组length基础上取出一个随机数
var random = Math.ceil(Math.random() * arr.length) - 1;
// 将原数组中的随机一个值push到新数组newArr中
newArr.push(arr[random]);
// 对应删除原数组arr的对应数组项
arr.splice(random,1);
return randomSort(arr, newArr);
}

この場合、次のように使用できます:

for (var i = 0; i < 10; i++) {
var arr=[1,2,3,4,5,6,7,8,9];
var newArr=[];
randomSort(arr,newArr);
console.log(newArr);
}

出力結果:

randomSort(arr, newArr) 関数を実行すると、元の配列 arr はクリアされます。

このメソッドを使用して記事の冒頭にあるシャッフルの例を実行する場合は、resetPic() 関数で pukePic 配列をリセットする必要があります。

上記の 2 つの方法に加えて、@Traveller が DIV.IO で記事「配列要素のランダムな並べ替えアルゴリズムの実装」を共有しました。この記事では、配列項目のランダムな並べ替えのための 3 つの実装方法が提供されています。

配列の並べ替えメソッドを使用して、配列要素をランダムに並べ替えます

Array.prototype.shuffle = function(n) {
var len = this.length ,
num = n ? Math.min(n,len) : len,
arr = this.slice(0);
arr.sort(function(a,b){
return Math.random()-0.5;
});
return arr.slice(0,num-1);
}

配列内の要素をランダムに交換します

lib = {}
lib.range = function(min,max) {
return min + Math.floor(Math.random()*(max-min+1));
}

Array.prototype.shuffle = function(n) {
var len = this.length,
num = n ? Math.min(n,len) : len,
arr = this.slice(0),
temp,
index;
for (var i=0;i<len;i++){
index = lib.range(i,len-1);
temp = arr[i];
arr[i] = arr[index];
arr[index]=temp;
}
return arr.slice(0,num);
}

元の配列から要素をランダムに抽出し、新しい配列に追加します

lib = {}
lib.range = function(min,max) {
return min+Math.floor(Math.random()*(max-min+1));
}
Array.prototype.shuffle = function(n) {
var len = this.length, 
num = n ? Math.min(n,len) : len,
arr = this.slice(0),
result=[],
index;
for (var i=0;i<num;i++){
index = lib.range(0,len-1-i);
// 或者 result.concat(arr.splice(index,1))
result.push(arr.splice(index,1)[0]);
}
return result
}

シャッフルアルゴリズム

配列のランダムな並べ替えの基本原理は、シャッフル アルゴリズム (フィッシャー – イェーツ シャッフル) です。

は有限集合の順序を崩すアルゴリズムです

原則

配列 (シャッフル) を定義します。長さ (length) は元の配列 (arr) の長さです

ランダム値 rand に 0 をインデックス (初期値 0)、shuffled[index] = shuffled[rand]、shuffled[rand] = arr[index]
Index++ ; Index = 長さ -1
になるまでステップ 2 を繰り返します。 0からlength-1までシャッフルして代入する処理で、新しく追加される値がarr[index]になります。 shuffled[index]の値は、代入された要素のうちのランダムな値shuffled[rand]になります。値が重複しているため、shuffled[rand] は新しく追加された値 arr[index]
と等しくなります。

underscore.js の shuffle メソッド

function random(min, max) {
if (max == null) {
max = min;
min = 0;
}
return min + Math.floor(Math.random() * (max - min + 1));
};
function shuffle(arr) {
var length = arr.length,
shuffled = Array(length);
for (var index = 0, rand; index < length; index++) {
rand = random(0, index);
if (rand !== index) shuffled[index] = shuffled[rand];
shuffled[rand] = arr[index];
}
return shuffled;
}

実際の応用:

var arr = [1,2,3,4,5,6,7,8,9];
for (var i = 0; i < 10; i++){
console.log(shuffle(arr));
}

Chrome によって出力された結果は次のとおりです:

同様に、シャッフル アルゴリズムを使用して、記事の冒頭の例を完成させます。

もっとシンプルで分かりやすい書き方もあります:

function shuffle(arr) {
var i, 
j,
temp;
for (i = arr.length - 1; i > 0; i--) {
j = Math.floor(Math.random() * (i + 1));
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
return arr;
};

概要

この記事は主に配列のランダムソートに関する関連情報を要約し、収集しています。もちろん、市場には同様の機能を実現するための方法がたくさんあります。これらはここで収集して整理したものです。より良い方法がある場合は、コメントで共有してください。

上記の内容は、編集者が紹介したJavaScript学習ノートにおける配列のランダムソートの紹介です。