希尔排序中的Hibbard序列
一 定义
Hibbard序列的每个元素由以下公式生成：
h_k = 2^k - 1
其中k从1开始递增，序列为：1, 3, 7, 15, 31, 63, …
二 生成方式
起始条件：k=1，对应h_1=2^1-1=1
递推公式：每次k增加1，计算 h_{k+1}=2^{k+1}-1
示例：前5项为：1, 3, 7, 15, 31
三 在希尔排序中的应用
1 目的
作为希尔排序的步长（间隔序列），用于将数据分为多个子序列进行插入排序。
2 操作步骤
1. 从最大的h_k（小于数组长度n）开始。
2. 按递减顺序使用Hibbard序列中的步长。
3. 对每个步长，执行插入排序。
四 C++ 实现步骤
1 生成Hibbard序列
#include <vector>
using namespace std;
vector<int> generateHibbardSequence(int n) {
vector<int> sequence;
int k = 1;
// 找到最大的k使得2^k -1 < n
while ((1 << k) - 1 < n) { // 1<<k等价于2^k
k++;
}
k--; // 回退到最后一个