希尔排序（基于逐趟缩小增量）

基本思想

• 先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
  

算法实现

void ShellSort(SqList &L, int dlta[], int t){
	// 按增量序列dlta[0…t-1]对顺序表L作Shell排序
	for(k = 0; k < t; k++)
		ShellInsert(L, dlta[k]);  // 增量为dlta[k]的一趟插入排序

}

void ShellInsert(SqList &L, int dk){
	// 对顺序表L进行一趟增量为dk的Shell排序，dk为步长因子
	for(i = dk + 1; i <= L.length; i++){
		// 开始将r[i] 插入有序增量子表
		if(r[i].key < r[i - dk].key){ r[0] = r[i];  // 暂存在r[0] for(j = i - dk; j > 0 && (r[0].key < r[j].key); j = j - dk) r[j + dk] = r[j];  // 关键字较大的记录在子表中后移 r[j + dk] = r[0];  // 在本趟结束时将r[i]插入到正确位置
		}
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

算法分析

• 时间复杂度： O（n3/2）
• 空间复杂度为 O(1)
• 稳定性： 不稳定

如何选择最佳的序列，目前尚未解决
最后一个增量值必须为1，无除1以外的公因子
不宜在链式存储结构上实现

文章来源: ruochen.blog.csdn.net，作者：若尘，版权归原作者所有，如需转载，请联系作者。

原文链接：ruochen.blog.csdn.net/article/details/103802725