Nota kajian JavaScript: Pengisihan rawak kemahiran arrays_javascript

Bacaan yang disyorkan: Kaedah Jumlah Tatasusunan Nota Kajian JavaScript

Tambah, padam, ubah suai dan semak tatasusunan nota kajian JavaScript

JavaScript menyediakan kaedah sort() dan reverse() untuk menyusun semula item tatasusunan. Tetapi sering kali kedua-dua kaedah ini tidak dapat memenuhi keperluan perniagaan sebenar kami, seperti shuffling rawak dalam permainan poker.

Dalam artikel ini, mari kita pelajari cara untuk mencapai kesan contoh di atas, serta beberapa pengetahuan berkaitan tentang pengisihan rawak tatasusunan.

Saya menyemak maklumat yang berkaitan tentang pengisihan rawak tatasusunan di Internet, dan saya melihat Math.random(). Buka pengawal penyemak imbas dan masukkan:

Math.random()

Seperti yang dapat dilihat dari gambar, Math.random() memperoleh nombor rawak antara 0 dan 1. Seperti yang kita semua tahu, sort() boleh memanggil fungsi sebagai parameter Jika fungsi mengembalikan nilai -1, ia bermakna item a dalam tatasusunan diletakkan sebelum item b. Dengan cara ini, anda boleh menulis fungsi rawak untuk membandingkan nombor yang dijana secara rawak oleh Math.random() dengan 0.5 Jika lebih besar daripada .5, ia akan mengembalikan -1 (a diletakkan di hadapan b), jika tidak akan mengembalikan 1 (b diletakkan di hadapan a):

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

Lihat contoh:

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

Dengan cara ini, kesan contoh pada permulaan artikel boleh dicapai:

Walaupun kaedah sebelumnya mencapai pengisihan rawak tatasusunan, ia sentiasa merasakan bahawa kedudukan setiap elemen yang dihantar ke tatasusunan baharu bukanlah rawak. Sama seperti contoh sebelumnya, elemen dengan nilai 1 dalam array arr mempunyai nilai kunci asalnya 0. Selepas pengisihan rawak, kebarangkalian nilai kunci 1 ialah 0-8 adalah sama. Kemudian ia berkurangan di sini kerana kaedah sort() membandingkan secara berurutan.

Untuk menangani fenomena ini, kita boleh menggunakan kaedah rekursif berikut untuk menanganinya:

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

Dalam kes ini, kita boleh menggunakannya seperti ini:

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

Hasil keluaran:

Selepas melaksanakan fungsi randomSort(arr, newArr), arr tatasusunan asal dikosongkan.

Jika anda menggunakan kaedah ini untuk melakukan contoh shuffling pada permulaan artikel, anda perlu menetapkan semula tatasusunan pukePic dalam fungsi resetPic():

Selain daripada dua kaedah di atas, @Traveller berkongsi artikel "Pelaksanaan Algoritma Isih Rawak untuk Elemen Tatasusunan" pada DIV.IO Artikel ini menyediakan tiga kaedah pelaksanaan untuk pengisihan item tatasusunan secara rawak:

Gunakan kaedah isihan tatasusunan untuk mengisih unsur tatasusunan secara rawak

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

Tukar unsur secara rawak dalam tatasusunan

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

Ekstrak elemen secara rawak daripada tatasusunan asal dan tambahkannya pada tatasusunan baharu

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
}

Algoritma shuffling

Prinsip asas pengisihan rawak tatasusunan ialah algoritma kocok (Fisher–Yates shuffle):

ialah algoritma yang mengganggu susunan set terhingga

Prinsip

Tentukan tatasusunan (kocok), panjang (panjang) ialah panjang tatasusunan asal (arr)
Ambil 0 ke indeks (awal 0) nilai rawak rand, kocok[indeks] = kocok[rand], kocok[rand] = arr[indeks]
index++ ; Ulang langkah 2 sehingga indeks = panjang -1
Ia adalah proses tugasan yang dikocok daripada 0 kepada panjang-1, dan nilai yang baru ditambah ialah arr[index]. nilai pendua, jadi dikocok[rand] adalah sama dengan nilai arr[indeks] yang baru ditambah

kaedah kocok dalam garis bawah.js

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

Aplikasi praktikal:

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

Hasil keluaran oleh Chrome adalah seperti berikut:

Begitu juga, gunakan algoritma shuffling untuk melengkapkan contoh pada permulaan artikel:

Terdapat juga cara penulisan yang lebih ringkas dan mudah difahami:

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

Ringkasan

Artikel ini terutamanya meringkaskan dan mengumpulkan maklumat yang berkaitan tentang pengisihan rawak tatasusunan. Sudah tentu, terdapat banyak cara untuk mencapai fungsi yang sama di pasaran. Ini baru dikumpulkan dan disusun di sini.

Kandungan di atas adalah pengenalan kepada pengisihan rawak tatasusunan dalam nota kajian JavaScript yang diperkenalkan oleh editor saya harap ia akan membantu anda!