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)，纯属自作自受。
No Comments Now!
Be the first to comment on this entry.