前端面试专栏-算法篇：17. 排序算法

🔥 欢迎来到前端面试通关指南专栏！从js精讲到框架到实战，渐进系统化学习，坚持解锁新技能，祝你轻松拿下心仪offer。
前端面试通关指南专栏主页
前端面试专栏规划详情

面试必备：排序算法（冒泡、快速、归并等）深度解析

在程序员面试中，算法相关问题占据着举足轻重的地位，而排序算法作为算法领域的基础且核心内容，更是面试官考察的重点。无论是互联网大厂还是初创公司，都期望应聘者对常见排序算法有深入理解并能灵活运用。本文将详细剖析冒泡排序、快速排序、归并排序等经典排序算法，助力读者在面试中脱颖而出。

一、冒泡排序（Bubble Sort）

1.1 算法原理

冒泡排序是一种基于比较的简单排序算法，其名称来源于排序过程中较小的元素会像"气泡"一样逐步"浮"到数列顶端（升序排列时）。该算法主要通过以下步骤实现排序：

1. 遍历比较：从数列的第一个元素开始，依次比较相邻的两个元素。例如，比较第1个和第2个元素，然后是第2个和第3个元素，以此类推直到最后两个元素。

2. 交换操作：如果相邻元素的顺序不符合要求（比如前一个元素大于后一个元素时进行升序排序），就交换它们的位置。

3. 重复过程：完成一轮遍历后，最大的元素会"冒泡"到数列末尾。然后对剩下的n-1个元素重复上述过程。

4. 终止条件：当某一轮遍历中没有发生任何元素交换时，说明数列已经有序，排序过程即可终止。

时间复杂度分析：

• 最优情况（已排序数列）：O(n)，只需进行一轮比较
• 平均和最坏情况：O(n²)，需要进行n(n-1)/2次比较

空间复杂度：O(1)，属于原地排序算法，仅需常数级别的额外空间用于交换操作。

应用场景：

• 适用于小规模数据排序
• 常用于教学目的，帮助理解基本排序原理
• 在数据基本有序的情况下效率较高

示例说明：
假设要对数组[5, 3, 8, 6, 2]进行升序排序：
第一轮遍历后变为[3,5,6,2,8]（8已到位）
第二轮变为[3,5,2,6,8]（6已到位）
第三轮变为[3,2,5,6,8]（5已到位）
第四轮变为[2,3,5,6,8]（完成排序）

1.2 算法实现（以 JavaScript 为例）

冒泡排序是一种简单的排序算法，通过重复地遍历要排序的列表，比较相邻元素并交换它们的位置来实现排序。其核心思想是将较大的元素逐步"冒泡"到数组的末端。以下是完整的 JavaScript 实现及详细说明：

/**
 * 冒泡排序算法实现
 * @param {Array} arr - 待排序的数组
 * @returns {Array} - 排序后的数组
 */
function bubbleSort(arr) {
    const len = arr.length;
    // 外层循环控制排序轮数，每轮会将当前最大元素"冒泡"到数组末尾
    // 由于最后一个元素无需比较，故循环次数为 len-1
    for (let i = 0; i < len - 1; i++) {
        let swapped = false; // 优化标志位，记录本轮是否发生元素交换
        
        // 内层循环进行相邻元素比较
        // 随着i增加，已排序区域扩大，比较范围相应缩小(len-1-i)
        for (let j = 0; j < len - 1 - i; j++) {
            // 比较相邻元素，前大后小则交换位置
            if (arr[j] > arr[j + 1]) {
                // 使用解构赋值实现元素交换（ES6特性）
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true; // 标记本轮发生交换
            }
        }
        
        // 性能优化：若本轮未发生交换，说明数组已完全有序
        // 提前终止排序过程，避免不必要的比较
        if (!swapped) break;
    }
    return arr;
}

// 示例用法
const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
console.log("排序前:", unsortedArray);
console.log("排序后:", bubbleSort(unsortedArray));

