排序算法是数据结构与算法的核心基础，也是日常开发、面试高频考点。本文精简拆解五种常见排序算法，清晰讲解原理、代码、复杂度及适用场景，新手可快速掌握核心要点。
先明确三个核心概念，统一认知：
时间复杂度：描述算法执行时间随数据量增长的趋势，重点关注最坏及平均情况。
空间复杂度：描述算法所需额外空间的趋势，分为原地排序（O(1)）和非原地排序。
稳定性：排序后相同值元素相对位置不变，多条件排序中尤为重要。
一、冒泡排序（Bubble Sort）——入门级排序
1. 核心原理
两两比较相邻元素，将较大元素逐步“冒”到数组末尾，重复操作至全部有序，本质是相邻元素交换。
2. 简洁代码（Python）
def bubble_sort(arr): n = len(arr) for i in range(n-1): for j in range(n-1-i): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr
3. 复杂度与稳定性
时间复杂度：最坏/平均O(n²)，最好O(n)（有序时可优化）；
空间复杂度：O(1)（原地排序）；
稳定性：稳定。
4. 适用场景
数据量极小（n<100）、入门练习，实际开发中极少使用。
二、选择排序（Selection Sort）——简单高效略优于冒泡
1. 核心原理
每次从待排序元素中找到最小（大）值，放到待排序区间开头，重复至有序，减少交换次数。
2. 简洁代码（Python）
def selection_sort(arr): n = len(arr) for i in range(n-1): min_index = i for j in range(i+1, n): if arr[j] < arr[min_index]: min_index = j arr[i], arr[min_index] = arr[min_index], arr[i] return arr
3. 复杂度与稳定性
时间复杂度：最坏/平均/最好均为O(n²)（无法优化）；
空间复杂度：O(1)（原地排序）；
稳定性：不稳定。
4. 适用场景
数据量极小、交换成本高的场景，整体效率较低，不适合大规模数据。
三、插入排序（Insertion Sort）——简单排序中最实用
1. 核心原理
将数组分为已排序和未排序区间，依次将未排序元素插入已排序区间的合适位置，直至有序。
2. 简洁代码（Python）
def insertion_sort(arr): n = len(arr) for i in range(1, n): temp = arr[i] j = i - 1 while j >= 0 and arr[j] > temp: arr[j+1] = arr[j] j -= 1 arr[j+1] = temp return arr
3. 复杂度与稳定性
时间复杂度：最坏/平均O(n²)，最好O(n)（有序时）；
空间复杂度：O(1)（原地排序）；
稳定性：稳定。
4. 适用场景
数据量小（n<1000）、接近有序，或嵌入式系统（空间有限），是简单排序中最实用的一种。
四、快速排序（Quick Sort）——实际开发首选
1. 核心原理
分治法思想：选基准值，将数组分为“小于、等于、大于基准”三部分，递归排序左右子数组，直至有序（随机基准可避免最坏情况）。
2. 简洁代码（Python，随机基准优化）
import random def quick_sort(arr): if len(arr) <= 1: return arr pivot = random.choice(arr) 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 quick_sort(left) + middle + quick_sort(right)
3. 复杂度与稳定性
时间复杂度：平均/最好O(nlogn)，最坏O(n²)（可通过随机基准规避）；
空间复杂度：O(logn)~O(n)（递归栈，非原地）；
稳定性：不稳定。
4. 适用场景
大规模数据排序（n>1000）、数据分布均匀场景，效率极高，是实际开发首选。
五、归并排序（Merge Sort）——稳定高效
1. 核心原理
分治法思想：先将数组递归拆分至单个元素（天然有序），再逐步合并两个有序子数组，直至得到完整有序数组。
2. 简洁代码（Python）
def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): res, i, j = [], 0, 0 while i < len(left) and j < len(right): if left[i] <= right[j]: res.append(left[i]) i += 1 else: res.append(right[j]) j += 1 res.extend(left[i:]) res.extend(right[j:]) return res
3. 复杂度与稳定性
时间复杂度：最坏/平均/最好均为O(nlogn)（稳定）；
空间复杂度：O(n)（非原地，需额外存储）；
稳定性：稳定。
4. 适用场景
大规模数据、要求稳定排序（如多条件排序）、外部排序（数据无法全部放入内存）场景。
六、五种排序算法汇总（面试必背）
七、总结与面试要点
1. 简单排序（冒泡、选择、插入）：O(n²)，适用于小规模数据，重点掌握插入排序；
2. 高效排序（快速、归并）：O(nlogn)，适用于大规模数据，是面试重点；
3. 面试重点：快排与归并的区别（稳定性、空间、场景），快排的优化方法；
4. 实际开发：优先使用语言内置排序（如Python sort()），按需选择排序算法。
