/**
* 快速排序
* 时间复杂度O(n2) 平均O(nlongn)
*
* @param {any} arr
* @returns
*
* @memberof sort
*/
sort3(arr) {
if(arr.length <= 1)
return arr;
let middle = Math.floor(arr.length / 2);
let midVal = arr.splice(middle, 1)[0];
let left = [];
let right = [];
for(let i = 0;i < arr.length;i++) {
if(arr[i] < midVal) {
left.push(arr[i])
} else {
right.push(arr[i]);
}
}
return this.sort3(left).concat([midVal], this.sort3(right));
}
