是对直接插入排序的一种优化
最小增量数组 由大到小，且为素数，最后一个增量必须为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;
}
