以下是各种排序算法的时间复杂度详细对比：
- 比较排序算法
O(n²) 复杂度算法
算法 平均情况 最好情况 最坏情况 空间复杂度 稳定性 说明
冒泡排序 O(n²) O(n) O(n²) O(1) ✓ 通过相邻元素交换
选择排序 O(n²) O(n²) O(n²) O(1) ✗ 每次选最小/最大值
插入排序 O(n²) O(n) O(n²) O(1) ✓ 适合小规模或基本有序
希尔排序 O(n log n) - O(n²) O(n log n) O(n²) O(1) ✗ 改进的插入排序
梳排序 O(n log n) O(n) O(n²) O(1) ✗ 冒泡排序的改进
O(n log n) 复杂度算法
算法 平均情况 最好情况 最坏情况 空间复杂度 稳定性 说明
快速排序 O(n log n) O(n log n) O(n²) O(log n) ✗ 分治，实际最快
归并排序 O(n log n) O(n log n) O(n log n) O(n) ✓ 稳定，适合外排序
堆排序 O(n log n) O(n log n) O(n log n) O(1) ✗ 原地排序，不稳定
TimSort O(n log n) O(n) O(n log n) O(n) ✓ Python/Java内置
- 非比较排序算法
线性复杂度算法
算法 平均情况 最好情况 最坏情况 空间复杂度 稳定性 适用条件
计数排序 O(n + k) O(n + k) O(n + k) O(k) ✓ k是数值范围
桶排序 O(n + k) O(n) O(n²) O(n + k) ✓ 数据均匀分布
基数排序 O(d·(n + k)) O(d·(n + k)) O(d·(n + k)) O(n + k) ✓ d是最大位数
- 详细分析
快速排序
""" 时间复杂度分析： - 最优情况：每次分区都能均匀划分 T(n) = 2T(n/2) + O(n) = O(n log n) - 最坏情况：每次选到最小或最大值作为枢纽 T(n) = T(n-1) + O(n) = O(n²) - 平均情况：O(n log n) 空间复杂度：递归栈深度 O(log n) """归并排序
""" 时间复杂度分析： - 分治递归：T(n) = 2T(n/2) + O(n) - 用主定理求解：O(n log n) - 稳定且总是 O(n log n) 空间复杂度：需要额外数组 O(n) """堆排序
""" 时间复杂度分析： - 建堆：O(n) - 每次堆调整：O(log n) - 总复杂度：O(n) + n·O(log n) = O(n log n) 空间复杂度：原地排序 O(1) """- 实际性能对比
小规模数据 (n < 50)
插入排序 > 选择排序 ≈ 冒泡排序 > 快速排序原因：插入排序在小数据上常数因子小
中等规模数据 (50 < n < 1000)
快速排序 > 归并排序 > 堆排序 > 希尔排序大规模数据 (n > 10000)
快速排序 > TimSort > 归并排序 > 堆排序特定情况
· 基本有序数据：插入排序 O(n)，TimSort O(n)
· 范围小的整数：计数排序 O(n + k)
· 外排序（内存不足）：归并排序
· 需要稳定性：归并排序、TimSort
- Python中的排序实现
内置排序
# Python的sorted()使用TimSortsorted_list=sorted(data)# O(n log n), 稳定# list.sort()也是TimSortdata.sort()# 原地排序TimSort特点
""" TimSort = 归并排序 + 插入排序 + 优化 1. 将数组分成多个run（有序子序列） 2. 对小的run使用插入排序 3. 使用归并排序合并run 4. 自适应：利用已有顺序 复杂度： - 最好：O(n)（已基本有序） - 平均：O(n log n) - 最坏：O(n log n) - 空间：O(n) """- 各算法代码实现
defbubble_sort(arr):"""冒泡排序 O(n²)"""n=len(arr)foriinrange(n):swapped=Falseforjinrange(0,n-i-1):ifarr[j]>arr[j+1]:arr[j],arr[j+1]=arr[j+1],arr[j]swapped=Trueifnotswapped:breakreturnarrdefselection_sort(arr):"""选择排序 O(n²)"""n=len(arr)foriinrange(n):min_idx=iforjinrange(i+1,n):ifarr[j]<arr[min_idx]:min_idx=j arr[i],arr[min_idx]=arr[min_idx],arr[i]returnarrdefinsertion_sort(arr):"""插入排序 O(n²) - 最好O(n)"""foriinrange(1,len(arr)):key=arr[i]j=i-1whilej>=0andkey<arr[j]:arr[j+1]=arr[j]j-=1arr[j+1]=keyreturnarrdefmerge_sort(arr):"""归并排序 O(n log n)"""iflen(arr)<=1:returnarr mid=len(arr)//2left=merge_sort(arr[:mid])right=merge_sort(arr[mid:])result=[]i=j=0whilei<len(left)andj<len(right):ifleft[i]<=right[j]:result.append(left[i])i+=1else:result.append(right[j])j+=1result.extend(left[i:])result.extend(right[j:])returnresultdefheap_sort(arr):"""堆排序 O(n log n)"""defheapify(arr,n,i):largest=i left=2*i+1right=2*i+2ifleft<nandarr[left]>arr[largest]:largest=leftifright<nandarr[right]>arr[largest]:largest=rightiflargest!=i:arr[i],arr[largest]=arr[largest],arr[i]heapify(arr,n,largest)n=len(arr)# 建堆foriinrange(n//2-1,-1,-1):heapify(arr,n,i)# 一个个取出元素foriinrange(n-1,0,-1):arr[i],arr[0]=arr[0],arr[i]heapify(arr,i,0)returnarrdefcounting_sort(arr):"""计数排序 O(n + k)"""ifnotarr:return[]max_val=max(arr)min_val=min(arr)range_size=max_val-min_val+1count=[0]*range_size output=[0]*len(arr)# 计数fornuminarr:count[num-min_val]+=1# 累加foriinrange(1,range_size):count[i]+=count[i-1]# 输出foriinrange(len(arr)-1,-1,-1):idx=arr[i]-min_val output[count[idx]-1]=arr[i]count[idx]-=1returnoutput- 算法选择指南
根据需求选择：
· 通用排序：快速排序或TimSort
· 需要稳定：归并排序或TimSort
· 原地排序（内存少）：堆排序或快速排序
· 小数据量：插入排序
· 整数，范围小：计数排序
· 数据基本有序：插入排序或TimSort
· 链表结构：归并排序
根据数据特征：
数据特征 | 推荐算法 ----------------------|------------ 随机 | 快速排序 基本有序 | 插入排序/TimSort 范围小的整数 | 计数排序 需要稳定排序 | 归并排序/TimSort 内存受限 | 堆排序 分布式/外排序 | 归并排序- 性能测试示例
importtimeimportrandomimportmatplotlib.pyplotaspltdefbenchmark_algorithms():"""性能基准测试"""algorithms={'冒泡排序':bubble_sort,'选择排序':selection_sort,'插入排序':insertion_sort,'快速排序':quick_sort_simple,'归并排序':merge_sort,'堆排序':heap_sort,}sizes=[100,500,1000,5000,10000]results={name:[]fornameinalgorithms}forsizeinsizes:arr=random.sample(range(size*10),size)forname,funcinalgorithms.items():ifsize>5000andnamein['冒泡排序','选择排序','插入排序']:# O(n²)算法太慢，跳过results[name].append(None)continuearr_copy=arr.copy()start=time.time()func(arr_copy)end=time.time()results[name].append(end-start)# 可视化plt.figure(figsize=(12,6))forname,timesinresults.items():valid_times=[tfortintimesiftisnotNone]valid_sizes=[sizes[i]fori,tinenumerate(times)iftisnotNone]ifvalid_times:plt.plot(valid_sizes,valid_times,marker='o',label=name)plt.xlabel('数据量')plt.ylabel('时间 (秒)')plt.title('排序算法性能对比')plt.legend()plt.grid(True)plt.show()# benchmark_algorithms() # 取消注释运行测试这个总结应该能帮助你根据具体情况选择合适的排序算法！