算法特点说明：

1. 时间复杂度：

   • 最坏情况（逆序数组）为O(n²)
   • 最好情况（已排序数组）为O(n)（得益于swapped优化）

2. 空间复杂度：O(1)，属于原地排序算法

3. 稳定性：是稳定排序算法，相等元素不会改变相对位置

4. 适用场景：

   • 小规模数据排序
   • 对算法稳定性有要求的场景
   • 作为排序算法的教学示例

实际应用时，当处理大规模数据时建议使用更高效的排序算法（如快速排序或归并排序），但对于小型数据集或近乎有序的数据，冒泡排序的简单实现和优化特性仍有一定价值。

1.3 时间复杂度与空间复杂度

时间复杂度分析

冒泡排序的时间复杂度分析需要考虑三种情况：

1. 最坏情况：

   • 当数组完全逆序时，需要进行最大数量的比较和交换
   • 具体过程：
     • 第一轮比较：n-1次比较
     • 第二轮比较：n-2次比较
     • …
     • 最后一轮比较：1次比较
   • 总比较次数 = (n-1)+(n-2)+…+1 = n(n-1)/2 ≈ n²/2
   • 因此最坏时间复杂度为O(n²)

2. 平均情况：

   • 对于随机排列的数组，仍需进行约n²/2次比较
   • 交换次数取决于数组的初始有序程度
   • 平均时间复杂度同样为O(n²)

3. 最好情况：

   • 当数组已经有序时，只需进行n-1次比较
   • 不需要进行任何元素交换
   • 可以通过设置标志位优化（如发现某轮没有交换可直接结束）
   • 最好时间复杂度为O(n)

示例：对长度为5的数组[5,4,3,2,1]排序：

• 需要4轮比较（n-1轮）
• 总比较次数：4+3+2+1=10次（满足n(n-1)/2=10）

空间复杂度分析

冒泡排序的空间效率很高：

• 只需要常数级别的额外空间：
  • 用于交换的临时变量（通常1个）
  • 可能需要的循环计数器等
• 所有操作都在原数组上进行（原地排序）
• 不随输入规模n增大而增加
• 因此空间复杂度为O(1)

对比：与归并排序（需要O(n)额外空间）等算法相比，冒泡排序在空间效率上具有优势，适合内存受限的环境。

实际应用中的考量

虽然时间复杂度较高，但在以下场景仍有应用价值：

1. 小规模数据排序（n<100）
2. 数据基本有序的情况
3. 内存资源非常有限的嵌入式系统
4. 作为教学示例演示基本排序原理

可以通过以下优化提升实际性能：

• 添加交换标志位（提前终止）
• 记录最后交换位置（减少比较范围）
• 双向冒泡（鸡尾酒排序）等变种算法

1.4 稳定性

冒泡排序是一种稳定的排序算法，这是由其算法特性决定的。所谓稳定性，是指在排序过程中能够保持相等元素的原始相对顺序不变。在冒泡排序的实现中，当相邻两个元素进行比较时，只有在前一个元素大于后一个元素时才会进行交换；如果两个元素相等，则不会进行交换操作。

具体来说，冒泡排序的稳定性表现在以下几个方面：

1. 比较规则：算法仅在前一个元素严格大于后一个元素时才执行交换
2. 相等处理：对于相等的元素对（如a[i] == a[j]），会保持它们的原始相对位置
3. 顺序保持：经过多轮比较和交换后，相等元素的输入顺序会被完整保留

为了更清楚地说明这一点，我们可以看一个具体例子：
初始数组：[2（红色）, 2’（蓝色）, 1]
其中2和2’是值相同但可区分的元素
排序过程：

1. 第一轮比较：比较2和2’，相等不交换 → [2, 2’, 1]
2. 比较2’和1，交换 → [2, 1, 2’]
3. 第二轮比较：比较2和1，交换 → [1, 2, 2’]
4. 比较2和2’，相等不交换
   最终结果：[1, 2, 2’]，保持了原始数组中2和2’的相对顺序

