js 快速排序

问题:一个值未知的数组,如何快速根据值的大小进行排序。
思路:
先找到数组的中位数pivot作为参照物
遍历数组中的每一项与其比较,然后小的放到一个Left的空数组里面,比它大的放点right的空数组里面
再递归左边的数组和右边的组数,最后把2个数组和中位数连接到一个数组里面去

let arr = [11, 82, 4, 44, 20]
var quickSort = function (arr) {
    if (arr.length <= 1) { return arr }
    var pivotIndex = Math.floor(arr.length / 2)
    var pivot = arr.splice(pivotIndex, 1)[0]
    var left = []
    var right = []
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }
    return quickSort(left).concat([pivot], quickSort(right))
}
console.info(quickSort(arr))
本站文章如未注明均为原创 | 文章作者:刘晓帆 | 转载请注明来自:前端印象

发表评论

邮箱地址不会被公开。 必填项已用*标注

浏览量:87 次浏览