js实现快速排序

/**

    * 快速排序

    * 时间复杂度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));

    }