.png){kind=small}
排序算法的稳定性
什么是算法的稳定性？
算法的稳定性（Stable Sorting）是指排序算法在排序过程中，相等元素的相对顺序是否保持不变。具体来说：
•稳定排序算法：如果两个相等的元素
A和B（A == B），在原始序列中A出现在B之前，那么排序后A仍然在B之前。•不稳定排序算法：排序后
A和B的相对顺序可能发生改变。
1. 为什么稳定性重要？
稳定性在某些应用场景中至关重要，例如：
•多关键字排序：
比如先按年龄排序，再按姓名排序。如果第二次排序不稳定，年龄相同的记录可能会被打乱。•数据库查询：
某些查询需要保持相同键值的记录顺序不变。•UI 列表排序：
用户期望相同值的项目顺序不会无故变化。
原地排序
原地排序（In-place Sorting）是指算法在排序过程中仅使用常数级别（O(1)）的额外存储空间，主要依赖输入数据本身的空间进行排序操作。换句话说，排序过程中不会因为数据规模的增大而申请额外的内存空间（如数组、链表等）。
核心特点
•空间复杂度为 O(1)：仅使用少量临时变量（如交换时的
temp），不依赖额外数据结构（如新数组）。•直接修改原数据：排序后的结果存储在原始数据结构中，而不是返回一个新副本。
•适合内存受限场景：例如嵌入式系统或大数据处理，避免内存浪费。
三种排序算法的对比
以下是 冒泡排序、选择排序、插入排序 的全面对比，涵盖时间复杂度、空间复杂度、稳定性、适用场景及代码示例，帮助快速掌握它们的核心区别：
1. 核心对比表
2. 详细解析
(1) 时间复杂度
冒泡排序：
最好情况（已有序）：仅需一轮比较（O(n)）。
最坏情况（逆序）：需
n(n-1)/2次比较和交换（O(n²)）。
选择排序：
无论数据是否有序，固定比较
n(n-1)/2次（O(n²)），但交换次数少（最多n-1次）。
插入排序：
最好情况（已有序）：仅需
n-1次比较（O(n)）。最坏情况（逆序）：需
n(n-1)/2次比较和移动（O(n²)）。
(2) 空间复杂度
三者均为 原地排序（O(1)），无需额外存储空间。
(3) 稳定性
稳定：冒泡排序、插入排序（不改变相等元素的原始顺序）。
不稳定：选择排序（如
[5, 5, 2]，第一个5会被交换到末尾）。
(4) 排序过程特点
冒泡排序：
每轮通过相邻交换将最大值“冒泡”到末尾。
优化：可设置标志位提前终止（若某轮无交换）。
选择排序：
每轮选出未排序部分的最小值，与当前位置交换。
优势：交换次数少（适合交换成本高的场景，如磁盘存储数据）。
插入排序：
将未排序元素插入已排序序列的合适位置。
优势：对部分有序数据效率接近 O(n)。
3. 代码示例（Python）
# 冒泡排序（优化版）
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped:
break
# 选择排序
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
# 插入排序
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >= 0 and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key4. 性能对比场景
数据量小（n < 100）：三者差异不大，插入排序常更优（常数因子小）。
基本有序数据：插入排序 ≈ 冒泡排序（O(n)） > 选择排序（O(n²)）。
交换成本高（如对象排序）：选择排序（交换次数少）优于冒泡排序。
5. 总结
优先选择插入排序：适合小规模或部分有序数据，实现简单且稳定。
避免冒泡排序：除非数据已基本有序且需要稳定排序。
选择排序的适用场景：交换成本高且不要求稳定性时。
扩展思考：为什么插入排序在标准库中（如
Java的Arrays.sort()）常用于小数组的排序？
→ 因对小规模数据，插入排序的常数因子优于更高级的算法（如快速排序的递归开销）。
归并排序和快排
快速排序（Quick Sort）和归并排序（Merge Sort）详解
1. 快速排序（Quick Sort）
核心思想：分治法（Divide and Conquer） + 原地排序
关键操作：分区（Partition），选择一个基准值（pivot），将数组分为两部分：小于基准的放左边，大于基准的放右边。
算法步骤
选择基准（pivot）：
通常选第一个元素、最后一个元素或随机元素（避免最坏情况）。
分区（Partition）：
使用双指针（
i和j），i从左找比基准大的，j从右找比基准小的，交换它们。最终将基准放到正确位置，使得左边 ≤ 基准 ≤ 右边。
递归排序左右子数组：
对左半部分和右半部分分别递归调用快排。
代码实现（Python）
def quick_sort(arr, low, high):
if low < high:
# 找到分区点
pivot_idx = partition(arr, low, high)
# 递归排序左半部分
quick_sort(arr, low, pivot_idx - 1)
# 递归排序右半部分
quick_sort(arr, pivot_idx + 1, high)
def partition(arr, low, high):
pivot = arr[high] # 选择最后一个元素作为基准
i = low - 1 # i 是小于基准的区域的右边界
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i] # 交换
# 把基准放到正确位置
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1 # 返回基准的最终位置时间复杂度
平均情况：
O(n log n)（每次分区较均衡）。最坏情况：
O(n²)（如数组已排序或逆序，分区极度不平衡）。优化方法：
随机化基准（避免最坏情况）。
三数取中法（选
arr[low],arr[mid],arr[high]的中位数作为基准）。
空间复杂度
递归栈空间：
O(log n)（平均情况，取决于递归深度）。最坏情况：
O(n)（极端不平衡时递归深度为n）。
稳定性
不稳定：分区交换可能改变相等元素的相对顺序。
适用场景
大规模数据：平均效率高，缓存友好（局部性原理）。
内存受限环境：原地排序，额外空间少。
2. 归并排序（Merge Sort）
核心思想：分治法 + 非原地排序（需额外空间）
关键操作：分解 + 合并，将数组分成两半，分别排序后再合并。
算法步骤
分解（Divide）：
递归地将数组分成两半，直到子数组长度为1（天然有序）。
合并（Merge）：
创建临时数组，按顺序合并两个有序子数组。
代码实现（Python）
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
# 递归排序左右两半
merge_sort(left)
merge_sort(right)
# 合并两个有序数组
i = j = k = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
# 处理剩余元素
while i < len(left):
arr[k] = left[i]
i += 1
k += 1
while j < len(right):
arr[k] = right[j]
j += 1
k += 1时间复杂度
所有情况：
O(n log n)（稳定高效，不受数据分布影响）。递归深度：
log n层，每层合并操作O(n)。
空间复杂度
额外空间：
O(n)（需临时数组存储合并结果）。递归栈空间：
O(log n)。
稳定性
稳定：合并时优先保留左子数组的元素顺序。
适用场景
需要稳定排序：如数据库、对象排序。
链表排序：归并排序是链表排序的最佳选择（无需随机访问）。
外部排序：处理大规模数据时（如磁盘文件），归并排序可分段加载数据。
3. 快速排序 vs 归并排序对比
4. 如何选择？
优先快排：
数据随机分布 + 内存受限（如普通数组排序）。
优先归并：
需要稳定性 + 数据结构复杂（如链表、对象排序）。
极端情况：
若数据已近乎有序，快排可能退化为
O(n²)，此时可用归并或优化快排基准选择。
一句话总结：
快排：快但不稳，省内存。
归并：稳但费内存，万能但稍慢。