希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。
需要基础点的,大家可以看我的上一篇算法 ,直接插入排序算法。
源码:
template <class T> int getSize(T& array) { return (sizeof(array)/sizeof(array[0])); } int main(int argc,char *argv[]) { int input[] {10,12,11,2,5,78,34,64,46,32}; int group[] {5,2,1}; int iSize = getSize(input); int gSize = getSize(group); int span,temp,j; for(int m = 0;m < gSize;m++) { span = group[m]; for(int k=0;k<span;k++) { //间隔增量 for(int i = k; i<iSize-span;i = i+span) { temp = input[i+span]; j = i; while( j>-1 && temp < input[j]) { input[j+span] = input[j]; j = j-span; } input[j+span] = temp; } } } cout<<"iSize: "<<iSize<<"\ngSize: "<<gSize<<endl; for(auto iter = begin(input); iter!=end(input); iter++) { cout<<" "<<*iter<<" "; } return 0; }
内部算法和直接插入算法是一样的,只是外层增量,从之前的+1 ,变成+间隔大小。
优化算法:
void swap(int &a,int &b) { int temp; temp = a; a = b; b = temp; } template <class T> int getSize(T& array) { return (sizeof(array)/sizeof(array[0])); } int main(int argc,char *argv[]) { int i,j,gap; int a[]{10,12,11,2,5,78,34,64,46,32}; int n = getSize(a); for (gap = n / 2; gap > 0; gap /= 2) for (i = gap; i < n; i++) for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap) swap(a[j], a[j + gap]); for(auto iter = begin(a); iter!=end(a); iter++) { cout<<" "<<*iter; } return 0; }
分析:理解好,将数组进行分组概念就好,之后对比方式和直接插入算法都是一样的。
© 版权声明
文章版权归作者所有,未经允许请勿转载。
THE END
喜欢就支持一下吧