由js打亂陣列想到的
導語: 在js中,能把陣列隨機打亂的方法有很多,每個方法都有自己的哪些特點呢,同時若想隨機取出陣列中的幾個元素,怎麼辦呢?
在js中,能把陣列隨機打亂的方法有很多,每個方法都有自己的特點。
1. 打亂陣列的方法
這裡主要講解3個打亂陣列的方法。
1.1 隨機從陣列中取出資料
這個方法的詳細操作步驟是:隨機從陣列中取出一個數組放入到新陣列中,然後將該資料從原陣列中刪除,然後再隨機取出下一個數,直到原資料的長度為0。
function randomArrByOut(arr) { let result = []; let arrTemp = [...arr]; // splice會影響原陣列,複製一個新的陣列,防止影響原陣列 while(arrTemp.length) { let index = Math.floor(Math.random() * arrTemp.length); result.push(arrTemp[index]); arrTemp.splice(index, 1); } return result; } let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]; randomArrByOut(arr); // [7, 1, 3, 8, 2, 4, 6, 5, 9] randomArrByOut(arr); // [8, 4, 3, 7, 9, 2, 1, 5, 6]
這個演算法看似是 O(n)
的演算法,但實際上 arr.splice
內部是一個 O(n^2)
的演算法 Array.prototype.splice的內部實現 :外部迴圈用來刪除元素,內部的迴圈用來填充新新增的元素,或後面的元素向前移動,填充剛才被刪除的元素的坑。總的算下來,這個演算法的時間複雜度就是 O(n^3)
了。
1.2 sort方法打亂
還有一種常見的方法就是使用陣列自帶的sort方法來打算陣列,sort方法是直接修改當前的陣列:
function randomSortBySort(arr) { arr.sort(() => Math.random() - 0.5); }
當前環節裡所有的測試均在Chrome中。當我們使用9個數據,經過多次的測試發現,打亂的資料排布並不均勻:
var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]; var n = 10000; var count = {}; while(n--){ randomSortBySort(arr); var index = arr.indexOf(1); count[index] ? count[index]++ : (count[index] = 1); } console.log(count); /* 資料1經過10000次打亂後的分佈規律,主要集中在前2個 0: 2047 1: 1403 2: 947 3: 822 4: 777 5: 822 6: 992 7: 1008 8: 1182 */
我們再把arr的陣列擴充套件為15,再進行測試:
var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]; var n = 10000; var count = {}; while(n--){ randomSortBySort(arr); var index = arr.indexOf(1); count[index] ? count[index]++ : (count[index] = 1); } console.log(count); // {0: 668, 1: 647, 2: 652, 3: 665, 4: 692, 5: 652, 6: 679, 7: 657, 8: 665, 9: 683, 10: 685, 11: 690, 12: 662, 13: 663, 14: 640}
可以發現每次打亂後的分佈比較均勻,每個數字出現在每個位置的機會都是均等的!
在 V8的原始碼中L710行 中可以看到:
function InnerArraySort( array, length, comparefn ) { // In-place QuickSort algorithm. // For short (length <= 22) arrays, insertion sort is used for efficiency. // 雖然註釋是length<=22,但程式碼裡是<=10 // 插入排序 var InsertionSort = function InsertionSort( a, from, to ) { }; var QuickSort = function QuickSort( a, from, to ) { var third_index = 0; while ( true ) { // Insertion sort is faster for short arrays. if ( to - from <= 10 ) { InsertionSort( a, from, to ); return; } // 快排其他的內容 } } QuickSort(array, 0, num_non_undefined); }
sort的內部使用快速排序,當快排拆分後的分割槽裡的資料個數小於等於10個時,則採用插入排序!因此,當資料量比較小的時候,使用 sort
打亂排序時,會造成不均等的分佈!
1.3 洗牌演算法
最後一個經典的陣列打亂演算法就是洗牌演算法:從最後一個數據開始往前,每次從前面隨機一個位置,將兩者交換,直到陣列交換完畢:
function shuffleSort(arr) { var n = arr.length; while(n--) { var index = Math.floor(Math.random() * n); var temp = arr[index]; arr[index] = arr[n]; arr[n] = temp; // ES6的解耦交換方式: [arr[index], arr[n]] = [arr[n], arr[index]]; } }
這種方式是 O(n)
的時間複雜度,而且還能保證一個比較均勻的分佈!高效了很多
2. 從陣列中隨機取出多個元素
這是從陣列中隨機取出幾個元素,上面的一節是將整個陣列進行排序,而這裡只是需要幾個元素而已!
2.1 打亂整個陣列取出資料
當然,先把整個陣列打亂了,然後再取出前n個數據也是其中的一種方法,比如我們這裡就使用洗牌演算法打亂陣列,然後取出資料:
function getRandomArr(arr, num) { var _arr = arr.concat(); var n = _arr.length; // 先打亂陣列 while(n--) { var index = Math.floor(Math.random() * n); [_arr[index], _arr[n]] = [_arr[n], _arr[index]]; } return _arr.slice(0, num); }
不過實際上我們只是需要其中的幾個元素而已,如果把整個陣列都打亂排序,就顯得很浪費。因此這裡我們使用洗牌演算法的思路,稍微改進一下。
2.2 改進型
從最後一個數據開始往前,每次從前面隨機一個位置,將兩者交換,拿到最後的那個資料,直到達到要獲取的個數:
function getRandomArr(arr, num) { var _arr = arr.concat(); var n = _arr.length; var result = []; // 先打亂陣列 while(n-- && num--) { var index = Math.floor(Math.random() * n); // 隨機位置 [_arr[index], _arr[n]] = [_arr[n], _arr[index]]; // 交換資料 result.push(_arr[n]); // 取出當前最後的值,即剛才交換過來的值 } return result; }
3. 總結
陣列中還是有很多的學問的,看看其中的原始碼,也會發現更多的奧妙!