高效排序算法：如何在实际项目中选择合适的方法？

创作时间:

作者:

@小白创作中心

高效排序算法：如何在实际项目中选择合适的方法？

引用

CSDN

https://blog.csdn.net/weixin_42554191/article/details/143228155

高效排序算法是用于处理大量数据的排序方法，它们通常具有更优的时间复杂度和空间复杂度。下面将详细介绍四种高效排序算法：归并排序、快速排序、堆排序和基数排序。

1. 归并排序（Merge Sort）

归并排序是一种分治算法，它将数组分成两个子数组，递归地排序这两个子数组，然后将它们合并成一个有序的数组。

特点

时间复杂度：最坏、平均和最佳情况均为 $O(n \log n)$。
空间复杂度：$O(n)$（需要额外的数组空间）。
稳定性：稳定。

实现示例

function mergeSort(arr) {
    if (arr.length <= 1) return arr; // 基础情况
    const mid = Math.floor(arr.length / 2); // 找到中间索引
    const left = mergeSort(arr.slice(0, mid)); // 递归排序左半部分
    const right = mergeSort(arr.slice(mid)); // 递归排序右半部分
    return merge(left, right); // 合并两个有序数组
}
function merge(left, right) {
    const result = [];
    let i = 0, j = 0;
    // 合并两个有序数组
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }
    // 将剩余元素添加到结果中
    return result.concat(left.slice(i)).concat(right.slice(j));
}
// 示例
const array1 = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(array1)); // [3, 9, 10, 27, 38, 43, 82]

2. 快速排序（Quick Sort）

快速排序是一种分治排序算法，它选择一个"基准"元素，然后将数组分成比基准小的部分和比基准大的部分，递归地对这两个部分进行排序。

特点

时间复杂度：最坏情况是 $O(n^2)$，平均和最佳情况是 $O(n \log n)$。
空间复杂度：$O(\log n)$（递归栈空间）。
稳定性：不稳定。

实现示例

function quickSort(arr) {
    if (arr.length <= 1) return arr; // 基础情况
    const pivot = arr[Math.floor(arr.length / 2)]; // 选择基准元素
    const left = arr.filter(x => x < pivot); // 小于基准
    const middle = arr.filter(x => x === pivot); // 等于基准
    const right = arr.filter(x => x > pivot); // 大于基准
    return [...quickSort(left), ...middle, ...quickSort(right)]; // 递归排序并合并
}
// 示例
const array2 = [10, 7, 8, 9, 1, 5];
console.log(quickSort(array2)); // [1, 5, 7, 8, 9, 10]

3. 堆排序（Heap Sort）

堆排序是一种基于比较的排序算法，它利用堆数据结构的性质，将待排序的元素构建成一个最大堆（或最小堆），然后反复提取堆顶元素进行排序。

特点

时间复杂度：最坏、平均和最佳情况均为 $O(n \log n)$。
空间复杂度：$O(1)$（就地排序）。
稳定性：不稳定。

实现示例

function heapSort(arr) {
    const n = arr.length;
    // 建立最大堆
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    // 一个个取出最大元素
    for (let i = n - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]]; // 交换
        heapify(arr, i, 0); // 重建堆
    }
    return arr;
}
function heapify(arr, n, i) {
    let largest = i; // 初始化最大元素为根节点
    const left = 2 * i + 1; // 左子节点
    const right = 2 * i + 2; // 右子节点
    // 如果左子节点比根节点大
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    // 如果右子节点比最大值大
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    // 如果最大值不是根节点
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]]; // 交换
        heapify(arr, n, largest); // 递归
    }
}
// 示例
const array3 = [3, 0, 2, 5, -1, 4, 1];
console.log(heapSort(array3)); // [-1, 0, 1, 2, 3, 4, 5]

4. 基数排序（Radix Sort）

基数排序是一种非比较的排序算法，它通过将数字分解为数字位进行排序。基数排序可以使用稳定的排序算法（如计数排序）进行子排序。

特点

时间复杂度：$O(nk)$，其中 $n$ 是元素数量，$k$ 是数字的位数。
空间复杂度：$O(n + k)$（可能需要额外的空间）。
稳定性：稳定。

实现示例

function countingSortForRadix(arr, exp) {
    const output = new Array(arr.length);
    const count = new Array(10).fill(0);
    // 统计每位数字的出现次数
    for (let i = 0; i < arr.length; i++) {
        count[Math.floor(arr[i] / exp) % 10]++;
    }
    // 改变count[i]使其包含当前位置
    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    // 构建输出数组
    for (let i = arr.length - 1; i >= 0; i--) {
        output[count[Math.floor(arr[i] / exp) % 10] - 1] = arr[i];
        count[Math.floor(arr[i] / exp) % 10]--;
    }
    // 复制输出数组到原数组
    for (let i = 0; i < arr.length; i++) {
        arr[i] = output[i];
    }
}
function radixSort(arr) {
    const max = Math.max(...arr);
    // 对每一位进行排序
    for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
        countingSortForRadix(arr, exp);
    }
    return arr;
}
// 示例
const array4 = [170, 45, 75, 90, 802, 24, 2, 66];
console.log(radixSort(array4)); // [2, 24, 45, 66, 75, 90, 170, 802]