希尔排序法 算法

1. 适用范围:

1.1. 优点:

1. 无需额外数组

2. 梗概:

1. 依次对半缩短同组间距
   1. 每隔某个间距为一组
   2. 对每一组都进行插入排序
2. 最后只能分为同一组, 这时排序完成
   1. 最后每隔0为一组, 即包含所有记录

3. 算法动画

4. 在C语言的实现

梗概:

1. 算法的优化: 将遍历每一组和插入排序探针逐步推进结合在一个循环中
   1. 原因: 因为组的数量与组内长度有关系,所以能够结合
   2. 直观理解: 以gap为周期,每个周期内遍历向前推进一格其中一组的探针 代码:

void shell_sort(int arr[], int len) {
	int gap, i, j;
	int temp;
	/*每隔gap格作为一组,知道gap为0,排序完成*/
	for (gap = len >> 1; gap > 0; gap >>= 1)
		/*以gap为周期,每个周期内每步切换到不同的组*/
		/*每个周期内每步向前推进一格该组的插入排序探针*/
		/*将遍历每一组和指针遍历推进结合在一个循环中*/
		/*"i=gap"这个初始化对应插入排序从探测第二个元素开始*/
		for (i = gap; i < len; i++) {
			temp = arr[i];//为组内插入排序的轮换腾出空位
			/*j作为插入排序的探针*/
			/*以下为插入排序的第二个for循环*/
			/*每组中的元素在实际数组中相隔gap格*/
			for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
					arr[j + gap] = arr[j];
			arr[j + gap] = temp;
		}
}