JSランダムシャッフルアルゴリズム配列ランダムソート_JavaScriptスキル

推奨読書: JavaScript 学習ノート: 配列の追加、削除、変更、チェック

JavaScript 学習メモ Array Sum メソッド

JavaScript 学習ノート配列のランダム並べ替え

シャッフル アルゴリズムは比較的鮮明な用語であり、基本的に配列内の要素をランダムに配置することを可能にします。たとえば、以下の図に示すような配列があります。配列の長さは 9 で、配列内の要素の値は 1 ～ 9 です。

上記の配列から始めて、配列内の要素の順序を乱す必要があります。

コードの実装

ウィキペディアのフィッシャー・イェーツ シャッフル エントリでは、シャッフル アルゴリズムについて詳しく説明しています。以下に示すアルゴリズムも理論に基づいて作成されています。

Array.prototype.shuffle = function() {
var input = this;
for (var i = input.length-1; i >=0; i--) {
var randomIndex = Math.floor(Math.random()*(i+1));
var itemAtIndex = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIndex;
}
return input;
}
var tempArray = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
tempArray.shuffle();
// and the result is...
alert(tempArray);

上記のコードでは、配列内の要素をランダムに配置するために使用される shffle() メソッドを作成しました。さらに、このメソッドを Array オブジェクトのプロトタイプの下にマウントしたので、どの配列でもこのメソッドを直接呼び出すことができます。

var tempArray = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
tempArray.shuffle();

仕組み コードを読んだ後、それが配列に何を行うかを見てみましょう。まず、このメソッドは配列の最後の要素を選択します:

次に、配列の最初の要素から前のステップで選択した要素まで、すべてがこの範囲に属する、ランダムな要素を選択する範囲を決定します。

範囲を決定したら、ランダムに選択された要素が 4 であると仮定して、その範囲から数値をランダムに選択します。

次に、最後の要素とランダムに選択された要素の値を交換します:

上記の交換が完了すると、配列の最後の要素のランダム処理が完了したことになります。次に、配列内の最後から 2 番目の要素を選択します:

後ろから前に処理する理由は、ランダムに選択する範囲を決定しやすいためです。今回はランダムに取得した要素が 2: であると仮定します。

最後から2番目の要素と2番目の要素の値を交換して、最後から2番目の要素のランダムな配置が完成します。次に、最後から 3 番目の要素を選択し、前の操作を繰り返します:

残りは繰り返しの作業なので、あまり紹介しません。

コードを分析しています

前のセクションでは、図を使用してシャッフル プロセスを説明しました。次に、コード自体からシャッフル プロセスを見てみましょう。シャッフル機能から始めましょう:

シャッフル関数は Array オブジェクトのプロトタイプの下にマウントされているため、配列から関数を直接呼び出すことが簡単になります。シャッフル関数内で、これはシャッフルが呼び出される配列を指します:

Array.prototype.shuffle = function() {
var input = this;
for (var i = input.length-1; i >=0; i--) {
var randomIndex = Math.floor(Math.random()*(i+1));
var itemAtIndex = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIndex;
}
return input;
}

上記のコードでは、新しい変数でこれを参照しています。これは、シャッフル関数が呼び出される配列です。次に、for ループ内で何が行われるかを見てみましょう:

var input = this;

このループは、すべての配列内のすべての要素を反復処理し、ランダムな交換を実行するために使用されます。走査順序は後ろから前、つまり位置 input.length-1 の要素から始まり、配列内の最初の要素が走査されるまでであることに注意してください。トラバース中の位置は変数 i で指定されます。

for (var i = input.length-1; i >=0; i--) {
var randomIndex = Math.floor(Math.random()*(i+1));
var itemAtIndex = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIndex;
}

ここでの変数 i は、上の凡例で選択された要素です:

シャッフルアルゴリズム

次に、2 行のコードを使用して、指定された範囲内のランダムな要素を選択します。

变量 randomIndex 存储了一个随机数，该随机数可以用作数组的索引，进而提取一个随机元素。注意，该随机数的最大值并不是数组的长度，而是变量 i 的值。

确定了随机元素的索引之后，用新的变量保存该元素的值，然后交换选中元素和随机元素的值：

var itemAtIndex = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIndex;

在这三行代码中，第一行使用新的变量保存了随机元素的值；第二行将选中元素 input[i] 的值赋给随机元素 input[randomIndex]；第三行就随机元素的值 itemAtIndex 赋给选中元素 input[i]。本质上是一个互换两个元素的值的过程，并不难理解。

至此，循环内的逻辑就介绍完了，剩下的都是重复操作。

随机性测试

上图是使用 Highcharts 制作的随机性测试图表，以可视化的方式校验本文中洗牌算法的随机性。每次刷新页面都会重新计算和生成该图表。

生成上图的数据是这样计算而来的：首先创建一个数组（上图使用的数组为 [0, 1, 2 ... 18, 19, 20]），然后使用本文中的洗牌算法重新排序，排序完成后记录每一个元素的值……以此步骤执行 100000 次，最后对同一索引位置上的数值进行求和。如此执行 10000 次之后，索引之间的总值应该相差不大。

由计算可得：

以上内容是小编给大家介绍的JS随机洗牌算法之给数组随机排序的相关叙述，希望对大家有所帮助！