这个特性在实际应用中非常重要，例如：

• 在处理包含多个排序键的数据时（如先按姓名排序，再按年龄排序）
• 在需要保持原始数据某些特性的场景下（如日志的时间顺序）

相比之下，某些其他排序算法（如快速排序的简单实现）就不具备这种稳定性，这也是在某些特定场景下选择冒泡排序的一个重要考量因素。

二、快速排序（Quick Sort）

2.1 算法原理

快速排序（Quick Sort）是一种高效的排序算法，由英国计算机科学家托尼·霍尔（Tony Hoare）于1960年提出。其核心思想是"分治法"（Divide and Conquer），通过递归地将问题分解为更小的子问题来解决排序问题。

具体实现过程可分为以下步骤：

1. 基准元素（pivot）选择：

   • 通常选择数组的第一个、最后一个或中间元素作为基准
   • 更优化的方法包括"三数取中法"，即选择首、中、尾三个元素的中值作为基准

2. 分区（Partition）操作：

   • 将数组重新排列，使得所有小于基准的元素都位于基准之前
   • 所有大于基准的元素都位于基准之后
   • 基准元素最终位于其正确的位置（即最终排序数组中的位置）

3. 递归处理：

   • 对基准左侧的子数组进行快速排序
   • 对基准右侧的子数组进行快速排序
   • 递归的终止条件是子数组的长度小于等于1

示例说明：
假设要对数组 [3,6,8,10,1,2,1] 进行排序：

1. 选择最后一个元素1作为基准
2. 分区后得到：[1,1] (小于基准) | [2,3,6,8,10] (大于基准)
3. 对左右子数组递归执行相同操作

算法特点：

• 平均时间复杂度：O(nlogn)
• 最坏情况（如已排序数组）时间复杂度：O(n²)
• 空间复杂度：O(logn)（递归栈空间）
• 不稳定排序算法（相同元素的相对位置可能改变）

优化策略：

1. 小数组切换策略：当子数组规模较小时（如长度<10），改用插入排序
2. 三向切分的快速排序：针对包含大量重复元素的数组优化
3. 随机化快速排序：随机选择基准元素以避免最坏情况

应用场景：

• 适用于大规模数据排序
• 内存受限环境（相比归并排序需要更少的额外空间）
• 实际应用中常作为默认排序算法（如C++的qsort，Java的Arrays.sort）

2.2 算法实现（多语言示例）

JavaScript 实现（原地排序版）

function quickSort(arr, left = 0, right = arr.length - 1) {
    if (left >= right) return;
    
    // 选择基准元素（此处取中间元素）
    const pivotIndex = Math.floor((left + right) / 2);
    const pivot = arr[pivotIndex];
    
    // 分区操作：将小于基准的放左边，大于基准的放右边
    const partitionIndex = partition(arr, left, right, pivot);
    
    // 递归排序左右分区
    quickSort(arr, left, partitionIndex - 1);
    quickSort(arr, partitionIndex, right);
    
    return arr;
}

function partition(arr, left, right, pivot) {
    while (left <= right) {
        // 找到左边大于基准的元素
        while (arr[left] < pivot) left++;
        // 找到右边小于基准的元素
        while (arr[right] > pivot) right--;
        
        // 交换元素并移动指针
        if (left <= right) {
            [arr[left], arr[right]] = [arr[right], arr[left]];
            left++;
            right--;
        }
    }
    return left;
}

Python 实现（简洁版）

def quickSort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quickSort(left) + middle + quickSort(right)

Java 实现（经典双指针版）

