请完成以下验证码
||
今天把希尔排序法看了一下，写个日志，记一下，没事回头再看看，多温习总会有好处
算法原理（来源于网络，主要是为了理解原理^_^）:
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
原始的算法实现在最坏的情况下需要进行O(n2)的比较和交换。V. Pratt的书对算法进行了少量修改，可以使得性能提升至O(nlog2n)。这比最好的比较算法的O(nlogn)要差一些。
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n2)的排序（冒泡排序或插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。
一个更好理解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序（通过增加索引的步长，例如是用i += step_size而不是i++）。
例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：
13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10
然后我们对每列进行排序：
10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45
将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：
10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45
排序之后变为：
10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94
最后以1步长进行排序（此时就是简单的插入排序了）。
下面是用C语言做的实验，编译环境：Dev C++ 4.9.9.2, 编程语言：C
#include <stdio.h>
#include <stdlib.h>
int test_tab[] = {0,4,9,5,7,1,3,9,6,4,5,6,7,7,8,8,1,0,3,2};
void Shell_Sort(int *dat,int len)
{
int i,j,k,t;
int n = 0;
k = len/2;
while(k>0)
{
for(i=k;i<len;i++)
{
t = dat[i];
j = i - k;
while((j>=0)&&(t<dat[j]))
{
dat[j+k] = dat[j];
j = j - k;
n++;
}
dat[j+k] = t;
}
k /= 2;
}
printf("循环的次数是：%d \r\n",n);
}
int main(int argc, char *argv[])
{
int i = 0;
int len = sizeof(test_tab)/sizeof(test_tab[0]);
Shell_Sort(test_tab,sizeof(test_tab)/sizeof(test_tab[0]));
for(i=0;i<len;i++)
printf("%d ",test_tab[i]);
system("PAUSE");
return 0;
}
/////////////////////////////////////////////////////////////////////////////////////////////////
最后，吼一下俺的口号：
每天进步一点点，开心多一点^_^
