编辑代码

//程序运行完成时一定要有输出语句，本工具才能正确展示运行结果。 

// 1、选择排序
function selectSort(arr) {
    // 缓存数组长度
    const len = arr.length
    // 定义 minIndex，缓存当前区间最小值的索引，注意是索引
    let minIndex
    // i 是当前排序区间的起点
    for (let i = 0; i < len - 1; i++) {
        // 初始化 minIndex 为当前区间第一个元素
        minIndex = i
        // i、j分别定义当前区间的上下界，i是左边界，j是右边界
        for (let j = i; j < len; j++) {
            // 若 j 处的数据项比当前最小值还要小，则更新最小值索引为 j
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }
        // 如果 minIndex 对应元素不是目前的头部元素，则交换两者
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
        }
    }
    return arr
}

// 2、冒泡排序
function bubbleSort(arr) {
    // 外层循环用于控制从头到尾的比较+交换到底有多少轮
    for (let i = 0; i < arr.length; i++) {
        // 内层循环用于完成每一轮遍历过程中的重复比较+交换
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr
}

// 3、直接插入排序
// function insertSort(arr) {
//     for (let i = 1; i < arr.length; i++) {
//         for (let j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
//             [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
//         }
//     }
//     return arr
// }
function insertSort(arr) {
    // 缓存数组长度
    const len = arr.length
    // temp 用来保存当前需要插入的元素
    let temp
    // i用于标识每次被插入的元素的索引
    for (let i = 1; i < len; i++) {
        // j用于帮助 temp 寻找自己应该有的定位
        let j = i
        temp = arr[i]
        // 判断 j 前面一个元素是否比 temp 大
        while (j > 0 && arr[j - 1] > temp) {
            // 如果是，则将 j 前面的一个元素后移一位，为 temp 让出位置
            arr[j] = arr[j - 1]
            j--
        }
        // 循环让位，最后得到的 j 就是 temp 的正确索引
        arr[j] = temp
    }
    return arr
}

// // 4、归并排序
// function mergeSort(arr) {
//     function merge(left, right) {
//         const temp = []
//         while (left.length && right.length) {
//             if (left[0] < right[0]) {
//                 temp.push(left.shift())
//             } else {
//                 temp.push(right.shift())
//             }
//         }
//         return temp.concat(left, right)
//     }

//     function sort(arr) {
//         if (arr.length === 1) {
//             return arr
//         }
//         const mid = Math.floor(arr.length / 2)
//         return merge(sort(arr.slice(0, mid)), sort(arr.slice(mid)))
//     }
//     return sort(arr)
// }
function mergeSort(arr) {
    function mergeArr(arr1, arr2) {
        // 初始化两个指针，分别指向 arr1 和 arr2
        let i = 0, j = 0
        // 初始化结果数组
        const res = []
        // 缓存arr1的长度
        const len1 = arr1.length
        // 缓存arr2的长度
        const len2 = arr2.length
        // 合并两个子数组
        while (i < len1 && j < len2) {
            if (arr1[i] < arr2[j]) {
                res.push(arr1[i])
                i++
            } else {
                res.push(arr2[j])
                j++
            }
        }
        // 若其中一个子数组首先被合并完全，则直接拼接另一个子数组的剩余部分
        if (i < len1) {
            return res.concat(arr1.slice(i))
        } else {
            return res.concat(arr2.slice(j))
        }
    }
    const len = arr.length
    // 处理边界情况
    if (len <= 1) {
        return arr
    }
    // 计算分割点
    const mid = Math.floor(len / 2)
    // 递归分割左子数组，然后合并为有序数组
    const leftArr = mergeSort(arr.slice(0, mid))
    // 递归分割右子数组，然后合并为有序数组
    const rightArr = mergeSort(arr.slice(mid, len))
    // 合并左右两个有序数组
    arr = mergeArr(leftArr, rightArr)
    // 返回合并后的结果
    return arr
}




// 5、快速排序
function quickSort(arr, left = 0, right = arr.length - 1) {
    // 定义递归边界，若子数组只有一个元素，则没有排序必要
    if (arr.length > 1) {
        // 计算当前数组的基准值
        const nextPivot = partition(arr, left, right)
        // 如果左边子数组的长度不小于1，则递归快排这个子数组
        if (left < nextPivot - 1) {
            quickSort(arr, left, nextPivot - 1)
        }
        // 如果右边子数组的长度不小于1，则递归快排这个子数组
        if (nextPivot < right) {
            quickSort(arr, nextPivot, right)
        }
    }
    return arr
}

// 寻找基准值的过程
function partition(arr, left, right) {
    // 基准值默认值
    // const pivot = arr[left];
    const pivot = arr[Math.floor(left + (right - left) / 2)]
    // const pivot = getPivot(arr, left, right);
    // 当左右指针不越界时，循环执行以下逻辑
    while (left <= right) {
        // 左指针所指元素若不大于基准值，则右移左指针
        while (arr[left] < pivot) {
            left++
        }
        // 右指针所指元素若不小于基准值，则左移右指针
        while (arr[right] > pivot) {
            right--
        }
        // 若i<=j，则意味着基准值左边存在较大元素或右边存在较小元素，交换两个元素确保左右两侧有序
        if (left <= right) {
            [arr[left], arr[right]] = [arr[right], arr[left]];
            left++
            right--
        }
    }
    // 返回左指针索引作为下一个基准值的索引
    return left;
}

// 注意：Partition函数中 key<=a[right] 以及 key>=a[left] 表达式必须包含等于的判断，否则当数组两头的数相等时将会造成死循环  例如 {5,2,6,2,9,10,5}

function getPivot(a, left, right) {//三值取中
    let mid = left + Math.floor((right - left) / 2);
    if (a[mid] > a[right])
        [a[mid], a[right]] = [a[right], a[mid]];//交换
    if (a[left] > a[right])
        [a[left], a[right]] = [a[right], a[left]];//交换
    if (a[mid] > a[left])
        [a[left], a[mid]] = [a[mid], a[left]];//交换
    let pivot = a[left];//现在a[mid]<a[left]<a[right];
    return pivot;
}

// // 5、快速排序（in-place 实现）
// function quickSort2(arr) {
//     function partition(arr, left, right) {
//         let pivot = arr[left]
//         let storeIndex = left

//         for (let i = left + 1; i <= right; i++) {
//             if (arr[i] < pivot) {
//                 storeIndex++
//                 [arr[storeIndex], arr[i]] = [arr[i], arr[storeIndex]]
//             }
//         }

//         [arr[left], arr[storeIndex]] = [arr[storeIndex], arr[left]]

//         return storeIndex
//     }

//     function sort(arr, left, right) {
//         if (left < right) {
//             let storeIndex = partition(arr, left, right)
//             sort(arr, left, storeIndex - 1)
//             sort(arr, storeIndex + 1, right)
//         }
//     }

//     sort(arr, 0, arr.length - 1)

//     return arr
// }

// 6、希尔排序
function shellSort(arr) {
    let len = arr.length
    // 逐步降低步长直至为1为止
    for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        // 内层循环与插入排序的写法基本一致，只是每次移动的步长变为gap
        for (let i = gap; i < arr.length; i++) {
            let j = i;
            let cur = arr[i]
            while (j - gap >= 0 && cur < arr[j - gap]) {
                arr[j] = arr[j - gap]
                j = j - gap
            }
            arr[j] = cur
        }
    }
    return arr
}

