数组和算法-数组排序-快速排序

快速排序

• 基本思想：

1. 我们首先在数组中选择一个基准点(一般我们选择数组中间这一项 Math.floor(ary.length/2))
2. 拿基准点和数组中的其他项进行比较，比基准点小的方法左边，比它大的放在右边
3. 以后每一边都重复上述两个操作，直到当前这一边只有一项的时候停止

下面上代码

function quickSort(ary) {
        if (ary.length <= 1) {
            return ary;
        }
        var pointIndex = Math.floor(ary.length / 2);//找到基准点索引
        var pointValue = ary.splice(pointIndex, 1)[0];//找到基准点的值，删除掉，并拿出来。此处是一个数组。因此还要取值[0]
        // 接下来拿基准值和数组进行比较，把小于基准值的放在基准值的左边，大的放在右边
        var left = [];
        var right = [];
        for (var i = 0; i < ary.length; i++) {
            var cur = ary[i];
            cur < pointValue ? left.push(cur) : right.push(cur);
        }
        return quickSort(left).concat([pointValue],quickSort(right)); //此处用到递归
    }
    var ary = [15, 13, 17, 11, 8, 20, 22];
    var res = quickSort(ary);
    console.log(res);

结果是：[8, 11, 13, 15, 17, 20, 22]

最后要说的话:写程序要注意细节，细节决定不了你知识的深度，但是细节能决定你的路有多远！