Home>

### Problem with normal distribution sort of javascript array

Looking for a job in the cool 40 ° weather of Shanghai in recent days,I'm happy in my heartEvery time I interview, I have to sit there and sweat for a long time to get back to my mind.Feeling the deep love this world has for me,Closer to home,I encountered several written tests during the interview.There is such a question,Since I have n’t encountered it in actual work,So watch out,The title is this:

There is an array:var arr=[1,2,1,3,3,2,4,6,3], which is processed into a normal distribution form:[1,2,3,3,6 , 4,3,2,1].

I I will explain briefly about the normal distribution,In fact, you can roughly understand the processed array.Is small at both ends,The middle is large, the normal curve reflected in the coordinate axis is bell-shaped,The two ends are low, the middle is high, and the left-right symmetry is bell-shaped because of its curve.Therefore, it is often called a bell curve.

This is the last question in the interview.When I did this, the time was tight and the weather was hot, thirsty, and hungry. The girl at the front desk was so pretty (don't talk nonsense because the algorithm is weak.. . ), Think a bit and wrote the following code:

``````var arr=[1,2,1,3,3,2,4,6,3]
~ (function (arr) {
var temp=[], i=0, l=arr.length,   sortarr=arr.sort (function (a, b) {return a-b})
for (;i&l;i ++) {
if (i%2 == 0) {
temp [i/2]=sortarr [i] //put the subscripts in even order
} else {
temp [l- (i + 1)/2]=sortarr [i] //put subscripts from the back to the front
}
}
console.log (temp) //[1, 2, 3, 3, 6, 4, 3, 2, 1] looks perfect
}) (arr)
``````

Since it is a written test,After yy programming in my mind for a while,I think there is no major problem and I submit it.Later interviewers looked at the test papers,This question was not mentioned during the interview.So I felt that this method was fine, so I didn't ask again during the interview process.But on the way back,I suddenly thought of a situation like this:

``````var arr=[1,2,3,4,5,6,7,8,9] //a regular increasing array
~ (function (arr) {
var temp=[], i=0, l=arr.length,   sortarr=arr.sort (function (a, b) {return a-b})
for (;i&l;i ++) {
if (i%2 == 0) {
temp [i/2]=sortarr [i]
} else {
temp [l- (i + 1)/2]=sortarr [i]
}
}
console.log (temp) //[1, 3, 5, 7, 9, 8, 6, 4, 2] The problem has occurred.
.
}) (arr)
``````

Yes, so the left and right parts of this array are not symmetrical,With 9 as the center, the left side is 1 + 3 + 5 + 7=16, and the right side is 2 + 4 + 6 + 8=20. Obviously, the left is light and the right is heavy.Is not a uniform normal distribution,As the array grows,The problems that are brought about will get worse.

Linen band. . . . I am a budding flower. Don't do this to me.. .

It seems that the previous code is unusable,Can only rethink the solution,In fact, the core of the problem is to ensure that the left and right sides of the array are equal or approximately equal.Whether it is an odd number of arrays or an even number,The array can be divided into two parts (the odd number can be regarded as an even array after the maximum value is dropped,It doesn't matter if there are multiple identical maximums,Remove the last one after sorting from small to large), or follow the method above,When the subscript is even, put it on the left,When it is odd, put it to the right,During the growth of the left and right arrays,When the arrays are equal in length,Compare the sum of the left and right arrays,Because they are arranged from small to large,So under normal circumstances,The right side will be larger than the left side,Then swap the first on the right with the last on the left to achieve balance.code show as below:

``````var arr=[1,2,3,4,5,6,7,8,9],  sortarr=arr.sort (function (a, b) (return a-b)),  l=arr.length,  temp_left=[], temp_right=[]
function sort (arr) {
var i=0
for (;i<l;i ++) {
var eq=sortarr [i]
i%2 == 0?temp_left.push (eq):temp_right.unshift (eq)
if (i>1) {
if (temp_left.length == temp_right.length &&! compare (temp_left, temp_right)) {
wrap (temp_left, temp_right) //Swap when the arrays are equal and the right side is greater than the left side
}
}
}
return temp_left.concat (temp_right)
}
//array summation
function sum (arr) {
return eval (arr.join ("+"));
}
//Array comparison size
function compare (arr1, arr2) {
return sum (arr1)>= sum (arr2)
}
//The last one on the left is swapped with the first on the right
function wrap (l, r) {
var m=r.shift ()
r.unshift (l.pop ())
l.push (m)
}
console.log (sort (arr)) //get [1, 4, 6, 7, 9, 8, 5, 3, 2]
``````

In this way, the entire normal distribution is much more uniform,Do a few more tests to see the effect:

``````arr=[1,333,444,555,66,7788,909]
console.log (sort (arr))/[1, 444, 909, 7788, 555, 333, 66]
arr=[168.6,177.5,174.2,189.3,167.2,177.6,167.8,175.5]
console.log (sort (arr)) //[167.2, 174.2, 175.5, 189.3, 177.6, 177.5, 168.6, 167.8]
``````

Looks pretty good,There is an article in the stationClick to view, Done in C++, but see the final result of the article,Is not a uniform normal distribution,It's similar to my first program,

I don't know C++ very much, and I haven't run multiple sets of results.Interested students can try it for comparison.

all All the procedures in this article I have only tested in chrome,If there are problems with other browsers,Hope to leave a message,In fact, this thing is not difficult.Right as a record,Can be used when needed.

• Previous Mysql simple tutorial (2)
• Next CodeIgniter method for generating static pages