kym*_*lly 6 sorting algorithm math
当将随机数插入排序算法时,1,4,13,40,121 ...((3*n)+ 1)比1,2,4,8,16 ...(2*n)稍微更有效.
为什么是这样？它与线程有什么关系吗？
谢谢.
小智 2
众所周知，希尔排序增量步骤 2^k, 2^(k-1), ..., 1 是最差的步骤之一。例如，您只在最后一步比较奇数位置的元素，而与偶数位置的元素进行比较！
其他步骤似乎是 (3^k -1)/2 （而不是 3n+1），并且不会遇到偶数/奇数问题等问题。这不是一个证明，但我们可能期望它比 2 的幂更好。
如果您正在寻找数学分析，众所周知，希尔排序会给数学家带来困难。
我在塞奇威克的论文中没有找到对你的序列的任何分析。也许高德纳的一本书中有这样的内容。
祝你好运。
顺便说一句，你为什么问线程？