题解 | #排序#

简洁版本快排

/**
 * 快排
 */
function MySort( arr ) {
    // write code here
    quickSort(arr, 0, arr.length - 1)
    return arr
}
function quickSort(arr, l, r) {
    if (l >= r) return
    const pivot = arr[l]
    let i = l + 1
    let x = l
    let y = r
    while(i <= y) {
        if(arr[i] <= pivot) swap(arr, i++, x++)
        else swap(arr, i, y--)
    }
    quickSort(arr, l, x - 1)
    quickSort(arr, x + 1, r)
}
function swap(arr, i, j) {
    const temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}
module.exports = {
    MySort : MySort
};

归并排序

/**
 归并排序
 */
function MySort( arr ) {
    // write code here
    return mergeSort(arr, 0, arr.length - 1)
}
function mergeSort(arr, l, r) {
    if (l === r) return [arr[l]]
    const mid = l + ((r - l) >> 1)
    const left = mergeSort(arr, l, mid)
    const right = mergeSort(arr, mid + 1, r)
    return merge(left, right)
}
function merge(arr1, arr2) {
    const len1 = arr1.length
    const len2 = arr2.length
    const res = []
    let i = 0
    let j = 0
    while(i < len1 && j < len2) {
        if (arr1[i] <= arr2[j]) res.push(arr1[i++])
        else res.push(arr2[j++])
    }
    while(i < len1) res.push(arr1[i++])
    while(j < len2) res.push(arr2[j++])
    return res
}
module.exports = {
    MySort : MySort
};