📚 前言：核心概念与记忆体系
🔍 1. 核心术语定义
在深入学习排序算法前，需先明确两个核心评价指标的定义，这是后续算法对比和选择的基础：
🔄 稳定性：指排序过程中，对于数组中两个相等的元素，其排序前后的相对位置是否保持不变。若保持不变则为稳定排序，反之则为不稳定排序。稳定性的核心意义在于，当排序场景中存在“多关键字排序”（如先按成绩排序，再按姓名排序）时，稳定排序可保证前序排序结果不被破坏。
⏱️ 时间复杂度：用于描述排序算法执行时间随数据规模增长的变化趋势，通常关注最坏情况、平均情况和最好情况三种场景。常用量级有 O(n²)（平方阶，效率较低）、O(nlogn)（线性对数阶，效率较高）、O(n^1.3)（亚平方阶）等，其中 n 为待排序数据的规模。
🗄️ 空间复杂度：指排序算法执行过程中所需额外存储空间的大小，分为原地排序（O(1)，仅需常数级额外空间）和非原地排序（如 O(n)、O(logn)，需额外线性或对数级空间）。
📝 2. 记忆口诀与核心特征速记
为快速掌握八大排序的核心特征，可借助以下口诀建立记忆体系：
🔄 稳定性口诀：插帽龟（插入、冒泡、归并）稳如狗；选快堆希（选择、快速、堆、希尔）不稳；基数排序单独记——“鸡你太稳”（谐音记忆，基数排序为稳定排序）。
⏱️ 时间复杂度口诀：插帽选（插入、冒泡、选择）平均平方阶（O(n²)），插帽最好线性阶（O(n)，适用于基本有序数据）；快堆归（快速、堆、归并）平均对数阶（O(nlogn)），快排最坏平方阶（O(n²)，可通过优化枢轴规避）；希尔排序亚平方（O(n^1.3)），基数排序看位数（O(d(n+r))，d 为数字位数，r 为基数）。
📊 3. 八大排序核心特征总表
📌 一、直接插入排序
🔍 1. 核心思想
直接插入排序的核心逻辑源于日常生活中整理扑克牌的行为：将待排序数组划分为“已排序区”和“未排序区”两个部分。初始状态下，已排序区仅包含数组的第一个元素（单个元素天然有序）；随后，从第二个元素开始，依次取出未排序区的每个元素，将其与已排序区的元素从后向前逐一比较，找到该元素的合适插入位置（即找到第一个小于或等于该元素的位置，若所有元素均大于该元素，则插入到已排序区的起始位置）；在找到插入位置后，将已排序区中大于当前元素的所有元素向后平移一位，为当前元素腾出插入空间，最终完成插入操作。重复上述过程，直到未排序区的所有元素均被插入到已排序区，排序完成。
📋 2. 核心执行流程
以测试用例数组 [49, 38, 65, 97, 76, 13, 27, 49] 为例，核心执行流程如下：
1. 初始化：已排序区仅含第一个元素 [49]，未排序区为 [38, 65, 97, 76, 13, 27, 49]。
2. 遍历插入：依次取出未排序区元素，与已排序区元素从后向前比较，找到插入位置后平移元素并插入（如 38<49，插入已排序区首位；65>49，插入末尾等）。
3. 完成排序：当未排序区元素全部插入后，得到有序数组 [13, 27, 38, 49, 49, 65, 76, 97]。
💻 3. Python代码实现
def insertion_sort(arr):
"""
直接插入排序实现
:param arr: 待排序数组（列表）
:return: 排序后的数组（不修改原数组）
"""
# 复制输入数组，避免直接修改原数据
arr_sorted = arr.copy()
n = len(arr_sorted)
# 从第二个元素开始遍历（第一个元素已构成初始已排序区）
for i in range(1, n):
# 保存当前要插入的元素（避免后续元素后移时被覆盖）
current = arr_sorted[i]
# 初始化已排序区的末尾指针 j，指向当前元素的前一个位置
j = i - 1
# 向前遍历已排序区，寻找当前元素的插入位置
# 循环条件：j >= 0（未遍历完已排序区）且 已排序区元素 > 当前元素（需要继续后移）
while j >= 0 and arr_sorted[j] > current:
# 将大于当前元素的元素向后平移一位
arr_sorted[j + 1] = arr_sorted[j]
# 指针 j 向前移动一位
j -= 1
# 找到插入位置（j + 1），将当前元素插入
arr_sorted[j + 1] = current
return arr_sorted
# 测试用例
if __name__ == "__main__":
test_arr = [49, 38, 65, 97, 76, 13, 27, 49]
result = insertion_sort(test_arr)
print("原始数组：", test_arr)
print("排序后数组：", result) # 输出：[13, 27, 38, 49, 49, 65, 76, 97]
🔍 4. 代码核心逻辑解析
1. 数组复制：通过 arr.copy() 复制输入数组，确保排序过程不会修改原数组，符合函数设计的“无副作用”原则。
2. 外层循环：for i in range(1, n)，从第二个元素（索引 1）开始遍历，因为第一个元素（索引 0）是初始已排序区，无需处理。
3. 保存当前元素：current = arr_sorted[i]，这一步是关键。因为后续在寻找插入位置时，需要将已排序区的元素向后平移，可能会覆盖当前元素所在的位置，因此提前保存。
4. 内层循环（寻找插入位置）：while j >= 0 and arr_sorted[j] > current。j 从 i-1 开始向前移动，只要已排序区的元素大于当前元素，就将该元素向后平移一位（arr_sorted[j + 1] = arr_sorted[j]），直到找到小于或等于当前元素的位置，或者遍历完已排序区（j < 0）。
5. 插入元素：arr_sorted[j + 1] = current。当退出内层循环时，j 指向的是最后一个大于当前元素的位置（或 j = -1，说明当前元素是已排序区最小元素），因此插入位置为 j + 1。
6. 稳定性保证：由于内层循环的条件是 arr_sorted[j] > current（而非 >=），当遇到与当前元素相等的元素时，不会继续向后平移，而是将当前元素插入到相等元素的后面，从而保证了相同元素的相对位置不变，实现了稳定性。
📝 5. 算法特点与优化方向
优点：
1. 逻辑简单直观，易于理解和实现，代码量少。
2. 原地排序，空间复杂度为 O(1)，对内存资源占用少。
3. 对于基本有序的数据（如接近排序完成的数组），效率极高，最好时间复杂度可达 O(n)，此时只需遍历一次数组，无需大量元素平移。
4. 稳定排序，适用于需要保持相同元素相对位置的场景。
缺点：
1. 时间复杂度为 O(n²)，对于大规模无序数据，效率极低。因为当数据无序时，每个元素都需要向前遍历整个已排序区，且需要大量元素平移操作。
优化方向：
1. 折半插入排序：在寻找插入位置时，由于已排序区是有序的，可以使用二分查找（折半查找）替代线性遍历，减少比较次数。但元素平移的次数并未减少，因此时间复杂度仍为 O(n²)，但在比较操作成本较高的场景（如复杂对象排序）中，可提升效率。
2. 希尔排序：直接插入排序的进阶优化，通过按步长分组减少元素平移的距离，大幅提升效率。
📌 二、希尔排序（缩小增量排序）
🔍 1. 核心思想
希尔排序是对直接插入排序的改进，其核心思路是：通过引入“步长（增量）”的概念，将待排序数组按步长划分为多个子数组，对每个子数组分别执行直接插入排序；然后逐步缩小步长（通常是前一步长的一半），重复分组和插入排序的操作；当步长缩小到 1 时，整个数组被划分为一个子数组，此时执行的直接插入排序与普通直接插入排序一致，排序完成。
希尔排序的设计初衷是解决直接插入排序在大规模无序数据下的低效问题。直接插入排序中，元素需要逐步向前平移，当元素距离其正确位置较远时，需要多次平移；而希尔排序通过大步长分组，可让元素快速向其正确位置靠拢，减少后续小步长排序时的平移次数，从而提升整体效率。
📋 2. 核心执行流程
以测试用例数组 [49, 38, 65, 97, 76, 13, 27, 49] 为例，采用步长序列 n//2、n//4、...、1，核心流程如下：
初始数组：[49, 38, 65, 97, 76, 13, 27, 49]，n=8。
🔄 第一趟：步长 step=4
按步长 4 分组（共 4 组），每组执行直接插入排序，排序后数组变为 [49, 13, 27, 49, 76, 38, 65, 97]。
第一趟排序后数组：[49, 13, 27, 49, 76, 38, 65, 97]。
🔄 第二趟：步长 step=2
按步长 2 分组（共 2 组），每组执行直接插入排序，排序后数组变为 [27, 13, 49, 38, 65, 49, 76, 97]。
第二趟排序后数组：[27, 13, 49, 38, 65, 49, 76, 97]。
🔄 第三趟：步长 step=1
步长为 1 时，整个数组为一组执行直接插入排序，最终得到有序数组 [13, 27, 38, 49, 49, 65, 76, 97]。
第三趟排序后数组即为最终有序数组：[13, 27, 38, 49, 49, 65, 76, 97]。
💻 3. Python代码实现
def shell_sort(arr):
"""
希尔排序实现（采用步长折半序列）
:param arr: 待排序数组（列表）
:return: 排序后的数组（不修改原数组）
"""
arr_sorted = arr.copy()
n = len(arr_sorted)
# 初始化步长为数组长度的一半
step = n // 2
# 逐步缩小步长，直到步长为 0
while step > 0:
# 按步长分组，对每组执行直接插入排序
# i 从 step 开始，遍历每组的第二个及以后元素（每组第一个元素已有序）
for i in range(step, n):
# 保存当前要插入的元素
current = arr_sorted[i]
# 初始化组内已排序区的末尾指针 j，指向当前元素的前一个组内元素
j = i - step
# 组内向前遍历，寻找插入位置
while j >= 0 and arr_sorted[j] > current:
# 组内元素向后平移 step 位
arr_sorted[j + step] = arr_sorted[j]
j -= step
# 插入当前元素到组内正确位置
arr_sorted[j + step] = current
# 步长折半，缩小增量
step = step // 2
return arr_sorted
# 测试用例
if __name__ == "__main__":
test_arr = [49, 38, 65, 97, 76, 13, 27, 49]
result = shell_sort(test_arr)
print("原始数组：", test_arr)
print("排序后数组：", result) # 输出：[13, 27, 38, 49, 49, 65, 76, 97]
🔍 4. 代码核心逻辑解析
1. 数组复制：与直接插入排序一致，通过 arr.copy() 避免修改原数组。
2. 步长初始化与缩小：初始步长为 n//2，之后每趟排序后步长折半（step = step//2），直到步长为 0 时退出循环，排序完成。
3. 分组插入排序：外层循环 for i in range(step, n)，遍历每组的第二个及以后元素（每组第一个元素索引为 0、1、...、step-1，已构成组内初始已排序区）。
4. 组内元素保存与遍历：current = arr_sorted[i] 保存当前要插入的元素；j = i - step 初始化组内已排序区末尾指针，指向当前元素的前一个组内元素（间隔 step 位）。
5. 组内元素平移：while j >= 0 and arr_sorted[j] > current，组内向前遍历，若已排序区元素大于当前元素，则将该元素向后平移 step 位（arr_sorted[j + step] = arr_sorted[j]），直到找到插入位置。
6. 组内元素插入：arr_sorted[j + step] = current，将当前元素插入到组内正确位置。
7. 不稳定性原因：分组排序过程中，相同元素可能被分到不同组，排序后其相对位置可能被打乱。例如，若数组中有两个相等元素，在大 step 分组时，可能一个在组内前半部分，一个在另一组的后半部分，排序后相对位置发生变化。
📝 5. 算法特点与步长序列选择
优点：
1. 效率高于直接插入排序：通过大步长分组让元素快速靠拢正确位置，减少后续小步长排序的平移次数，平均时间复杂度为 O(n^1.3)，优于直接插入排序的 O(n²)。
2. 原地排序：空间复杂度为 O(1)，内存占用少。
3. 对数据适应性强：无论是有序、无序还是随机数据，都能保持较好的效率（相对直接插入排序）。
缺点：
1. 不稳定排序：分组排序可能打乱相同元素的相对位置，不适用于需要稳定排序的场景。
2. 逻辑较直接插入排序复杂：需要理解分组和步长缩小的逻辑，代码实现稍复杂。
3. 步长序列影响效率：不同的步长序列会导致排序效率差异较大，最优步长序列的选择是希尔排序的关键。
常见步长序列：
1. 折半序列（n//2, n//4, ..., 1）：最常用的步长序列，实现简单，但效率并非最优。
2. 希尔序列（1, 4, 13, 40, ...）：由希尔提出的原始序列，效率优于折半序列。
3. 帕佩尔诺夫 - 斯塔舍维奇序列（1, 2, 5, 10, 23, 57, ...）：效率更高，但实现复杂。
📌 三、冒泡排序
🔍 1. 核心思想
冒泡排序的核心逻辑是“相邻元素两两比较，逆序则交换”。排序过程中，每一趟遍历都会将当前未排序区的最大值逐步“冒泡”到未排序区的末尾，成为已排序区的新元素。具体来说，从数组起始位置开始，依次比较相邻的两个元素，若前一个元素大于后一个元素，则交换两者位置；继续向后比较下一对相邻元素，直到遍历完未排序区的末尾。重复上述过程，每趟遍历后未排序区的长度减少 1，已排序区的长度增加 1，直到未排序区长度为 0，排序完成。
冒泡排序的关键优化点是“提前退出”：若某一趟遍历过程中没有发生任何元素交换，说明数组已经完全有序，此时无需继续后续遍历，可直接退出排序过程，大幅提升在基本有序数据下的效率。
📋 2. 核心执行流程
以测试用例数组 [49, 38, 65, 97, 76, 13, 27, 49] 为例，含提前退出优化的核心流程如下：
初始状态：已排序区为空，未排序区为整个数组 [49, 38, 65, 97, 76, 13, 27, 49]。
🔄 第一趟（未排序区长度8）
相邻元素两两比较交换，最大值 97 冒泡至末尾，数组变为 [38, 49, 65, 76, 13, 27, 49, 97]，已排序区新增 [97]。
本趟发生交换，继续下一趟。
🔄 第二至五趟
每趟将未排序区最大值（76、65、49、49）依次冒泡至末尾，数组逐步有序，各趟均发生交换。
🔄 第六趟（未排序区长度3）
遍历未排序区 [13, 27, 38]，无任何元素交换，说明数组已完全有序，提前退出排序。
最终有序数组：[13, 27, 38, 49, 49, 65, 76, 97]。
💻 3. Python代码实现
def bubble_sort(arr):
"""
冒泡排序实现（含提前退出优化）
:param arr: 待排序数组（列表）
:return: 排序后的数组（不修改原数组）
"""
arr_sorted = arr.copy()
n = len(arr_sorted)
# 外层循环：控制排序趟数，最多需要 n-1 趟（每趟确定一个最大值）
for i in range(n):
# 标志位：记录本趟是否发生交换，初始为 False（未交换）
swapped = False
# 内层循环：遍历未排序区，比较相邻元素
# 未排序区范围：0 到 n-i-1（每趟后已排序区增加 1，未排序区减少 1）
for j in range(0, n - i - 1):
# 相邻元素逆序，交换两者位置
if arr_sorted[j] > arr_sorted[j + 1]:
arr_sorted[j], arr_sorted[j + 1] = arr_sorted[j + 1], arr_sorted[j]
swapped = True # 标记本趟发生了交换
# 若本趟未发生任何交换，说明数组已有序，提前退出
if not swapped:
break
return arr_sorted
# 测试用例
if __name__ == "__main__":
test_arr = [49, 38, 65, 97, 76, 13, 27, 49]
result = bubble_sort(test_arr)
print("原始数组：", test_arr)
print("排序后数组：", result) # 输出：[13, 27, 38, 49, 49, 65, 76, 97]
🔍 4. 代码核心逻辑解析
1. 数组复制：arr_sorted = arr.copy()，避免修改原数组。
2. 外层循环：for i in range(n)，控制排序趟数，最多需 n-1 趟（每趟确定一个最大值）。
3. 交换标志位：swapped = False，用于标记本趟是否发生交换，若未交换则说明数组已有序，可提前退出，优化效率。
4. 内层循环：for j in range(0, n - i - 1)，遍历未排序区（范围随每趟缩小），相邻元素逆序则交换，并标记 swapped 为 True。
5. 提前退出：若 swapped 为 False，直接 break 退出循环，避免无效遍历。
📝 5. 算法特点与优化方向
优点：
1. 逻辑极简，易于理解和实现，适合排序算法入门教学。
2. 原地排序，空间复杂度 O(1)，内存占用少。
3. 稳定排序，且可通过提前退出优化，在基本有序数据下效率极高（O(n)）。
缺点：
1. 时间复杂度 O(n²)，大规模无序数据下效率极低，元素交换次数多。
优化方向：
1. 双向冒泡排序（鸡尾酒排序）：从左到右和从右到左交替遍历，适用于数组两端无序、中间有序的场景，减少遍历次数。
2. 记录最后一次交换位置：将内层循环的终止条件改为最后一次交换的位置，减少后续无效遍历范围。
📌 四、快速排序
🔍 1. 核心思想
快速排序基于“分治思想”，核心逻辑是通过“选枢轴→分区→递归排序”三步实现：首先从数组中选择一个元素作为“枢轴（pivot）”；然后将数组划分为两个子区间，使得左区间的所有元素均小于等于枢轴，右区间的所有元素均大于枢轴（此过程为“分区”）；最后对左、右两个子区间分别递归执行上述步骤，直到子区间长度为 1（天然有序）或 0（空区间），排序完成。枢轴的选择直接影响排序效率，常用选择方式有：选第一个元素、选最后一个元素、随机选元素、选中间元素。
📋 2. 核心执行流程
以测试用例数组 [49, 38, 65, 97, 76, 13, 27, 49] 为例，选择第一个元素作为枢轴，核心流程如下：
1. 初始化：待排序数组 [49, 38, 65, 97, 76, 13, 27, 49]，选择枢轴 pivot=49（索引 0）。
2. 分区操作：通过双指针遍历，将小于等于 49 的元素移到左区间，大于 49 的元素移到右区间，分区后数组变为 [49, 38, 27, 13, 49, 76, 97, 65]，枢轴最终位置为索引 4（左区间：[49,38,27,13]，右区间：[76,97,65]）。
3. 递归排序：分别对左、右子区间递归执行快速排序：
- 左区间 [49,38,27,13] 选枢轴 49，分区后得到 [13,38,27,49]，再递归排序子区间 [13,38,27] 和 [49]（后者有序）；
- 右区间 [76,97,65] 选枢轴 76，分区后得到 [65,76,97]，再递归排序子区间 [65]（有序）和 [97]（有序）。
4. 完成排序：所有子区间排序完成后，合并得到有序数组 [13, 27, 38, 49, 49, 65, 76, 97]。
💻 3. Python代码实现
def quick_sort(arr):
"""
快速排序实现（选第一个元素为枢轴，递归实现）
:param arr: 待排序数组（列表）
:return: 排序后的数组（不修改原数组）
"""
# 基线条件：子数组长度≤1时直接返回（天然有序）
if len(arr) <= 1:
return arr.copy()
# 选择第一个元素作为枢轴
pivot = arr[0]
# 分区：左区间（≤枢轴）、右区间（>枢轴）
left = [x for x in arr[1:] if x <= pivot]
right = [x for x in arr[1:] if x > pivot]
# 递归排序左、右区间，合并结果（左 + [枢轴] + 右）
return quick_sort(left) + [pivot] + quick_sort(right)
# 优化版：原地分区（减少空间占用）
def quick_sort_in_place(arr, low=0, high=None):
"""
原地快速排序实现（选最后一个元素为枢轴）
:param arr: 待排序数组（列表）
:param low: 子区间起始索引
:param high: 子区间结束索引
:return: None（直接修改原数组）
"""
if high is None:
high = len(arr) - 1
def partition(arr, low, high):
"分区函数：返回枢轴最终位置"
pivot = arr[high] # 选最后一个元素为枢轴
i = low - 1 # i 是左区间的末尾指针（初始为-1，代表左区间为空）
for j in range(low, high):
# 若当前元素≤枢轴，加入左区间
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
# 将枢轴插入左、右区间之间（i+1为枢轴最终位置）
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
# 递归条件：子区间起始索引 < 结束索引
if low < high:
pivot_idx = partition(arr, low, high) # 获得枢轴位置
quick_sort_in_place(arr, low, pivot_idx - 1) # 递归左区间
quick_sort_in_place(arr, pivot_idx + 1, high) # 递归右区间
# 测试用例
if __name__ == "__main__":
test_arr = [49, 38, 65, 97, 76, 13, 27, 49]
# 非原地版本测试
result = quick_sort(test_arr)
print("原始数组：", test_arr)
print("非原地排序后：", result) # 输出：[13, 27, 38, 49, 49, 65, 76, 97]
# 原地版本测试
test_arr_in_place = test_arr.copy()
quick_sort_in_place(test_arr_in_place)
print("原地排序后：", test_arr_in_place) # 输出：[13, 27, 38, 49, 49, 65, 76, 97]
🔍 4. 代码核心逻辑解析
1. 非原地版本核心：
- 基线条件：子数组长度≤1 时直接返回，避免无限递归；
- 枢轴选择：选第一个元素为枢轴，实现简单；
- 分区逻辑：用列表推导式快速划分左、右区间，左区间≤枢轴，右区间 > 枢轴；
- 递归合并：递归排序左、右区间后，按“左 +[枢轴]+ 右”合并，得到有序数组。
2. 原地版本核心（优化空间）：
- 分区函数（partition）：选最后一个元素为枢轴，通过 i 指针标记左区间末尾，j 指针遍历子区间，将≤枢轴的元素交换到左区间，最终将枢轴插入 i+1 位置，返回枢轴索引；
- 递归调用：根据枢轴索引拆分左（low~pivot_idx-1）、右（pivot_idx+1~high）子区间，递归执行排序；
- 空间优化：无需额外创建左、右区间数组，空间复杂度从 O(n) 降至 O(logn)（仅递归栈占用）。
3. 不稳定性原因：分区过程中，相等元素可能被交换到枢轴两侧，破坏相对位置。例如数组 [49, 38, 49, 27]，选第一个 49 为枢轴，分区后第二个 49 会被分到右区间，相对位置改变。
📝 5. 算法特点与优化策略
优点：
1. 效率极高：平均时间复杂度 O(nlogn)，实际应用中通常比归并排序、堆排序更快（缓存友好、交换操作少）；
2. 可原地排序：优化后空间复杂度 O(logn)，内存占用少；
3. 适应性强：对随机数据、大规模数据排序效果优异。
缺点：
1. 不稳定排序：不适用于需保持相同元素相对位置的场景；
2. 最坏时间复杂度 O(n²)：当数组基本有序且选两端元素为枢轴时，会导致分区失衡（子区间一端为空），递归深度变为 n；
3. 递归实现依赖栈：大规模数据排序可能导致栈溢出（可改用迭代实现规避）。
优化策略：
1. 优化枢轴选择：采用“三数取中”（选第一个、中间、最后一个元素的中位数为枢轴）或随机选枢轴