希尔排序(ShellSort)学习（四）

希尔排序(Shell Sort)

基本思想：
　    先取一个小于n的整数d₁作为第一个增量，把文件的全部记录分成d₁个组。所有距离为d_l的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d₂1重复上述的分组和排序，直至所取的增量d_t=1(d_tt-l<…21)，即所有记录放在同一组中进行直接插入排序为止。
    　该方法实质上是一种分组插入方法。 

给定实例的shell排序的排序过程

    　假设待排序文件有10个记录，其关键字分别是：
        49，38，65，97，76，13，27，49，55，04。
    　增量序列的取&＃20540;依次为：
        5，3，1

体会：一个> 或< 符号可能是致命的影响

不太清楚原理最好看看：排序过程如【动画模拟演示】

经过了半天的折腾终于搞定了，下面是我的代码

#include
using namespace std;
void ShellSort(int arr[], int len);
void main()
{
int a[]={49,38,65,97,76,13,27,49,55,04};
ShellSort(a,10);
cout<<"排序完成后"< for (int i=0; i<10; i++)
{
cout< }
system("pause");
}
void ShellSort(int arr[], int len)
{
int j,k,temp;
j = len/2;
for (j; j>= 1; j /=2)//确定增量
{
for (k =j; k {

if (arr[k] {
temp = arr[k];
int s =k-j;
while (arr[s] > temp)
{
arr[s +j] = arr[s];
s-=j;
}
arr[s+j] = temp;

}
}
cout<<"**********"<<"增量"< for (int g=0; g<10; g++)
{
cout< cout<<",";
}
cout<<""< }

}
运行效果如下：