public class QuickSort {
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length == 0) return;
        sort(arr, 0, arr.length - 1);
    }
    
    private static void sort(int[] arr, int left, int right) {
        if (left >= right) return;
        
        int pivot = arr[left + (right - left) / 2];
        int i = left;
        int j = right;
        
        while (i <= j) {
            while (arr[i] < pivot) i++;
            while (arr[j] > pivot) j--;
            
            if (i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }
        
        sort(arr, left, j);
        sort(arr, i, right);
    }
}

2.3 时间复杂度与空间复杂度

时间复杂度分析

1. 平均情况：

   • 快速排序采用分治策略，每次递归调用都能将数组相对均匀地划分为两部分。假设每次划分都能将数组分成两个大小相近的子数组（例如7:3或6:4的比例），那么递归树的高度约为$logn$。
   • 在每层递归中，需要$O(n)$时间进行元素划分（通过遍历数组完成基准元素的定位和交换）。因此，总时间复杂度计算公式为：递归深度$\times$每层处理时间 = $logn\times O(n)=O(nlogn)$。
   • 示例：对一个包含1024个元素的数组，理想情况下递归深度为$lo{g}_{2}1024=10$，每层处理约1024次比较，总操作次数约10×1024=10240次。

2. 最坏情况：

   • 当输入数组已经有序（升序或降序）时，若始终选择第一个或最后一个元素作为基准，会导致每次划分后一个子数组为空，另一个子数组包含$n-1$个元素。此时递归树退化为链状结构，深度达到$n$。
   • 每层仍需$O(n)$时间划分，总时间复杂度为$n\times O(n)=O(n^2)$。例如排序1000个已有序元素，需要约1000+999+…+1≈500500次操作。
   • 优化方法：通过随机选择基准元素或使用"三数取中法"（选择首、尾、中间元素的中位数），可有效降低最坏情况发生概率。

空间复杂度分析

1. 递归栈消耗：

   • 快速排序的空间消耗主要来自递归调用栈。在平均情况下，递归深度为$logn$，每次递归调用需要固定空间存储参数（如数组边界），因此空间复杂度为$O(logn)$。
   • 示例：排序1024个元素时，递归栈最多同时保存约10层调用信息。

2. 最坏情况空间消耗：

   • 当划分极度不均衡时（如最坏时间复杂度场景），递归深度达到$n$，空间复杂度升至$O(n)$。例如排序已有序的1000个元素，递归栈需要保存1000层调用帧。
   • 优化策略：采用尾递归优化或迭代实现（用显式栈替代递归），可将最坏空间复杂度降至$O(logn)$。

3. 辅助空间：

   • 原地分区（in-place partition）版本的快速排序仅需$O(1)$额外空间存储临时变量（如基准元素索引）。若实现为非原地版本（如每次划分创建新数组），则需额外$O(n)$空间。

实际应用权衡

• 在大多数标准库实现中（如C++的std::sort），快速排序常与其他算法结合使用。例如当递归深度超过阈值时切换为堆排序，以避免$O(n^2)$时间复杂度的风险，同时保持$O(logn)$的空间效率。
• 对于内存受限环境（如嵌入式系统），需特别注意最坏情况的空间消耗，可能优先选择堆排序等空间复杂度恒定为$O(1)$的算法。

2.4 稳定性

快速排序是一种典型的不稳定排序算法。不稳定排序是指当存在相同元素时，这些元素在排序前后的相对位置可能会发生改变。快速排序的不稳定性主要来源于其分区（partition）操作的方式。

具体来说，在快速排序的分区过程中，基准元素（pivot）的选择和交换操作可能导致相同元素的相对顺序被打乱。让我们通过一个更详细的例子来说明这一点：

