JS rawak shuffling algoritma array rawak sorting_javascript kemahiran

Bacaan yang disyorkan: Nota kajian JavaScript: Menambah, memadam, mengubah suai dan menyemak tatasusunan

Kaedah Jumlah Tatasusunan Nota Kajian JavaScript

Nota Kajian JavaScript Susunan Rawak Isih

Algoritma shuffling ialah istilah yang agak jelas, yang pada asasnya membolehkan elemen dalam tatasusunan disusun secara rawak. Sebagai contoh, kita mempunyai tatasusunan seperti yang ditunjukkan dalam rajah di bawah Panjang tatasusunan ialah 9, dan nilai unsur dalam tatasusunan ialah 1~9:

Bermula dari tatasusunan di atas, apa yang perlu kita lakukan ialah mengganggu susunan elemen dalam tatasusunan:

Pelaksanaan kod

Entri shuffle Fisher–Yates di Wikipedia menyediakan pengenalan terperinci kepada algoritma shuffling Algoritma yang ditunjukkan di bawah juga ditulis berdasarkan teori:

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); 

Dalam kod di atas, kami mencipta kaedah shffle(), yang digunakan untuk menyusun secara rawak elemen dalam tatasusunan. Di samping itu, kami memasang kaedah ini di bawah prototaip objek Array, jadi mana-mana tatasusunan boleh memanggil kaedah ini secara langsung:

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

Cara ia berfungsi

Selepas membaca kod, mari lihat apa yang dilakukannya kepada tatasusunan. Pertama, kaedah ini memilih elemen terakhir tatasusunan:

Seterusnya, tentukan julat untuk memilih unsur rawak Daripada elemen pertama tatasusunan kepada elemen yang dipilih dalam langkah sebelumnya, kesemuanya tergolong dalam julat ini:

Selepas menentukan julat, pilih nombor secara rawak daripadanya, dengan mengandaikan bahawa elemen yang dipilih secara rawak ialah 4:

Kemudian tukar nilai elemen terakhir dan elemen yang dipilih secara rawak:

Selepas pertukaran di atas selesai, ia adalah sama dengan kita melengkapkan pemprosesan rawak bagi elemen terakhir tatasusunan. Seterusnya pilih elemen kedua hingga terakhir dalam tatasusunan:

Sebab kami memprosesnya dari belakang ke hadapan adalah lebih mudah untuk menentukan julat pemilihan rawak. Kali ini kita menganggap bahawa unsur yang diperoleh secara rawak ialah 2:

Kemudian tukarkan nilai unsur praakhir dan unsur kedua untuk melengkapkan susunan rawak unsur praakhir. Kemudian pilih elemen ketiga hingga terakhir dan ulangi operasi sebelumnya:

Selebihnya adalah beberapa kerja yang berulang, jadi saya tidak akan memperkenalkannya banyak.

Menganalisis kod

Dalam bahagian sebelumnya, saya menggunakan ilustrasi untuk menunjukkan proses kocok. Sekarang mari kita lihat proses kocok daripada kod itu sendiri. Mari mulakan dengan fungsi shuffle:

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;
} 

Fungsi shuffle dipasang di bawah prototaip objek Array, menjadikannya mudah untuk tatasusunan untuk memanggil fungsi secara terus. Di dalam fungsi shuffle, ini merujuk kepada tatasusunan yang mana shuffle dipanggil:

var input = this;

Dalam kod di atas, saya merujuk ini dengan pembolehubah baharu, iaitu tatasusunan yang dipanggil fungsi shuffle. Seterusnya, mari kita lihat perkara yang dilakukan di dalam gelung untuk:

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;
}

Gelung ini digunakan untuk melelaran melalui semua elemen dalam semua tatasusunan dan melakukan pertukaran rawak. Ambil perhatian bahawa susunan traversal adalah dari belakang ke hadapan, iaitu, bermula dari elemen pada input kedudukan. panjang-1 sehingga elemen pertama dalam tatasusunan dilalui. Kedudukan semasa traversal ditentukan oleh pembolehubah i.

Pembolehubah i di sini ialah elemen yang dipilih dalam legenda di atas:

Algoritma shuffling

Seterusnya, dua baris kod digunakan untuk memilih elemen rawak dalam julat yang ditentukan:

var randomIndex = Math.floor(Math.random()*(i+1)); 
var itemAtIndex = input[randomIndex];

变量 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随机洗牌算法之给数组随机排序的相关叙述，希望对大家有所帮助！