希尔排序的增量及趟数确定问题

Question

//对顺序表L做一趟希尔插入排序。
//本算法是和一趟直接插入排序相比，做了如下修改：
//1、前后记录位置的增量是dk，而不是1；
//2、r[0]只是暂存单元，不是哨兵。当j<=0时，插入位置已找到。
void ShellInsert(SqList &L, int dk) {
	for(int i=dk+1; i<=L.length; ++i) {
		if(L.r[i].key < L.r[i-dk].key) {//需将 L.r[i] 插入有序增量子表
			L.r[0] = L.r[i];//暂存在 L.r[0]
			int j;
			for(j=i-dk; j>0 && (L.r[0].key < L.r[j].key); j-=dk) {
				L.r[j+dk] = L.r[j];//记录后移，查找插入位置
			}
			L.r[j+dk] = L.r[0];//插入
		}
	}
}
//按增量序列 dlta[0 .. t-1]对顺序表L做希尔排序
//SqList &L  
//int dlta[]  增量序列
//int t		  排序趟数
void ShellSort(SqList &L, int dlta[], int t) {
	for(int k=0; k<t; ++t){
		ShellInsert(L, dlta[k]);//一趟增量为dlta[k]的插入排序
	}
}

希尔排序的增量及趟数怎么确定？怎么调用？有点蒙啊？

Answer 1

参考GPT和自己的思路：

希尔排序的增量及趟数需要根据具体情况来确定，通常采用一些经验公式来计算增量序列，如Hibbard增量序列、Sedgewick增量序列等。同时，趟数也需要根据具体情况进行调整。一般来说，希尔排序的时间复杂度与增量序列有关，有些增量序列可以使得排序时间复杂度接近于O(n log n)。

对于上述代码中的ShellSort函数的调用，需要传入一个SqList类型的顺序表L，以及一个增量序列dlta和排序趟数t的数组，然后通过调用ShellInsert函数对L进行希尔排序，其中ShellInsert函数为对顺序表L进行一趟希尔插入排序的函数。