四大经典排序算法:选择、插入、希尔、基数排序原理与实现

选择排序(Selection Sort)通过不断选择剩余元素中的最小值来完成排序。其核心思想是将序列分为已排序和未排序两部分,每次从未排序部分选出最小元素放到已排序末尾。

时间复杂度分析

  • 最优/平均/最坏时间复杂度均为O(n²)
  • 空间复杂度O(1)

Python实现示例

def selection_sort(arr):
n = len(arr)
for i in range(n-1):
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]
return arr
# 测试不同情况
print(selection_sort([64, 25, 12, 22, 11])) # 常规数组
print(selection_sort([5, 1, 2, 2, 3, 4])) # 含重复元素
print(selection_sort([1])) # 单元素

工程实践要点

  1. 适用于内存空间有限场景
  2. 数据交换次数固定为n-1次
  3. 不稳定排序(可通过记录索引改为稳定)

插入排序(Insertion Sort)采用类似整理扑克牌的方式,将每个新元素插入到已排序序列的合适位置。

算法步骤分解

  1. 从第二个元素开始遍历
  2. 将当前元素与前面元素逐个比较
  3. 找到合适位置后插入

性能优化策略

  • 二分查找插入位置(优化比较次数)
  • 链表实现(优化移动次数)
  • 哨兵机制减少边界判断

优化版Python实现

def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
# 二分查找优化
low, high = 0, i-1
while low <= high:
mid = (low + high) // 2
if arr[mid] < key:
low = mid + 1
else:
high = mid - 1
# 移动元素
while j >= low:
arr[j+1] = arr[j]
j -= 1
arr[low] = key
return arr
# 测试大规模数据
import random
test_case = random.sample(range(1, 10000), 500)
assert insertion_sort(test_case) == sorted(test_case)

希尔排序(Shell Sort)是插入排序的改进版,通过分组插入排序实现高效处理。

核心参数选择

  • 增量序列设计(Hibbard、Sedgewick等)
  • 初始步长设置
  • 分组策略优化

Sedgewick增量序列实现

def shell_sort(arr):
n = len(arr)
# Sedgewick增量序列生成
gaps = []
k = 0
while True:
gap = 9*(4**k) - 9*(2**k) + 1
if gap > n:
break
gaps.append(gap)
gap = 4**(k+2) - 3*2**(k+2) + 1
if gap > n:
break
gaps.append(gap)
k += 1
for gap in reversed(gaps):
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
return arr
# 性能对比测试
import timeit
setup = '''
from __main__ import shell_sort, insertion_sort
import random
arr = random.sample(range(1, 100000), 10000)
'''
print("希尔排序耗时:", timeit.timeit('shell_sort(arr.copy())', setup=setup, number=1))
print("插入排序耗时:", timeit.timeit('insertion_sort(arr.copy())', setup=setup, number=1))

基数排序(Radix Sort)按位进行排序,支持稳定高效的数字排序。

关键技术细节

  1. 基数选择(10进制/256进制)
  2. 负数处理(偏移量转换)
  3. 内存使用优化

支持负数的优化实现

def radix_sort(arr):
# 处理负数
min_val = min(arr)
offset = -min_val if min_val < 0 else 0
arr = [num + offset for num in arr]
max_val = max(arr)
exp = 1
while max_val // exp > 0:
counting_sort(arr, exp)
exp *= 10
# 还原原始数据
return [num - offset for num in arr]
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for i in range(n):
index = (arr[i] // exp) % 10
count[index] += 1
for i in range(1, 10):
count[i] += count[i-1]
i = n - 1
while i >= 0:
index = (arr[i] // exp) % 10
output[count[index]-1] = arr[i]
count[index] -= 1
i -= 1
for i in range(n):
arr[i] = output[i]
# 测试含负数的用例
print(radix_sort([-5, 123, 0, 456, -789, 42, -314159]))

实际应用场景

  • 电话号码排序
  • IP地址排序
  • 大规模整数排序
  • 需要稳定排序的场合

从四个维度对算法进行综合评估:

指标 选择排序 插入排序 希尔排序 基数排序
平均时间复杂度 O(n²) O(n²) O(n^1.5) O(nk)
空间复杂度 O(1) O(1) O(1) O(n+k)
稳定性 不稳定 稳定 不稳定 稳定
适用数据规模 小规模 小规模 中等规模 大规模
最佳适用场景 内存敏感 基本有序 通用排序 整数排序

场景选择建议

  1. 内存严格受限时优先选择选择排序
  2. 处理基本有序数据使用插入排序
  3. 通用中等规模数据采用希尔排序
  4. 大规模整数排序首选基数排序
正文到此结束
评论插件初始化中...
Loading...
本文目录