算法排序篇——快速排序

发表于 | 分类于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function quickSort(arr) {
    if(arr.length == 0){
        return []; // 控制递归的终止
    }
    let lesser = [],
        greater = [],
        pivot = arr[0]; // 一般将第一个或最后一个作为基准数
    for (let i = 1; i <= arr.length - 1; i++) {
        // 因为基准数是第一个数，循环从第二个数开始
        if (arr[i] < pivot) {
            lesser.push(arr[i]);
        } else {
            greater.push(arr[i]);
        }
    }
    // 对子序列进行以上操作，通过递归实现
    return quickSort(lesser).concat(pivot, quickSort(greater));
}

// 测试代码
let arr = [];
for (let i = 0; i < 10; ++i) {
    arr[i] = Math.floor((Math.random() * 100) + 1);
}
console.log(arr);
console.log(quickSort(arr));