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

📝 写在前面

排序算法是算法的"Hello World"，但很多人学完就忘。今天我用最易懂的方式帮你把冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序这六大比较排序刻进脑子里。

阅读指南：每个算法都包含👇

• 生活比喻：一句话记住核心思想

• 算法可视化：一张流程图

• 代码实现：带详细注释

• LeetCode实战：用真题巩固理解

一、排序算法全家福

在开始之前，先认识一下今天的主角们：

二、冒泡排序（Bubble Sort）—— 像汽水冒泡一样简单

🎯 一句话记住

就像汽水里的气泡，轻的往上浮，重的往下沉。

🤔 核心思想

从头开始，两两比较相邻元素，如果顺序不对就交换。每一轮都会把当前未排序部分中最大的元素"冒泡"到最后。

举个栗子：对 [5, 1, 4, 2, 8] 排序

• 第一轮：5>1交换→[1,5,4,2,8]；5>4交换→[1,4,5,2,8]；5>2交换→[1,4,2,5,8]；5<8不动

• 第一轮结束，8已经就位

• 第二轮：1<4不动；4>2交换→[1,2,4,5,8]；4<5不动

• 第三轮：1<2不动；2<4不动 → 已经有序，可以提前结束

📊 算法流程图

💻 代码实现

/**
* 冒泡排序（带优化）
* @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）—— 插入排序的进阶版

🎯 一句话记住

让元素先跳着走，再一步步走，减少大量移动。

🤔 核心思想

插入排序有个缺点：如果一个很小的元素在很后面，它要一步步挪到前面，太慢了。希尔排序通过分组插入排序来解决这个问题。

具体做法：

举个栗子：对 [35, 63, 28, 72, 1, 43, 53, 48, 18] 排序，gap从4开始 

• gap=4：分成4组，每组内排序

• gap=2：重新分组，每组内排序

• gap=1：全局插入排序，完成

• 📊 算法流程图

💻 代码实现

/**
* 希尔排序
* @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）—— 应用最广的排序算法

🎯 一句话记住

选个基准，小的放左边，大的放右边，然后左右分别再来一次。

🤔 核心思想

也是分治思想，但和归并不同：先划分，再递归。

步骤：

举个栗子：对 [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)的下界！

如果你觉得这篇文章对你有帮助，欢迎点赞、收藏、转发！有问题欢迎在评论区讨论～