最近幾天頂著上海40°的涼爽天氣找工作，心裡是開心的不要不要的，每次面試都是要坐那裡出半天汗才能回過神來，感覺到了這個世界對我深深的愛意，言歸正傳，面試過程中碰到了幾次筆試，其中有這麼一道題，由於實際工作中沒遇到過，所以留意下來，題目是這樣：
有一個數組為：var arr = [1,2,1,3,3,2,4,6,3]，通過處理將其變為正態分布的形式： [1,2,3,3,6,4,3,2,1]。
關於正態分布我就簡單解釋一下吧，其實看到處理後的數組大致也能明白，就是兩頭小，中間大，體現到坐標軸裡的正態曲線呈鐘型，兩頭低，中間高，左右對稱因其曲線呈鐘形，因此人們又經常稱之為鐘型曲線。
這道是面試的最後一題，做到這裡的時候時間比較緊張了加上天氣炎熱口渴饑餓前台妹子太好看（別廢話了就是因為算法弱。。。），稍作思考寫了如下代碼：
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}) //先將數組從小到大排列得到 [1, 1, 2, 2, 3, 3, 3, 4, 6]
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, 2, 3, 3, 6, 4, 3, 2, 1] 看起來挺完美哈
})(arr)
由於是筆試，自己在腦海裡邊yy了一會程序後，覺得沒啥大問題就交卷了，後來的面試官看了試卷，在面試過程中並沒有提到這道題，所以覺得這種方法沒什麼問題了就沒在面試過程中再問，不過來回來的路上，我突然想到了一個這樣的情況：
var arr = [1,2,3,4,5,6,7,8,9] // 一個規則遞增的數組
~(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] 問題出現了。。
})(arr)
是的，這樣一來這個數組的左右部分並不是對稱的，以9為中心，左側為1+3+5+7=16，右側為2+4+6+8=20，明顯的是左輕右重，不是一個均勻的正態分布了，隨著數組的增大，帶來的問題會越來越嚴重。
亞麻帶。。。。我是一朵含苞欲放的花骨朵不要這樣對我。。。
看來前邊的代碼是不能用的，只能重新思考解決方法，其實問題的核心在於保證數組的左右兩側是相等或者大致相等的，不管是奇數個數的數組還是偶數個數的，數組可以分為兩部分（奇數個數的拋去最大值後也可以看做是一個偶數數組，即便有多個相同最大值也無所謂，從小到大排序後去除最後一個即可），還是按照上邊的方法，下標為偶數的時候放到左側，為奇數的時候放到右側，在左右兩邊的數組增長過程中，當數組長度相等的時候，對左右兩側數組之和進行比較，因為是按照從小到大排列的，所以正常情況下，右側會大於左側，然後將右側第一個跟左側最後一個互換一下即可達到平衡的目的，代碼如下：
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) //數組相等並且右側和大於左側的時候進行交換
}
}
}
return temp_left.concat(temp_right)
}
// 數組求和
function sum(arr) {
return eval(arr.join("+"));
}
// 數組比較大小
function compare(arr1,arr2) {
return sum(arr1) >= sum(arr2)
}
// 左邊最後一個跟右邊第一個交換
function wrap(l,r){
var m = r.shift()
r.unshift(l.pop())
l.push(m)
}
console.log(sort(arr)) // 得到 [1, 4, 6, 7, 9, 8, 5, 3, 2]
這樣一來整個正態分布就均勻多了，多做幾組測試看看效果：
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]
看起來還不錯，小站裡還有篇文章 點擊查看，用c++完成的，不過看到文章最後的結果，並不是一個均勻的正態分布，倒是跟我第一個程序差不多，
本人不怎麼會c++，也沒運行多組結果看看，有興趣的同學可以嘗試下作為對比。
本文所有的程序我僅在chrome做過測試，如果其他浏覽器有問題的話，希望留言告知，其實這東西也沒什麼難度，權當一個記錄吧，有需要的時候可以用用。