排序算法通关攻略：比较排序篇（从青铜到王者）

写在前面排序算法是算法的Hello World但很多人学完就忘。今天我用最易懂的方式帮你把冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序这六大比较排序刻进脑子里。阅读指南每个算法都包含生活比喻一句话记住核心思想算法可视化一张流程图代码实现带详细注释LeetCode实战用真题巩固理解一、排序算法全家福在开始之前先认识一下今天的主角们算法时间复杂度空间复杂度稳定性核心思想冒泡排序O(n²)O(1)✅ 稳定相邻比较大的沉底选择排序O(n²)O(1)❌ 不稳定每轮选最小放到前面插入排序O(n²)O(1)✅ 稳定像抓牌一样插到合适位置希尔排序O(n^1.3)O(1)❌ 不稳定插入排序的升级版跳跃式插入归并排序O(n log n)O(n)✅ 稳定分而治之先分后合快速排序O(n log n)O(log n)❌ 不稳定选基准小的左边大的右边二、冒泡排序Bubble Sort—— 像汽水冒泡一样简单 一句话记住就像汽水里的气泡轻的往上浮重的往下沉。 核心思想从头开始两两比较相邻元素如果顺序不对就交换。每一轮都会把当前未排序部分中最大的元素冒泡到最后。举个栗子对 [5, 1, 4, 2, 8] 排序第一轮51交换→[1,5,4,2,8]54交换→[1,4,5,2,8]52交换→[1,4,2,5,8]58不动第一轮结束8已经就位第二轮14不动42交换→[1,2,4,5,8]45不动第三轮12不动24不动 → 已经有序可以提前结束 算法流程图 代码实现/** * 冒泡排序带优化 * param {number[]} arr 待排序数组 * returns {number[]} 排序后数组 */ function bubbleSort(arr) { const n arr.length; // 外层循环控制需要比较的轮数 for (let i 0; i n - 1; i) { // 优化标记这一轮是否发生过交换 let swapped false; // 内层循环进行相邻元素比较 // 为什么是 n-1-i因为每轮结束后最后i个元素已经有序 for (let j 0; j n - 1 - i; j) { // 如果前面的比后面的大交换 if (arr[j] arr[j 1]) { // 经典的三行交换 [arr[j], arr[j 1]] [arr[j 1], arr[j]]; swapped true; } } // 如果这一轮没有发生交换说明数组已经有序 if (!swapped) break; } return arr; } // 测试 console.log(bubbleSort([5, 1, 4, 2, 8])); // [1, 2, 4, 5, 8] LeetCode实战颜色分类题目LeetCode 75. 颜色分类题目描述给定一个包含红色、白色和蓝色共 n 个元素的数组原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。思路分析虽然这道题有更优的解法三指针但作为新手用冒泡排序理解排序过程非常合适。因为只有三种值冒泡排序也能轻松搞定。解题代码/** * param {number[]} nums * return {void} 原地修改不返回 */ var sortColors function(nums) { const n nums.length; // 冒泡排序 for (let i 0; i n - 1; i) { for (let j 0; j n - 1 - i; j) { if (nums[j] nums[j 1]) { // 交换 [nums[j], nums[j 1]] [nums[j 1], nums[j]]; } } } // 不用返回nums已经原地修改 };时间复杂度O(n²)空间复杂度O(1)三、选择排序Selection Sort—— 矮个子里拔将军 一句话记住每轮从剩下的元素中选出最小的放到前面。 核心思想把数组分成两部分已排序区和未排序区。每一轮从未排序区找到最小的元素放到已排序区的末尾。举个栗子对 [64, 25, 12, 22, 11] 排序第一轮找出最小值11与第一个元素64交换 → [11, 25, 12, 22, 64]第二轮从剩余[25,12,22,64]中找出最小值12与第二个元素25交换 → [11, 12, 25, 22, 64]第三轮从剩余[25,22,64]中找出最小值22与第三个元素25交换 → [11, 12, 22, 25, 64]第四轮从剩余[25,64]中找出最小值25位置不变 代码实现/** * 选择排序 * param {number[]} arr 待排序数组 * returns {number[]} 排序后数组 */ function selectionSort(arr) { const n arr.length; for (let i 0; i n - 1; i) { // 假设当前位置i的元素是最小的 let minIndex i; // 在未排序部分中找真正的最小值 for (let j i 1; j n; j) { if (arr[j] arr[minIndex]) { minIndex j; } } // 如果最小值不在当前位置交换 if (minIndex ! i) { [arr[i], arr[minIndex]] [arr[minIndex], arr[i]]; } } return arr; } // 测试 console.log(selectionSort([64, 25, 12, 22, 11])); // [11, 12, 22, 25, 64] LeetCode实战选择排序的变种应用题目力扣讨论区题目 - 选择排序过程模拟题目描述给定初始序列 A[1∼n]保证 A 是排列即 1∼n 每个数恰好出现一次和 m 个询问 q[1,2,…,m]请你依次输出第 q[i] 趟之后的序列 A。思路分析这道题实际上是让我们模拟选择排序的中间过程。选择排序每趟会确定一个位置上的最终元素。我们只需要模拟到第q[i]趟然后输出当前数组状态。解题代码def selection_sort_process(n, arr, queries): result [] arr arr.copy() # 避免修改原数组 for i in range(max(queries)): # 只需要模拟到最大的q # 执行一趟选择排序 min_idx i for j in range(i 1, n): if arr[j] arr[min_idx]: min_idx j if min_idx ! i: arr[i], arr[min_idx] arr[min_idx], arr[i] # 如果当前趟数在询问中记录结果 if i 1 in queries: result.append(arr.copy()) return result时间复杂度O(n × max(q))空间复杂度O(n)四、插入排序Insertion Sort—— 打扑克牌 一句话记住就像打牌时整理手牌每抓一张新牌就插到已经有序的牌中适当位置。 核心思想把数组分成两部分已排序区左边和未排序区右边。每次从右边拿一个元素在左边找到合适的位置插入。举个栗子对 [12, 11, 13, 5, 6] 排序初始已排序 [12]未排序 [11,13,5,6]第一轮取11比12小插入到12前面 → [11,12,13,5,6]第二轮取13比12大位置不变 → [11,12,13,5,6]第三轮取5比前面所有都小插入到最前面 → [5,11,12,13,6]第四轮取6插入到5和11之间 → [5,6,11,12,13] 算法流程图 代码实现/** * 插入排序 * param {number[]} arr 待排序数组 * returns {number[]} 排序后数组 */ function insertionSort(arr) { const n arr.length; // 从第二个元素开始第一个元素默认有序 for (let i 1; i n; i) { // 保存当前要插入的元素 const key arr[i]; let j i - 1; // 在已排序区从后往前找插入位置 // 比key大的元素都往后挪一位 while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } // 插入到正确位置 arr[j 1] key; } return arr; } // 测试 console.log(insertionSort([12, 11, 13, 5, 6])); // [5, 6, 11, 12, 13] LeetCode实战搜索插入位置题目LeetCode LCR 068. 搜索插入位置题目描述给定一个排序的整数数组 nums 和一个整数目标值 target请在数组中找到 target并返回其下标。如果目标值不存在于数组中返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。思路分析这道题虽然要求用二分查找O(log n)但它的思想完美诠释了插入排序的核心——找到元素应该插入的位置。我们用二分法快速定位插入点。解题代码/** * param {number[]} nums 排序数组 * param {number} target 目标值 * return {number} 插入位置 */ var searchInsert function(nums, target) { let left 0; let right nums.length - 1; while (left right) { const mid Math.floor((left right) / 2); if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; } else { right mid - 1; } } // 当循环结束时left就是target应该插入的位置 return left; };时间复杂度O(log n)空间复杂度O(1)五、希尔排序Shell Sort—— 插入排序的进阶版 一句话记住让元素先跳着走再一步步走减少大量移动。 核心思想插入排序有个缺点如果一个很小的元素在很后面它要一步步挪到前面太慢了。希尔排序通过分组插入排序来解决这个问题。具体做法先取一个增量gap比如数组长度的一半将所有距离为gap的元素分成一组每组内进行插入排序缩小gap通常是除以2重复上述过程直到gap1进行最后一次插入排序举个栗子对 [35, 63, 28, 72, 1, 43, 53, 48, 18] 排序gap从4开始gap4分成4组每组内排序gap2重新分组每组内排序gap1全局插入排序完成 算法流程图 代码实现/** * 希尔排序 * param {number[]} arr 待排序数组 * returns {number[]} 排序后数组 */ function shellSort(arr) { const n arr.length; // 初始增量gap为长度的一半每次减半 for (let gap Math.floor(n / 2); gap 0; gap Math.floor(gap / 2)) { // 对每个分组进行插入排序 // 注意这里不是分组处理而是从gap开始每个元素都和自己组内的前一个元素比较 for (let i gap; i n; i) { const temp arr[i]; let j i; // 在同一组内进行插入排序 while (j - gap 0 arr[j - gap] temp) { arr[j] arr[j - gap]; j - gap; } arr[j] temp; } } return arr; } // 测试 console.log(shellSort([35, 63, 28, 72, 1, 43, 53, 48, 18])); // [1, 18, 28, 35, 43, 48, 53, 63, 72] LeetCode实战希尔排序的应用场景题目LeetCode 506. 相对名次改编题目描述给你一个长度为 n 的整数数组 score其中 score[i] 是第 i 位运动员在比赛中的得分。所有得分都互不相同。运动员根据得分决定名次名次第 1 的运动员获得金牌 Gold Medal名次第 2 获得银牌 Silver Medal名次第 3 获得铜牌 Bronze Medal其余名次获得他们的名次编号从 4 到 n。请返回一个字符串数组 answer其中 answer[i] 是第 i 位运动员的名次。思路分析我们需要按分数从高到低排序但排序后要知道每个分数原来的位置可以用希尔排序同时记录索引解题代码/** * param {number[]} score * return {string[]} */ var findRelativeRanks function(score) { const n score.length; // 创建 [分数, 原索引] 对数组 const athletes score.map((val, idx) [val, idx]); // 用希尔排序按分数降序排序 for (let gap Math.floor(n / 2); gap 0; gap Math.floor(gap / 2)) { for (let i gap; i n; i) { const temp athletes[i]; let j i; while (j - gap 0 athletes[j - gap][0] temp[0]) { athletes[j] athletes[j - gap]; j - gap; } athletes[j] temp; } } // 分配名次 const result new Array(n); for (let i 0; i n; i) { const originalIdx athletes[i][1]; if (i 0) result[originalIdx] Gold Medal; else if (i 1) result[originalIdx] Silver Medal; else if (i 2) result[originalIdx] Bronze Medal; else result[originalIdx] (i 1).toString(); } return result; };六、归并排序Merge Sort—— 分而治之的典范 一句话记住先分到最小再两两合并合并的时候顺便排序。 核心思想采用分治法Divide and Conquer分把数组从中间分成左右两部分分别排序治当子数组长度为1时自然有序合将两个有序的子数组合并成一个有序数组举个栗子对 [38, 27, 43, 3, 9, 82, 10] 排序[38 27 43 3 9 82 10]分左 分右[38 27 43 3] [9 82 10]重复[38 27] [43 3] [9 82] [10]重复[38] [27] [43] [3] [9] [82] [10]排序合并[27 38] [3 43] [9 82] [10]重复[3 27 38 43] [9 10 82]完成[3 9 10 27 38 43 82] 算法流程图 代码实现/** * 归并排序递归版本 * param {number[]} arr 待排序数组 * returns {number[]} 排序后数组 */ function mergeSort(arr) { // 递归终止条件数组长度小于等于1已经有序 if (arr.length 1) return arr; // 1. 分找到中间点分割数组 const mid Math.floor(arr.length / 2); const left arr.slice(0, mid); const right arr.slice(mid); // 2. 治递归排序左右两部分 const sortedLeft mergeSort(left); const sortedRight mergeSort(right); // 3. 合合并两个有序数组 return merge(sortedLeft, sortedRight); } /** * 合并两个有序数组 * param {number[]} left 左有序数组 * param {number[]} right 右有序数组 * returns {number[]} 合并后的有序数组 */ 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]); i; } else { result.push(right[j]); j; } } // 处理剩余元素左右可能有一边还剩一些 while (i left.length) { result.push(left[i]); i; } while (j right.length) { result.push(right[j]); j; } return result; } // 测试 console.log(mergeSort([38, 27, 43, 3, 9, 82, 10])); // [3, 9, 10, 27, 38, 43, 82] LeetCode实战合并两个有序数组题目LeetCode 88. 合并两个有序数组题目描述给你两个按非递减顺序排列的整数数组 nums1 和 nums2另有两个整数 m 和 n分别表示 nums1 和 nums2 中的元素数目。请你合并 nums2 到 nums1 中使合并后的数组同样按非递减顺序排列。注意nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。思路分析这正是归并排序中merge操作的直接应用我们可以从后往前填充避免使用额外空间。解题代码/** * param {number[]} nums1 * param {number} m nums1中有效元素个数 * param {number[]} nums2 * param {number} n nums2中有效元素个数 * return {void} 原地修改nums1 */ var merge function(nums1, m, nums2, n) { // 从后往前填充避免覆盖 let i m - 1; // nums1最后一个有效元素 let j n - 1; // nums2最后一个元素 let k m n - 1; // 合并后数组的最后一个位置 // 从后往前比较把大的放在后面 while (i 0 j 0) { if (nums1[i] nums2[j]) { nums1[k] nums1[i]; i--; } else { nums1[k] nums2[j]; j--; } k--; } // 如果nums2还有剩余全部放入nums1前面 while (j 0) { nums1[k] nums2[j]; j--; k--; } // nums1剩余的元素已经在正确位置不用处理 };七、快速排序Quick Sort—— 应用最广的排序算法 一句话记住选个基准小的放左边大的放右边然后左右分别再来一次。 核心思想也是分治思想但和归并不同先划分再递归。步骤选择基准pivot通常选第一个元素划分partition把小于基准的放左边大于基准的放右边基准放在中间递归对左右两部分重复上述过程举个栗子对 [3, 7, 8, 5, 2, 1, 9, 5, 4] 排序选第一个3为基准划分后左边 [2,1]都小于3基准3右边 [7,8,5,9,5,4]都大于3对左边 [2,1] 快速排序对右边 [7,8,5,9,5,4] 快速排序最后合并 算法流程图 代码实现/** * 快速排序 * param {number[]} arr 待排序数组 * param {number} left 左边界 * param {number} right 右边界 * returns {void} 原地排序 */ function quickSort(arr, left 0, right arr.length - 1) { if (left right) { // 获取划分点 const pivotIndex partition(arr, left, right); // 递归排序左右两部分 quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex 1, right); } } /** * 划分函数把小于基准的放左边大于基准的放右边 * param {number[]} arr * param {number} left * param {number} right * returns {number} 基准的最终位置 */ function partition(arr, left, right) { // 选择第一个元素作为基准 const pivot arr[left]; // i指向小于基准的区域的最后一个位置 let i left; // 遍历剩余元素 for (let j left 1; j right; j) { // 如果当前元素小于基准把它交换到左边区域 if (arr[j] pivot) { i; [arr[i], arr[j]] [arr[j], arr[i]]; } } // 把基准放到中间位置i的位置 [arr[left], arr[i]] [arr[i], arr[left]]; // 返回基准的最终位置 return i; } // 测试 const arr [3, 7, 8, 5, 2, 1, 9, 5, 4]; quickSort(arr); console.log(arr); // [1, 2, 3, 4, 5, 5, 7, 8, 9] LeetCode实战数组中的第K个最大元素题目LeetCode 215. 数组中的第K个最大元素题目描述给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。思路分析快速排序的partition操作有一个重要性质一次partition后基准元素的位置就是它在最终有序数组中的位置。我们可以利用这一点不需要完全排序只需找到第n-k小的元素第k大 第n-k小。解题代码/** * param {number[]} nums * param {number} k * return {number} */ var findKthLargest function(nums, k) { const n nums.length; // 第k大就是第n-k小0-indexed const target n - k; let left 0; let right n - 1; while (left right) { const pivotIndex partition(nums, left, right); if (pivotIndex target) { return nums[pivotIndex]; } else if (pivotIndex target) { // 基准在目标左边去右边找 left pivotIndex 1; } else { // 基准在目标右边去左边找 right pivotIndex - 1; } } }; // 复用之前的partition函数 function partition(arr, left, right) { const pivot arr[left]; let i left; for (let j left 1; j right; j) { if (arr[j] pivot) { i; [arr[i], arr[j]] [arr[j], arr[i]]; } } [arr[left], arr[i]] [arr[i], arr[left]]; return i; }时间复杂度平均O(n)最坏O(n²)空间复杂度O(1) 下期预告下一期我们将学习非比较排序计数排序、桶排序、基数排序——这些算法可以突破O(n log n)的下界如果你觉得这篇文章对你有帮助欢迎点赞、收藏、转发有问题欢迎在评论区讨论