1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | typedef int Type; void ShellSort(Type * beg, Type * end) { size_t size = end - beg; size_t step = size / 2; while(step > 0) { for(int i = step; i < size; ++i) { Type tmp = *(beg + i); int j = i - step; //~ 索引就不要用size_t了，易错 while(j >= 0 && tmp < *(beg + j)) { *(beg + j + step) = *(beg + j); j -= step; } *(beg + j + step) = tmp; } step = (size_t)step / 2.2; } } |
这个排序算法为什么被命名为Shell排序，我一直幻想着它可能最早被用以Shell脚本吧，Just Now我才知道，发明人叫做Donald Shell，居然有人叫自己壳？
以前从来没有写过这个排序，事实证明，没写过基本等于没听说过、没学过。
21行的小程序花了我将近一个小时来调试，对一个大小为9的逆序用gdb跟踪了程序整个的执行过程，发现两处错误，迭代变量j的类型习惯性地写成了size_t，导致死循环，以后凡是这种i,j,k，一律int。还有就是把最外层的while(step > 0)写成了while(size > 0)，纯属自作自受。
你好！除了代码，此处没有多少原创之物，皆为本人搜集、整理、总结之记录与心得，欢迎转载分享！转载时请尽量注明出处，将不胜感激。祝你健康、快乐！
之前没研究过shell sort，似乎看着有点像insertion sort……
这个复杂度额，似乎不怎么好分析- -
还有那个typedef int Type;
应该是C吧，C++的话通常都是用template
就是增量插入排序
typedef和C还是C++木有关系。