希尔排序（最小增量排序）

是对直接插入排序的一种优化

最小增量数组 由大到小，且为素数，最后一个增量必须为1；

原始数据： 1，56，6，33，7，12，45，32，14，42

按增量5组进行排序  1，56，6，33，7，12，45，32，14，42

即（1，12），（56，45），（6，32），（33，14），（7，42）

排序（1，12），（45，56），（6，32），（14，33），（7，42）

得到1，45，6，14，7，12，56，32，33，42

按增量2组进行排序1，45，6，14，7，12，56，32，33，42

即（1，6，7，56，33），（45，14，12，32，42）

排序 （1，6，7，33，56），（12，14，32，42，45）

得到1，12，6，14，7，32，33，42，56，45

按增量1组进行排序1，12，6，14，7，32，33，42，56，45

得到 1，6，7，12，14，32，33，42，45，56

那么有人会问了，这看上去更复杂了呀，怎么说是直接插入排序的优化了呢？

这就和直接插入排序的特点有关了，数据趋近于有序，则排序最快

那么开始写代码扒

void Shell(int *arr,int len,int gap) {
	for (int i = gap; i < len; i++) {
		int temp = arr[i];
		int j;
		for (j = i-gap; j>=0;j=j-gap) {
			if (arr[j] > temp) {
				arr[j+gap] = arr[j];
			}
			else {
				break;
			}
		}
		arr[j + gap] = temp;
	}
}
void Shell_Sort(int *arr,int len) {
	int gap[] = {5,3,1};
	for (int i = 0; i < sizeof(gap) / sizeof(gap[0]);i++) {
		Shell(arr,len,gap[i]);
	}
}
void print(int *arr,int len) {
	for (int i = 0; i < len - 1;i++) {
		cout << "  " << arr[i] << "  ";
	}
}
int main() {
	int arr[] = {1,8,5,4,6,2,7};
	int len = sizeof(arr) / sizeof(arr[0]);
	Shell_Sort(arr,len);
	print(arr,len);
	return 0;
}