希尔排序实现详细（c语言实现）

希尔排序（shell sort）的基本理解是代码上更加复杂的插入排序（insertionSort），对于我们普通的插入排序来说，若是排序对象已有一定的顺序，那插入排序的效率非常高，但是对于顺序非常乱的话，那插入排序将会十分复杂。而希尔排序这是先对数组分组，先对每一小组进行插入排序，交换不相邻的元素，多次局部排序将会使大数组基本有序，最后再进行一次完整的插入排序。

实现希尔排序的第一步我们要进行分组，常见的分组手段有对分法，分组情况可如下：

代码实现

#include<stdio.h>
#include<stdlib.h> //提供malloc函数

int main() {
	int len ;
	scanf("%d", &len);
	int* nums = (int*)malloc(sizeof(int) * len);

	for (int i = 0; i < len; i++) {
		scanf("%d", &nums[i]);
	}

	int gap = len / 2;
	while (gap > 0) { //每完成一次while循环，代表完成了一次分组后的插入排序
		for (int i = 0; i <= gap; i++) {
			
			for (int j = i+gap; j < len; j += gap) { //对间隔为gap的数组成员进行插入排序
				if (nums[j] < nums[j - gap]) {       //对于这一段代码如果没办法很好的理解
					int t = nums[j];                 //可以结合插入排序的代码
					nums[j] = nums[j - gap];
					nums[j - gap] =t;
				}
			}
		}
		gap /= 2;
	}
	
	for (int i = 0; i < len; i++) {
		printf("%d
", nums[i]);
	}
	return 0;
}