四大经典排序算法:选择、插入、希尔、基数排序原理与实现
选择排序原理与实现
选择排序(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])) # 单元素
工程实践要点:
- 适用于内存空间有限场景
- 数据交换次数固定为n-1次
- 不稳定排序(可通过记录索引改为稳定)
插入排序深度解析
插入排序(Insertion Sort)采用类似整理扑克牌的方式,将每个新元素插入到已排序序列的合适位置。
算法步骤分解:
- 从第二个元素开始遍历
- 将当前元素与前面元素逐个比较
- 找到合适位置后插入
性能优化策略:
- 二分查找插入位置(优化比较次数)
- 链表实现(优化移动次数)
- 哨兵机制减少边界判断
优化版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)按位进行排序,支持稳定高效的数字排序。
关键技术细节:
- 基数选择(10进制/256进制)
- 负数处理(偏移量转换)
- 内存使用优化
支持负数的优化实现:
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) |
稳定性 | 不稳定 | 稳定 | 不稳定 | 稳定 |
适用数据规模 | 小规模 | 小规模 | 中等规模 | 大规模 |
最佳适用场景 | 内存敏感 | 基本有序 | 通用排序 | 整数排序 |
场景选择建议:
- 内存严格受限时优先选择选择排序
- 处理基本有序数据使用插入排序
- 通用中等规模数据采用希尔排序
- 大规模整数排序首选基数排序
正文到此结束
相关文章
热门推荐
评论插件初始化中...
Loading...
微信扫一扫:分享
微信里点“发现”,扫一下
二维码便可将本文分享至朋友圈。