数据结构面试必问：6大排序算法实战对比（附Python代码）
数据结构面试必问：6大排序算法实战对比（附Python代码）
排序算法是计算机科学中最基础也最常被考察的知识点之一。无论是校招还是社招，几乎所有的技术面试都会涉及排序相关的问题。掌握常见排序算法的原理、实现和适用场景，不仅能帮助你在面试中游刃有余，更能提升日常开发中的编码能力。
本文将深入剖析6种经典排序算法：直接插入排序、希尔排序、冒泡排序、快速排序、选择排序和归并排序。我们会从实际编码角度出发，通过Python代码示例展示每种算法的实现细节，并对比它们的时间复杂度、空间复杂度和稳定性。最后，我们还会讨论如何根据具体场景选择合适的排序算法。
1. 排序算法基础概念
在深入算法之前，我们需要明确几个关键概念：
稳定性：如果排序前后相等元素的相对位置保持不变，则该排序算法是稳定的。这在某些业务场景中非常重要，比如先按年龄排序再按姓名排序时，我们希望相同姓名的记录保持年龄顺序。
时间复杂度：描述算法执行时间随数据规模增长的变化趋势。常见的有O(1)、O(n)、O(nlogn)、O(n²)等。
空间复杂度：描述算法执行过程中所需的额外存储空间。原地排序算法的空间复杂度为O(1)。
内排序与外排序：内排序指所有数据都能放入内存的排序，外排序则涉及磁盘等外部存储。
下面是一个简单的排序算法特性对比表：
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 直接插入 | O(n²) | O(n²) | O(1) | 稳定 |
| 希尔 | O(nlogn) | O(n²) | O(1) | 不稳定 |
| 冒泡 | O(n²) | O(n²) | O(1) | 稳定 |
| 快速 | O(nlogn) | O(n²) | O(logn) | 不稳定 |
| 选择 | O(n²) | O(n²) | O(1) | 不稳定 |
| 归并 | O(nlogn) | O(nlogn) | O(n) | 稳定 |
2. 直接插入排序
直接插入排序的思想类似于我们整理扑克牌的方式：将未排序的元素逐个插入到已排序序列的适当位置。
def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr算法特点：
- 对于几乎有序的数组，性能接近O(n)
- 实现简单，适合小规模数据
- 是稳定排序算法
提示：在面试中，可能会被要求优化插入排序，比如使用二分查找来定位插入位置（二分插入排序），这可以将比较次数从O(n²)降到O(nlogn)，但移动次数仍然是O(n²)。
3. 希尔排序
希尔排序是插入排序的改进版，通过将原始数组分割成若干子序列进行插入排序，逐步缩小子序列的间隔，最终完成整体排序。
def shell_sort(arr): n = len(arr) gap = n // 2 while gap > 0: for i in range(gap, n): temp = arr[i] j = i while j >= gap and arr[j - gap] > temp: arr[j] = arr[j - gap] j -= gap arr[j] = temp gap //= 2 return arr算法特点：
- 时间复杂度取决于间隔序列的选择
- 是不稳定排序算法
- 相比直接插入排序，更适合中等规模的数据
4. 冒泡排序
冒泡排序通过重复地遍历列表，比较相邻元素并交换它们的位置来完成排序。
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 return arr优化技巧：
- 添加
swapped标志位，当某一轮没有发生交换时提前终止 - 记录最后一次交换的位置，减少下一轮的比较范围
5. 快速排序
快速排序采用分治策略，选择一个基准元素将数组分成两部分，一部分小于基准，一部分大于基准，然后递归地对子数组排序。
def quick_sort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] 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)面试常见问题：
- 如何选择基准元素？（首元素、中间元素、随机元素、三数取中等）
- 如何处理大量重复元素？（三路快速排序）
- 如何优化递归深度？（尾递归优化或使用栈实现迭代版本）
6. 选择排序
选择排序每次从未排序部分选择最小（或最大）元素放到已排序部分的末尾。
def selection_sort(arr): for i in range(len(arr)): min_idx = i for j in range(i+1, len(arr)): if arr[j] < arr[min_idx]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr算法特点：
- 交换次数最少（最多n-1次）
- 无论输入数据如何，比较次数固定为O(n²)
- 是不稳定排序算法
7. 归并排序
归并排序也是采用分治策略，将数组分成两半分别排序，然后合并两个有序数组。
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): result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] < right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result应用场景：
- 需要稳定排序的大规模数据
- 外部排序（数据无法全部装入内存）
- 链表排序（归并排序是链表排序的最佳选择）
8. 如何选择合适的排序算法
在实际应用中，选择排序算法需要考虑多个因素：
数据规模：
- 小规模数据（n < 100）：插入排序、选择排序
- 中等规模数据：希尔排序
- 大规模数据：快速排序、归并排序
数据特性：
- 几乎有序的数据：插入排序
- 大量重复元素：三路快速排序
- 数据范围有限：计数排序、桶排序等非比较排序
环境限制：
- 内存紧张：原地排序算法（快速排序、堆排序）
- 需要稳定性：归并排序、插入排序
语言内置实现：
- Python的
sorted()使用Timsort（归并和插入的混合） - Java的
Arrays.sort()对原始类型使用快速排序，对象使用归并排序
- Python的
在面试中，除了写出算法实现，面试官更希望听到你选择某种算法的理由和对其特性的理解。例如，当被问到"为什么Python的sorted()不使用快速排序？"，你可以回答："因为Timsort在最坏情况下仍能保持O(nlogn)的时间复杂度，而且是稳定排序，适合Python这种动态类型语言处理各种复杂比较场景。"