希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序
最后一个增量必须为1才可以， 由于是跳跃式的排序 希尔排序不稳定，时间复杂度为O(N^1.5)
关键在于增量 的选择 我们来通过演示图，更深入的理解一下这个过程。
#include <iostream> #include <cstring> using namespace std; void ShellSort(int *a, int n) { int step = n/2; //先按增量step n/2,n为要排序数的个数进行希尔排序 while(step>=1) { for(int i=step;i<n;i++) { if(a[i]<a[i-step]) { int temp = a[i]; int j=i-step; for(; j>=0 && temp<a[j]; j=j-step) { a[j+step] = a[j]; } a[j+step] = temp; } } step = step/2; } } void InsertSort(int *a, int n) { for(int i=1; i<n;i++) { if(a[i]<a[i-1]) { int temp = a[i]; int j=i-1; for(;j>=0 && temp<a[j];j--) { a[j+1] = a[j]; } a[j+1] = temp; } } } int main() { int a[9] = {9,1,5,8,3,7,4,6,2}; int b = sizeof(a)/sizeof(int); ShellSort(a,9); for(int i=0;i<9;i++) { cout<<a[i]<<" "; } cout<<endl; return 0; } SoWhat1412 认证博客专家 签约作者 后端coder 微信搜索【SoWhat1412】，第一时间阅读原创干货文章。人之患、在好为人师、不实知、谨慎言。点点滴滴、皆是学问、看到了、学到了、便是收获、便是进步。
