js数组快排的实现原理

一.我们平时在使用数组的排序的时候，都是调用的js自带的sort()方法；
var arr = [5,1,8,1,2,9,3,4];
console.log(arr.sort()); //[1,1,2,3,4,5,8,9]
二.其实我们自己可以根据一些简单的方法自己实现，主要实现思路如下：
1.在数据集之中找一个基准点（位于目前的数组的中间的那个数值），
2.建立2个数组，分别存储左边和右边的数组，
3.利用递归进行逐次比较，然后拼接数组达到排序的效果。
function quickSort(arr) {
if (arr.length<=1) {
return arr;
}
var num = Math.floor(arr.length / 2),//找到中间值,如果是浮点数,就向下取整
numValue = arr.splice(num, 1)[0]; //找到中间数的值

        var leftArr = [],
            rightArr = [];
        for (var i = 0; i < arr.length; i++) {
            if (arr[i] < numValue) {
                leftArr.push(arr[i]);
            } else{
                rightArr.push(arr[i]);
            }
        }
        //遍历后的2数组,再调用此方法递归遍历
        return quickSort(leftArr).concat([numValue],quickSort(rightArr));
    }
    //调用测试结果
    var new_arr = quickSort(arr);  //[1,1,2,3,4,5,8,9]