preface

Let’s start with a piece of code

function randArr (arr) {
    return arr.sort(() => {
        return(Math. The random (0.5); }); }Copy the code

The goal is to get a given array out of order.

Using the array sort method, judge the random value of 0~1 and the size of 0.5, to achieve pseudo sort.

Why is it pseudo sort? There’s nothing wrong with the logic of the code.

Right, from this point of view, simple and clear, perfect to achieve the demand, in the spirit of everything to ancestral graves plane. Take a look at the internal implementation of this code.

Browser implementation

ECMA Script

The elements of this array are sorted. The sort is not necessarily stable (that is, elements that compare equal do not necessarily remain in their original order). If comparefn is not undefined, it should be a function that accepts two arguments x and y and returns a negative value if x < y, zero if x = y, or a positive value if x > y.

Generally speaking, I don’t care if your sorting algorithm is stable or not, but you can customize the sorting rules for the user

This help browser a listen to, good ah, the eldest brother hair words, that eight immortals cross the sea each show his powers, each think their implementation is the most cattle force.

The sort of Chrome

Based on V8 engine, its sort calculation has been a lot of optimization, but the core is less than or equal to 10 array with insertion sort (stable), greater than 10 using quickSort (unstable), source.

FireFox’s sort

Based on the SpiderMonkey engine, using merge sort (stable), source code

The sort of Safari

Based on the Nitro (JavaScriptCore) engine, if no custom sorting rule is passed in, bucket sorting is adopted (not necessarily stable, bucket sorting stability depends on the stability of bucket sorting, so its stability is uncertain). , incoming custom rules, using merge sort (stable), source code

Microsoft Edge/IE9+

Based on the Chakra engine, using fast (unstable) source code

Okay, the guy who said sort can’t be pseudo-sort, have you seen my 40-meter machete?

What? You’re tough. I like your personality.

Making the great god of var letters = [‘ A ‘, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’, ‘H’, ‘I’, ‘J’].

After 10,000 out-of-order processing, it is found that the element is likely to stay in its initial position.

Address: HOUCe/shuffle-array

You see? Short people admit it. They stand at attention.

Fisher-yates shuffling algorithm

To achieve true out-of-order, let’s look at it as long as each element is equally likely to appear in every position.

Boy, have you ever heard of the palm of the Buddha?

There is a Fisher-Yates shuffling algorithm, to meet your various chaotic needs, inexpensive, killing goods home travel essential boutique ~ (in fact, there are three versions, interested in their own search)

A general description of the algorithm

1. Find the butt of the array (the last element);

2. A random position between the head and the butt;

3. Swap elements.

4. At this time, the butt is already out of order, so the butt moves forward;

5. If your butt doesn’t hit your head, continue steps 1 to 4

function shuffle(arr) {
    let length = arr.length,
        r      = length,
        rand   = 0;

    while (r) {
        rand = Math.floor(Math.random() * r--);
        [arr[r], arr[rand]] = [arr[rand], arr[r]];
    }

    return arr;
}Copy the code

reference

Github.com/HOUCe/shuff…

En.wikipedia.org/wiki/Fisher…

Efe.baidu.com/blog/talk-a…

Segmentfault.com/a/119000001…