排序算法是计算机科学中的基础课题，无论是在日常开发还是算法面试中都占据重要地位。本文将通过动态图解和详细代码，带你全面掌握十种经典排序算法。
一、冒泡排序（Bubble Sort）
原理：重复比较相邻元素，将较大元素逐步“冒泡”至右侧。
动态图解：
假设数组 [5,3,8,6,4]
第一轮：
5>3 → 交换 → [3,5,8,6,4]
5<8 → 保持
8>6 → 交换 → [3,5,6,8,4]
8>4 → 交换 → [3,5,6,4,8]
后续轮次继续处理未排序部分。
代码实现（Python）：`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`
二、选择排序（Selection Sort）
原理：每次从未排序部分选择最小元素，放到已排序序列末尾。
代码实现：`python
def selectionsort(arr):
n = len(arr)
for i in range(n-1):
minidx = i
for j in range(i+1, n):
if arr[j] < arr[minidx]:
minidx = j
arr[i], arr[minidx] = arr[minidx], arr[i]
return arr`
三、插入排序（Insertion Sort）
原理：将每个元素插入到已排序序列的适当位置。
动态图解：
初始：[5,3,8,6,4]
第一步：3插入5前 → [3,5,8,6,4]
第二步：8保持 → [3,5,8,6,4]
第三步：6插入5和8之间 → [3,5,6,8,4]
第四步：4插入3和5之间 → [3,4,5,6,8]
代码实现：`python
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`
四、希尔排序（Shell Sort）
原理：改进的插入排序，通过增量分组进行预处理。
代码实现：`python
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`
五、归并排序（Merge Sort）
原理：分治策略，先递归分解数组，再合并有序子序列。
代码实现：`python
def mergesort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = mergesort(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`
六、快速排序（Quick Sort）
原理：选取基准值，将数组分为小于基准和大于基准的两部分，递归排序。
动态图解：
数组 [5,3,8,6,4]，选择基准5：
分区过程：
3<5 → 放左侧
8>5 → 放右侧
6>5 → 放右侧
4<5 → 放左侧
得到 [3,4] 5 [8,6]
递归处理左右子数组。
代码实现：`python
def quicksort(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 quicksort(left) + middle + quick_sort(right)`
七、堆排序（Heap Sort）
原理：构建最大堆，反复取出堆顶元素完成排序。
代码实现：`python
def heapify(arr, n, i):
largest = i
left = 2i + 1
right = 2i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
for i in range(n//2-1, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
return arr`
八、计数排序（Counting Sort）
原理：统计每个元素出现的次数，按统计结果输出有序序列。
代码实现：`python
def countingsort(arr):
if not arr:
return []
maxval = max(arr)
count = [0] (max_val+1)
for num in arr:
count[num] += 1
result = []
for i in range(len(count)):
result.extend([i] count[i])
return result`
九、桶排序（Bucket Sort）
原理：将数据分到有限数量的桶中，每个桶单独排序。
代码实现：`python
def bucketsort(arr, bucketsize=5):
if not arr:
return []
minval, maxval = min(arr), max(arr)
bucketcount = (maxval - minval) // bucketsize + 1
buckets = [[] for in range(bucketcount)]
for num in arr:
buckets[(num - minval) // bucketsize].append(num)
result = []
for bucket in buckets:
result.extend(sorted(bucket))
return result`
十、基数排序（Radix Sort）
原理：按位数从低位到高位依次进行稳定排序。
动态图解：
数组 [170,45,75,90,802,24,2,66]
第一轮按个位排序：
桶0: 170,90
桶2: 802,2
桶4: 24
桶5: 45,75
桶6: 66
得到 [170,90,802,2,24,45,75,66]
第二轮按十位排序...
代码实现：`python
def radixsort(arr):
maxnum = max(arr)
exp = 1
while maxnum // exp > 0:
buckets = [[] for in range(10)]
for num in arr:
buckets[(num // exp) % 10].append(num)
arr = []
for bucket in buckets:
arr.extend(bucket)
exp *= 10
return arr`
算法对比与
| 算法 | 平均时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|------|---------------|------------|--------|----------|
| 冒泡排序 | O(n²) | O(1) | 稳定 | 教学示例，小规模数据 |
| 选择排序 | O(n²) | O(1) | 不稳定 | 简单实现 |
| 插入排序 | O(n²) | O(1) | 稳定 | 小规模或基本有序数据 |
| 希尔排序 | O(n log n) | O(1) | 不稳定 | 中等规模数据 |
| 归并排序 | O(n log n) | O(n) | 稳定 | 大数据量，需要稳定排序 |
| 快速排序 | O(n log n) | O(log n) | 不稳定 | 通用场景，平均性能最优 |
| 堆排序 | O(n log n) | O(1) | 不稳定 | 内存受限场景 |
| 计数排序 | O(n+k) | O(k) | 稳定 | 整数排序，值范围较小 |
| 桶排序 | O(n+k) | O(n+k) | 稳定 | 均匀分布的数据 |
| 基数排序 | O(nk) | O(n+k) | 稳定 | 多关键字排序 |
学习建议
- 理解优先：先理解算法原理，再记忆代码
- 可视化学习：使用排序可视化工具观察算法执行过程
- 动手实现：独立编写每种算法的代码
- 对比分析：通过不同数据集测试算法性能
- 场景选择：根据实际需求选择合适的排序算法
掌握这十种排序算法，不仅能够应对技术面试，更能深入理解算法设计的核心思想。建议读者将代码实际运行，并尝试用不同数据测试，观察排序过程的变化。
