360提示的危险网站,重庆工程建设信息网官网入口,免费自己制作app手机软件,茶业网站设计方案对于这个问题#xff0c;我犹豫了很久。现在鼓起勇气来聊一聊。但是我仍然觉的自己会说不好。这里藏着一些令人惊讶的东西#xff0c;一直沉睡在没有被注意的角落里。
现在不用y_tab解释器。直接用c 语言。
void shellsort(int a[], int n)
{int i,j,t, gapn;for(gap/2;gap…对于这个问题我犹豫了很久。现在鼓起勇气来聊一聊。但是我仍然觉的自己会说不好。这里藏着一些令人惊讶的东西一直沉睡在没有被注意的角落里。
现在不用y_tab解释器。直接用c 语言。
void shellsort(int a[], int n)
{int i,j,t, gapn;for(gap/2;gap0;gap/2) {printag(a, n, gap);for(igap; in; i) {t a[i];ji-gap;while(j0) {if(a[j]t) {a[jgap]a[j];}else {break;}j-gap;}a[jgap]t;
if(i%gapgap-1) printag(a, n, gap);}
if(i%gap!0) printag(a, n, gap);printa(a,n);}
}为了观察运行过程插入了一些打印语句printa()是打印数组。printag()是什么?
void printag(int a[], int n, int gap)
{int i0;int g0;if(gap1) return;printf(-:\n);while(in) {printf(%2d , a[i]);if(ggap) {printf(\n); g0;}}printf(-END\n);
}
每遇到一次gap输出一个换行符的printa()。
这样原来的数组输出为n/gap行, gap列的矩阵。注意这个除法有余数。最后一行会有参差。
大家早已知晓希尔排序最外层循环直接拿掉。里面出现gap的地方直接改为1就变成了直接插入排序。执行的结果也得到一个正确排序的序列。那么把流程故意弄复杂的意图究竟是什么?
说复杂是因为暂时还没有掌握正确读它的方法。等一会儿掌握了就不再复杂而是很清楚了。刚才说到printag()把一个单行的数组输出为 gap列的矩阵。暂时忽略最后一行参差不齐的问题。
好了矩阵有行向量列向量两种分解的方法。现在按列向量来分。列向量是不是比原来的数组短对含有gap个列向量的向量组逐个做排序会怎么样这就是第2层循环 for(igap; in; i) {…这个循环所做的。想象一下对每一个列向量都开一个直接插入排序“线程”每个线程插入完一个数据就轮换给下一个线程。这就是上面循环所做的事情。
然后增量gap要缩小一半。这是最外层的循环。也是说排序好的半gap相邻的列向量要镶嵌合并变成长度增加一倍数目减少一半的又一个矩阵。这个收缩是有限度的gap缩到1就结束了。
而在这个镶嵌变化了的列向量上做排序是有特殊规律的。镶嵌排列的列向量有间隔的排序关系再做一遍插入排序基本上都在就地重排意义上完成而不能穿透。
这个最好直接看运行实例。下面给出16个数据的排序经过 57 13 31 18 19 9 14 71 11 17 69 7 3 2 8 97 END -: 57 13 31 18 19 9 14 71 11 17 69 7 3 2 8 97 -END -: 11 13 31 7 3 2 8 71 57 17 69 18 19 9 14 97 -END 11 13 31 7 3 2 8 71 57 17 69 18 19 9 14 97 END -: 11 13 31 7 3 2 8 71 57 17 69 18 19 9 14 97 -END -: 3 2 8 7 11 13 31 71 57 17 69 18 19 9 14 97 -END -: 3 2 8 7 11 13 31 18 57 17 69 71 19 9 14 97 -END -: 3 2 8 7 11 9 14 18 19 13 31 71 57 17 69 97 -END 3 2 8 7 11 9 14 18 19 13 31 71 57 17 69 97 END -: 3 2 8 7 11 9 14 18 19 13 31 71 57 17 69 97 -END -: 3 2 8 7 11 9 14 18 19 13 31 71 57 17 69 97 -END -: 3 2 8 7 11 9 14 18 19 13 31 71 57 17 69 97 -END -: 3 2 8 7 11 9 14 18 19 13 31 71 57 17 69 97 -END -: 3 2 8 7 11 9 14 13 19 18 31 71 57 17 69 97 -END -: 3 2 8 7 11 9 14 13 19 18 31 71 57 17 69 97 -END -: 3 2 8 7 11 9 14 13 19 17 31 18 57 71 69 97 -END -: 3 2 8 7 11 9 14 13 19 17 31 18 57 71 69 97 -END 3 2 8 7 11 9 14 13 19 17 31 18 57 71 69 97 END 2 3 7 8 9 11 13 14 17 18 19 31 57 69 71 97 END
而列向量的观点用c来表达就是
void shellsort2(int a[], int n)
{class colvec {public:int *a;int n;int m;int col;public:colvec(int *arr, int len, int gap, int icol) {aarr; nlen/gap (len%gapicol); mgap; colicol;}int operator[](int i) { return a[m*icol]; }int length() {return n;}};int i,j,t, gapn;for(gap/2;gap0;gap/2) {for(i0; igap; i) {colvec p(a, n, gap, i);int n p.length();for(j1; jn; j) {int kj;t p[k--];while(k0) {if(p[k]t) {p[k1]p[k];}else {break;}k--;}p[k1]t;}}printa(a,n);}
}
class colvec代表列向量。这里清楚地看到希尔排序内层一字不差的照搬了直接插入排序。