假设有一个数组[2, 2', 1]，其中2和2'是两个值相同但可能带有不同属性的元素（比如2'可能代表第二个出现的2）。如果我们选择第一个元素2作为基准（pivot），那么分区过程可能如下进行：

1. 初始数组：[2, 2', 1]
2. 选择2作为基准，设置左指针在2（基准自身），右指针在1
3. 从右向左扫描，找到第一个小于基准的元素1，交换2和1：
   • 交换后数组：[1, 2', 2]
4. 此时分区完成，基准2被放置到了数组末尾

最终排序结果为[1, 2', 2]。可以看到，原本2出现在2'之前，但排序后2'却排在了2的前面，它们的相对顺序发生了改变。这就是快速排序不稳定的典型表现。

造成这种情况的根本原因是：在分区过程中，算法无法保证在交换元素时能维持相同元素的原始顺序。当基准元素与另一个相同元素相遇时，它们可能会因为交换操作而改变相对位置。

在实际应用中，这种不稳定性可能会带来问题。例如：

• 在需要保持多重排序（如先按年龄排序，再按姓名排序）的场景中
• 当元素除了比较键值外还包含其他需要保持顺序的附加信息时

相比之下，像归并排序这样的稳定排序算法就能保持相同元素的原始相对顺序。因此，在选择排序算法时，如果需要保持稳定性，就需要考虑使用其他稳定的排序算法。

2.5 应用场景

快速排序凭借其平均$O(nlogn)$的时间复杂度和较好的实际运行效率，在诸多场景中被广泛应用。

• 大数据量排序场景：当需要处理大规模数据（如十万级、百万级数据）时，快速排序的高效性使其成为优选。例如在数据库查询结果排序、日志分析中对海量日志数据按时间或关键字排序等场景，能快速完成排序操作，提升处理效率。
• 内存中的排序需求：由于快速排序是原地排序（除递归栈外无需额外大空间），在内存资源有限，需要对数据在内存中直接排序时非常适用。比如在一些嵌入式系统或内存受限的应用中，对本地存储的数据集进行排序。
• 通用库实现：许多编程语言的标准库中，排序函数的实现都采用了快速排序或其变种（如C++的std::sort在部分情况下使用快速排序思想）。这是因为它在大多数实际数据场景下表现优异，能满足通用排序需求。
• 面试与算法竞赛：在面试中的算法题或算法竞赛里，当题目对排序效率有要求，且数据分布较为随机时，快速排序是常用的解题工具。例如在处理需要先排序再进行后续操作（如二分查找、求中位数等）的问题时，快速排序能快速为后续步骤提供有序数据。

三、归并排序（Merge Sort）

3.1 算法原理

归并排序是一种典型的分治算法（Divide and Conquer），其核心思想是将一个大问题分解为若干小问题，分别解决后再将结果合并。具体实现步骤如下：

1. 分解阶段：

   • 将待排序的数组递归地分成两个长度相等（或最多相差1）的子数组
   • 持续分解直到每个子数组只包含单个元素（此时自然有序）

2. 排序与合并阶段：

   • 对两个已排序的子数组进行合并操作
   • 使用双指针技术：初始化两个指针分别指向两个子数组的首元素
   • 比较指针所指元素，将较小的元素放入结果数组
   • 移动取用元素的指针，继续比较直到某个子数组被完全遍历
   • 将剩余子数组的元素直接追加到结果数组末尾

示例：
假设合并[3,7]和[2,5]两个有序子数组：

1. 比较3和2，取2 → 结果[2]
2. 比较3和5，取3 → 结果[2,3]
3. 比较7和5，取5 → 结果[2,3,5]
4. 剩余7直接追加 → 最终[2,3,5,7]

时间复杂度分析：

• 分解过程形成递归树，深度为log₂n
• 每层合并操作需O(n)时间
• 总时间复杂度为O(nlogn)，是稳定的高效排序算法

空间复杂度：

• 需要额外O(n)空间存储临时数组
• 属于"非原地排序"算法

应用场景：

• 适合链表排序（不需要随机访问）
• 外部排序（大数据量无法全部载入内存时）
• 需要稳定排序的场合（相同元素保持原始顺序）

3.2 算法实现（JavaScript 版）

归并排序是一种典型的分治算法实现，其核心思想是将数组递归地分成两半进行排序，然后将两个有序的子数组合并成一个有序数组。下面是用JavaScript实现的完整代码及详细说明：

/**
 * 归并排序主函数
 * @param {Array} arr - 待排序数组
 * @returns {Array} 排好序的新数组（不改变原数组）
 */
function mergeSort(arr) {
    // 递归终止条件：当数组长度小于等于1时，已经是有序的状态
    // 使用slice()创建新数组，避免修改原数组
    if (arr.length <= 1) return arr.slice();
    
    // 计算中间位置，将数组分成左右两部分
    // 使用Math.floor向下取整，确保mid是整数索引
    const mid = Math.floor(arr.length / 2);
    
    // 递归地对左半部分进行排序
    const left = mergeSort(arr.slice(0, mid));
    // 递归地对右半部分进行排序
    const right = mergeSort(arr.slice(mid));
    
    // 合并两个已排序的子数组
    return merge(left, right);
}

/**
 * 合并两个有序数组
 * @param {Array} left - 第一个有序数组
 * @param {Array} right - 第二个有序数组
 * @returns {Array} 合并后的有序数组
 */
function merge(left, right) {
    const result = [];
    let i = 0; // left数组的指针
    let j = 0; // right数组的指针
    
    // 比较两个数组当前指针位置的元素
    // 将较小的元素推入结果数组，并移动相应指针
    while (i < left.length && j < right.length) {
        // 这里的<=保证了排序的稳定性（相等时不改变相对顺序）
        if (left[i] <= right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }
    
    // 处理剩余元素（当其中一个数组已全部合并时）
    // 将left数组剩余元素加入结果
    while (i < left.length) result.push(left[i++]);
    // 将right数组剩余元素加入结果
    while (j < right.length) result.push(right[j++]);
    
    return result;
}

应用示例：

const unsortedArray = [8, 3, 5, 1, 9, 6, 2, 7, 4];
const sortedArray = mergeSort(unsortedArray);
console.log(sortedArray); // 输出：[1, 2, 3, 4, 5, 6, 7, 8, 9]

算法特点：

1. 时间复杂度：O(nlogn)，在最好、最坏和平均情况下都是这个复杂度
2. 空间复杂度：O(n)，需要额外的空间来存储临时数组
3. 稳定性：稳定排序（当遇到相等元素时保持原有顺序）
4. 适合场景：适合链表排序、大数据量排序等场景
5. 不适合场景：对内存要求较高的场景，因为需要额外的存储空间

3.3 时间复杂度与空间复杂度

• 时间复杂度：归并排序每次将数组分成两部分，递归深度为$logn$，每层递归中合并操作需要$O(n)$的时间，因此无论在最好、最坏还是平均情况下，时间复杂度均为$O(nlogn)$。

• 空间复杂度：归并排序在合并过程中需要一个额外的临时数组来存储合并结果，其大小与原数组相同，因此空间复杂度为$O(n)$。

3.4 稳定性

归并排序是稳定的排序算法。在合并操作中，当两个子数组中有相等元素时，会优先将左边子数组的元素放入结果数组，从而保持相等元素的相对顺序。例如，对于数组[2, 2’, 1]，合并时如果左边子数组是[2, 2’]，右边子数组是[1]，最终结果会是[1, 2, 2’]，2和2’的相对顺序不变。

四、其他常见排序算法（JavaScript 实现）

4.1 插入排序（Insertion Sort）

• 算法原理：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。类似于扑克牌整理，每次从手中未整理的牌中抽取一张，插入到已整理好的牌中的合适位置。

• JavaScript 实现：

function insertionSort(arr) {
    const len = arr.length;
    // 从第二个元素开始，作为待插入元素
    for (let i = 1; i < len; i++) {
        const current = arr[i];
        let j = i - 1;
        
        // 在已排序序列中找到插入位置
        while (j >= 0 && arr[j] > current) {
            arr[j + 1] = arr[j]; // 元素后移
            j--;
        }
        arr[j + 1] = current; // 插入待插入元素
    }
    return arr;
}

• 时间复杂度：最坏和平均情况下为$O(n^2)$，最好情况（数组已有序）下为$O(n)$。

• 空间复杂度：$O(1)$，是一种原地排序算法。

• 稳定性：稳定，相等元素不会交换位置。

4.2 选择排序（Selection Sort）

• 算法原理：首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后从剩余未排序元素中继续寻找最小（或最大）元素，放到已排序序列的末尾，以此类推。

• JavaScript 实现：

function selectionSort(arr) {
    const len = arr.length;
    for (let i = 0; i < len - 1; i++) {
        let minIndex = i; // 记录最小元素索引
        
        // 寻找未排序部分的最小元素
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // 将最小元素与未排序部分的第一个元素交换
        if (minIndex!== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }
    return arr;
}

• 时间复杂度：无论数组初始状态如何，都需要进行$n(n-1)/2$次比较，时间复杂度为$O(n^2)$。

• 空间复杂度：$O(1)$。

• 稳定性：不稳定，例如数组[2, 2’, 1]，选择最小元素1与第一个2交换后，2和2’的相对顺序改变。

4.3 堆排序（Heap Sort）

• 算法原理：利用堆这种数据结构进行排序。先将数组构建成一个大顶堆（或小顶堆），然后将堆顶元素与堆尾元素交换，再对剩余元素重新调整为堆，重复此过程直到数组有序。

• JavaScript 实现：

function heapSort(arr) {
    const len = arr.length;
    
    // 构建大顶堆
    for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
        heapify(arr, len, i);
    }
    
    // 排序过程
    for (let i = len - 1; i > 0; i--) {
        // 交换堆顶与当前末尾元素
        [arr[0], arr[i]] = [arr[i], arr[0]];
        // 对剩余元素重新构建大顶堆
        heapify(arr, i, 0);
    }
    
    return arr;
}

// 堆调整函数：将以index为根的子树调整为大顶堆
function heapify(arr, size, index) {
    let largest = index;
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    
    // 比较左子节点与根节点
    if (left < size && arr[left] > arr[largest]) {
        largest = left;
    }
    
    // 比较右子节点与根节点
    if (right < size && arr[right] > arr[largest]) {
        largest = right;
    }
    
    // 若最大值不是根节点，则交换并继续调整
    if (largest!== index) {
        [arr[index], arr[largest]] = [arr[largest], arr[index]];
        heapify(arr, size, largest);
    }
}

• 时间复杂度：$O(nlogn)$。

• 空间复杂度：$O(1)$。

• 稳定性：不稳定。

五、排序算法总结与面试应对策略

不同排序算法在时间复杂度、空间复杂度和稳定性等方面各有特点。在面试中，应根据具体问题场景选择合适的排序算法。例如，当数据规模较小且要求稳定性时，插入排序可能是不错的选择；对于大规模数据，快速排序（平均性能好）或归并排序（稳定且性能稳定）更为合适。

面试时，除了要能准确写出算法代码，还需清晰阐述算法原理、时间复杂度和空间复杂度分析过程，以及算法的稳定性等特性。此外，对于一些算法在特定场景下的优化（如快速排序的基准元素选择优化）也要有所了解，展现出对算法的深入理解和灵活运用能力。通过对常见排序算法的扎实掌握和深入思考，相信读者在面试算法相关问题时能够游刃有余，顺利通过面试关卡。

📌 下期预告：查找算法（二分查找、哈希查找）
❤️❤️❤️：如果你觉得这篇文章对你有帮助，欢迎点赞、关注本专栏！后续解锁更多功能，敬请期待！👍🏻 👍🏻 👍🏻
更多专栏汇总：
前端面试专栏
Node.js 实训专栏

数码产品严选