湖南网站推广建设公司自己怎么做游戏推广赚钱

湖南网站推广建设公司,自己怎么做游戏推广赚钱,qq企业邮箱怎么开通注册,会展设计是什么一、希尔排序 算法逻辑 希尔排序采用“增量分组插入排序”的策略。初始时设定一个增量#xff08;通常为数组长度的一半#xff09;#xff0c;将相隔该增量的元素组成一个子序列#xff0c;对每个子序列进行直接插入排序#xff1b;然后逐步缩小增量#xff08;如每次除…一、希尔排序算法逻辑希尔排序采用“增量分组插入排序”的策略。初始时设定一个增量通常为数组长度的一半将相隔该增量的元素组成一个子序列对每个子序列进行直接插入排序然后逐步缩小增量如每次除以2重复分组和排序过程直到增量减为1最后进行一次直接插入排序完成整体有序。代码实现中外层循环控制增量变化从n//2逐渐减至1内层循环对每个子序列执行插入排序操作。由于前期通过较大增量快速调整元素位置避免了小元素远距离移动提高了效率。defshell_sort(arr):nlen(arr)gapn//2# 初始增量whilegap0:foriinrange(gap,n):temparr[i]ji# 对相隔gap的元素进行插入排序whilejgapandarr[j-gap]temp:arr[j]arr[j-gap]j-gap arr[j]temp gap//2# 缩小增量returnarr算法特性稳定性不稳定。因为相同元素可能被分在不同子序列中排序后相对位置可能发生改变。时间复杂度取决于增量序列的选择常见情形下约为 $ O(n^{1.3}) $最坏可达 $ O(n^2) $但平均性能优于直接插入排序。空间复杂度$ O(1) $仅使用常数个辅助变量。二、快速排序基本思想基于分治法选择一个基准元素枢轴 pivot将序列划分为两个子序列——左子序列所有元素 ≤ pivot右子序列所有元素 ≥ pivot再递归地对左右两部分进行快排最终使整个序列有序。划分过程Partition详解以data[low]作为 pivot设置两个指针i low从左向右找大于 pivot 的元素j high从右向左找小于 pivot 的元素步骤如下将 pivot 暂存为temp data[low]当i j时循环j向前移动直到找到第一个 temp的元素将其赋值给data[i]i向后移动直到找到第一个 temp的元素将其赋值给data[j]直到i j此时将temp放入data[i]pivot 归位defpartition(arr,low,high):pivotarr[low]i,jlow,highwhileij:whileijandarr[j]pivot:j-1ifij:arr[i]arr[j]whileijandarr[i]pivot:i1ifij:arr[j]arr[i]arr[i]pivotreturnidefquick_sort(arr,low,high):iflowhigh:pipartition(arr,low,high)quick_sort(arr,low,pi-1)quick_sort(arr,pi1,high)算法特性稳定性不稳定交换过程中相同元素顺序可能被打乱时间复杂度平均 $ O(n \log n) $最坏 $ O(n^2) $已有序时退化空间复杂度$ O(\log n) $递归调用栈深度希尔排序的性能在很大程度上依赖于所采用的增量序列gap sequence。不同的增量序列会显著影响排序的比较和移动次数从而改变其实际运行效率。一、常见的增量序列Shell 原始序列最原始增量公式$ d_k \left\lfloor \frac{n}{2^k} \right\rfloor $每次除以 2示例n88 → 4 → 2 → 1特点简单直观但性能一般最坏时间复杂度为 $ O(n^2) $Knuth 序列增量公式$ d_k \frac{3^k - 1}{2} $从大到小取不超过 n 的值示例1, 4, 13, 40, 121, …实际使用时逆序应用如对长度为100的数组用 40 → 13 → 4 → 1时间复杂度约为 $ O(n^{1.5}) $是较优的选择之一被广泛推荐Hibbard 序列增量公式$ 2^k - 1 $即 1, 3, 7, 15, 31, …可证明最坏情况时间复杂度为 $ O(n^{3/2}) $对某些数据分布表现良好Sedgewick 序列定义复杂形式为1, 5, 9, 17, 29, 77, … 有多种构造方式例如$ { \max(2^i \cdot 3^j) n } $ 或特定公式生成经实验验证具有非常好的平均性能时间复杂度接近 $ O(n^{4/3}) $被认为是实践中最优的增量序列之一Ciura 序列经验序列预定义的经验值1, 4, 10, 23, 57, 132, 301, 701, …不基于数学公式而是通过大量实验优化得出在实际应用中表现极佳常用于现代实现中二、不同增量序列对性能的影响增量序列最坏时间复杂度平均性能说明Shell 原始÷2$ O(n^2) $较差当相邻元素分布在不同组时效率低易退化Knuth$ O(n^{1.5}) $中等偏上结构合理适合教学与一般用途Hibbard$ O(n^{3/2}) $较好理论保障较好避免部分退化情况Sedgewick$ O(n^{4/3}) $很好实验性能优秀适合高性能需求场景Ciura经验未知但非常快极佳当前公认最快的实用序列⚠️ 注意所有增量序列都必须保证最后一个增量为 1以确保最终进行一次完整的插入排序使数组完全有序。三、代码示例使用 Knuth 序列defshell_sort_knuth(arr):nlen(arr)# 生成 Knuth 增量序列(3^k - 1)/2 ngap1while(3*gap1)n:gap3*gap1# 得到最大的小于 n 的 Knuth 数whilegap1:foriinrange(gap,n):temparr[i]jiwhilejgapandarr[j-gap]temp:arr[j]arr[j-gap]j-gap arr[j]temp gap//3# 回退到前一个 Knuth 数returnarr总结增量序列决定了希尔排序的分组策略更科学的序列如 Ciura、Sedgewick能大幅提高效率教学中常用 Shell 原始序列或 Knuth 序列实际工程中建议使用 Ciura 等经验序列以获得最佳性能。