The Ordering Problem of javascript Array with Normal Distribution

Looking for a job in the cool weather of 40 in Shanghai in recent days, I am happy in my heart. I have to sit there and sweat for half a day in every interview to come to my senses. I feel the deep love of the world for me. To get down to business, I encountered several written tests during the interview. Among them, there is such a question. Because I have never encountered it in actual work, pay attention to it. The topic is as follows:

There is one array: var arr = [1, 2, 1, 3, 3, 2, 4, 6, 3], which is changed into a normal distribution by processing: [1, 2, 3, 3, 6, 4, 3, 2, 1].

I'll explain the normal distribution briefly. In fact, I can roughly understand it after seeing the processed array, that is, the normal curve reflected in the coordinate axis is bell-shaped, low at both ends and high in the middle, and symmetrical left and right. Because its curve is bell-shaped, people often call it bell-shaped curve.

This is the last question of the interview. When I do it here, the time is tight and the weather is hot, thirsty and hungry. The front desk girl is too good-looking (don't talk nonsense because the algorithm is weak...) After a little thinking, I 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}) // First, arrange the array from small to large to get  [1, 1, 2, 2, 3, 3, 3, 4, 6]
for (;i<l;i++){
   if(i%2==0){
    temp[i/2] = sortArr[i] //  The order in which the subscript is even is put before 
   } else {
    temp[l-(i+1)/2] = sortArr[i] //  If the subscript is odd, put it from back to front 
   }
  }

  console.log(temp) // [1, 2, 3, 3, 6, 4, 3, 2, 1]  It looks perfect, huh 
 })(arr)

Because it was a written test, after I had yy in my mind for a while, I felt that there was no big problem and handed in the paper. Later, the interviewer read the test paper and did not mention this question during the interview, so I felt that there was no problem with this method and I didn't ask again during the interview. However, on the way back, I suddenly thought of one such situation:

var arr = [1,2,3,4,5,6,7,8,9] // 1 Array of regular increments 
 ~(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 arises. . 
 })(arr)

Yes, in this way, 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, which is not a uniform normal distribution. With the increase of the array, the problems will become more and more serious.

Linen belt. . . . I am a flower in bud. Don't do this to me. . .

It seems that the previous code can't be used, We 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 roughly equal. Whether it is an odd-numbered array or an even-numbered array, The array can be divided into two parts (the odd number can also be regarded as an even array after throwing away the maximum value, even if there are multiple identical maximum values, it doesn't matter, and the last one can be removed after sorting from small to large). Or according to the above method, When the subscript is even, put it to the left, When it is odd, put it on the right side, In the growth process of the left and right arrays, when the array length is equal, the sum of the left and right arrays is compared, because it is arranged from small to large, so under normal circumstances, the right side will be larger than the left side, and then the first one on the right side and the last one on the left side can be exchanged for 1 to achieve the purpose of balance. The code is as follows:

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 arrays are equal and right and larger than left 
    }
   }
  }
  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)
 }

 //  Left last 1 A heel to the right 1 Individual exchange 

 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 whole normal distribution will be much more uniform. Do several 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]

It looks good. There is an article in the station to click and view, which is completed with c + +. However, the final result of the article is not a uniform normal distribution, but it is similar to my first program.

I don't know much about c + +, and I didn't run multiple groups of results to see. Interested students can try it as a comparison.

I have only tested all the procedures in chrome. If there are problems with other browsers, I hope to leave a message to inform you. In fact, this thing is not difficult. It is a record. You can use it when you need it.