应用网站建设深圳市网站维护

应用网站建设,深圳市网站维护,兰州市生态建设管理局网站,wordpress版权说明以下是各种排序算法的时间复杂度详细对比#xff1a; 比较排序算法 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(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)· 外排序内存不足归并排序· 需要稳定性归并排序、TimSortPython中的排序实现内置排序# Python的sorted()使用TimSortsorted_listsorted(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²)nlen(arr)foriinrange(n):swappedFalseforjinrange(0,n-i-1):ifarr[j]arr[j1]:arr[j],arr[j1]arr[j1],arr[j]swappedTrueifnotswapped:breakreturnarrdefselection_sort(arr):选择排序 O(n²)nlen(arr)foriinrange(n):min_idxiforjinrange(i1,n):ifarr[j]arr[min_idx]:min_idxj arr[i],arr[min_idx]arr[min_idx],arr[i]returnarrdefinsertion_sort(arr):插入排序 O(n²) - 最好O(n)foriinrange(1,len(arr)):keyarr[i]ji-1whilej0andkeyarr[j]:arr[j1]arr[j]j-1arr[j1]keyreturnarrdefmerge_sort(arr):归并排序 O(n log n)iflen(arr)1:returnarr midlen(arr)//2leftmerge_sort(arr[:mid])rightmerge_sort(arr[mid:])result[]ij0whileilen(left)andjlen(right):ifleft[i]right[j]:result.append(left[i])i1else:result.append(right[j])j1result.extend(left[i:])result.extend(right[j:])returnresultdefheap_sort(arr):堆排序 O(n log n)defheapify(arr,n,i):largesti left2*i1right2*i2ifleftnandarr[left]arr[largest]:largestleftifrightnandarr[right]arr[largest]:largestrightiflargest!i:arr[i],arr[largest]arr[largest],arr[i]heapify(arr,n,largest)nlen(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_valmax(arr)min_valmin(arr)range_sizemax_val-min_val1count[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):idxarr[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:arrrandom.sample(range(size*10),size)forname,funcinalgorithms.items():ifsize5000andnamein[冒泡排序,选择排序,插入排序]:# O(n²)算法太慢跳过results[name].append(None)continuearr_copyarr.copy()starttime.time()func(arr_copy)endtime.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,markero,labelname)plt.xlabel(数据量)plt.ylabel(时间 (秒))plt.title(排序算法性能对比)plt.legend()plt.grid(True)plt.show()# benchmark_algorithms() # 取消注释运行测试这个总结应该能帮助你根据具体情况选择合适的排序算法