// 7、堆排序
function heapSort(arr) {
    // 堆排序，反复向下对比+交换，low表示下界，high表示上界
    function heapify(low, high) {
        // 初始化 i 为当前结点，j 为当前结点的左孩子
        let i = low, j = i * 2 + 1
        // 当 j 不超过上界时，重复向下对比+交换的操作
        while (j <= high) {
            // 如果右孩子比左孩子更大，则用右孩子和根结点比较
            if (j + 1 <= high && arr[j + 1] > arr[j]) {
                j = j + 1
            }

            // 若当前结点比孩子结点小，则交换两者的位置，把较大的结点“拱上去”
            if (arr[i] < arr[j]) {
                // 交换位置
                [arr[i], arr[j]] = [arr[j], arr[i]]
                // i 更新为被交换的孩子结点的索引
                i = j
                // j 更新为孩子结点的左孩子的索引
                j = j * 2 + 1
            } else {
                break
            }
        }
    }
    const len = arr.length
    // 初始化堆排序，从第一个非叶子结点开始
    for (let i = Math.floor((len / 2) - 1); i >= 0; i--) {
        heapify(i, len - 1)
    }
    // 排序，每一次for循环找出一个当前最大值，数组长度减一
    for (let j = len - 1; j >= 0; j--) {
        // 从根结点开始调整，并且最后一个结点已经为当前最大值，不需要再参与比较，
        // 所以第三个参数为j - 1，即比较到最后一个结点前即可
        [arr[0], arr[j]] = [arr[j], arr[0]]
        heapify(0, j - 1)
    }
    return arr
}

// 8、基数排序 
// digit 最大位数
function radixSort(arr, digit) {
    let a = 10
    let b = 1
    const counter = []
    for (let i = 0; i < digit; i += 1, a *= 10, b *= 10) {
        // 向各个桶中添加元素
        for (let j = 0; j < arr.length; j++) {
            const bucket = Math.floor((arr[j] % a / b))
            if (!counter[bucket]) {
                counter[bucket] = []
            }
            counter[bucket].push(arr[j])
        }
        let c = 0
        // 将已经根据相应位数排好的桶的元素导回arr中
        for (let k = 0; k < counter.length; k++) {
            let value
            if (counter[k]) {
                while ((value = counter[k].shift()) !== undefined) {
                    arr[c++] = value
                }
            }
        }
    }
    return arr
}

// let arr = [6, 7, 3, 4, 1, 5, 9, 2, 8];
let arr = [5, 2, 6, 2, 9, 10, 5]
console.log(mergeSort(arr))