JavaScript排序算法系列——快速排序「建议收藏」

9,     7,     1,     4,     6,      2
[1, 2]     [4]     [9, 7, 6]
[1] [2] [] [4]   [] [6] [9, 7]
[1] [2] [] [4]   [] [6] [7] [9] []

function quickSort(arr){ 
   
    // 设置递归的终点
    if(arr.length <= 1){
        return arr;
    }
    // 1. 在数组中任选一个数
    var midNum = arr[Math.floor(arr.length / 2)];//向下取整

    // 2. 将数组分成三组
    var left = [];
    var middle = [];
    var right = [];

    // 3. 判断
    for(var i = 0; i < arr.length; i++){
        if(arr[i] < midNum){
            left.push(arr[i]);
        } else if(arr[i] == midNum){
            middle.push(arr[i]);
        } else if(arr[i] > midNum){
            right.push(arr[i]);
        }
    }

    // 4. 将三个分组分别用同样的方法排序并连接在一起
    return quickSort(left).concat(middle, quickSort(right));
}

var arr = [1,5,7,3,12];
console.log(quickSort(arr));