常见排序算法实现

[ziv-zjc]

常见排序算法实现

/*
快速排序
不稳定排序
原地排序，空间复杂度为O(1)
时间复杂度为nlogn
let arr = [10, 3, 6, 5, 16, 8, 9]
*/

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr
    }
    let midIndex = Math.floor(arr.length / 2)
    let midNum = arr[midIndex]
    arr.splice(midIndex, 1)
    let leftArr = []
    let rightArr = []
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] <= midNum) {
            leftArr.push(arr[i])
        } else {
            rightArr.push(arr[i])
        }
    }
    return quickSort(leftArr).concat(midNum, quickSort(rightArr))

}

/*
冒泡排序
稳定排序
原地排序空间复杂度O(1)
时间复杂度O(n^2)
let arr=[11,2,31,45,6,78,37,33,21];
*/
function bubbleSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            let temp = arr[j]
            if (temp > arr[j + 1]) {
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
    return arr
}


/**
 * 选择排序
 * 原地排序, 空间复杂度O(1)
 * 不稳定排序
 * 时间复杂度 O(n^2)
 * @param {*} arr 
 * let arr=[11,2,31,45,6,78,37,33,21];
 */
function SelectSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            let temp = arr[i]
            if (temp > arr[j]) {
                arr[i] = arr[j]
                arr[j] = temp
            }
        }
    }
    return arr
}

/**
 * 插入排序
 * 原地排序，空间复杂度O(1)
 * 稳定排序
 * 时间复杂度O(n^2)
 * @param {*} arr 
 * let arr=[11,2,31,45,6,78,37,33,21];
 */
function insertSort(arr) {
    let temp = null
    for (let i = 1; i < arr.length; i++) {
        if (arr[i - 1] > arr[i]) {
            temp = arr[i]
            let j = i - 1
            while (temp < arr[j] && j >= 0) {
                arr[j + 1] = arr[j]
                arr[j] = temp
                j--
            }
        }
    }
    return arr
}



//归并排序
/**
 * 非原地排序，空间复杂度为O(n)
 * 稳定排序
 * 时间复杂度为O(nlogn)
 * @param {*} arr 
 * let arr=[11,2,31,45,6,78,37,33,21];
 */
function mergeSort(arr) {
    if (arr.length < 2) {
        return arr
    }
    let midIndex = Math.floor(arr.length / 2)
    let leftArr = arr.slice(0, midIndex)
    let rightArr = arr.slice(midIndex)
    if (leftArr == "undefined" && rightArr == "undefined") {
        return false
    }
    return mergeArr(mergeSort(leftArr), mergeSort(rightArr))

}

function mergeArr(leftArr, rightArr) {
    let temp = []
    while (leftArr.length && rightArr.length) {
        if (leftArr[0] > rightArr[0]) {
            temp.push(rightArr.shift())
        } else {
            temp.push(leftArr.shift())
        }
    }
    while (leftArr.length) {
        temp.push(leftArr.shift())
    }
    while (rightArr.length) {
        temp.push(rightArr.shift())
    }
    return temp
}