/**
? ? * 快速排序
? ? * 時間復雜度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));
? ? }
