Algorithm: Shell 排序法 （改良的插入排序）

Shell 排序法

插入排序法为从后半部分未排序的取出一个，插入已排序的前半部分的适当位置。但速度不够快。

排序要加快速度，就要让后一次排序进行时，尽量用前一次排序结果，以加快速度······

Shell排序既是基于此方法的改良插入排序法。

Shell‘s Sort 又称 “缩小增量排序”（Diminishing Increment Sort），基本思想：想将整个待排序的记录分割为若干个子序列分别进行插入排序，待整个序列中的记录“基本有序”是，再对全体记录进行一次直接插入排序。

算法实现：

/*****************************************************************
希尔排序（插入排序的该进方法）C语言

*****************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX 10
#define SWAP(x,y){int t;t=x;x=y;y=t;} //这里出错会导致调用地方编译出错

void shellsort(int[]);

int main(void)
{
int number[MAX] = {0};
int i;

srand(time(NULL));

printf("排序前：");
for(i = 0;i<MAX;i++)
{
number[i] = rand()%100;
printf("%d ",number[i]);
}

shellsort(number);

return 0;
}

void shellsort(int number[])
{
int i,j,k,gap,n;
gap = MAX/2; //步长可以自己定义每次的长度，比如不定义好的步长放在一个数组里。这里我定义每次为gap/=2,

while(gap>0)
{
printf("\ngap = %d :",gap);
for(k= 0;k<gap;k++) //相当于逻辑上分为gap组数，进行排序
{
for(i=k+gap;i<MAX;i+=gap) //每个组的循环
{
for(j=i-gap;j>=k;j-=gap) //组内的循环 ***错在了循环上，小小的错误呀！！！让我情何以堪··········
{
if(number[j]>number[j+gap])
{

SWAP(number[j],number[j+gap]);

}

else
break;
}
}
}
gap/=2;

for(i=0;i<MAX;i++)
printf("%d ",number[i]);
printf("\n");

}
}

*******************************************************************************

C++Shell排序
*******************************************************************************

#include<iostream>
using namespace std;
#define LISTSIZE 100
#define ElemType int
typedef struct{
ElemType *elem;
int length;
}SqList;
void InitList(SqList &L) //构造空的线性表
{
L.elem=new int(LISTSIZE+1);
if(!L.elem)
exit(-1);
L.length=0;

}
void CeateList(SqList &L) //建一个线性表
{
int i;
cout<<"请输入表的长度："<<endl;
cin>>i;
L.length=i;
for(int j=1;j<=i;j++)
{
cout<<"请输入第"<<j<<"个元素：";
cin>>L.elem[j];
}
}

void ShellInsert(SqList &L,int dk)
{

for(int i=dk+1;i<=L.length;i++) //这里应该是神马 加一、？
if((L.elem[i]<L.elem[i-dk]))
{
L.elem[0] = L.elem[i];
for(int j=i-dk;j>0&&L.elem[0]<L.elem[j];j-=dk)
L.elem[j+dk]=L.elem[j];
L.elem[j+dk]=L.elem[0];
}
}
void ShellSort(SqList &L,int data [],int t)
{
for(int k=0;k<t;++k)
ShellInsert(L,data[k]);
}
void Shell(SqList &L)
{
int data[3]={5,3,1};

cout<<"此希尔排序分三趟";
ShellSort(L,data,3);
}

void printList(SqList &L) //输出 您的表
{
cout<<"输入的表为："<<endl;
for(int i=1;i<=L.length;i++)
{
cout<<L.elem[i]<<" ";
}
}

int main()
{
SqList A;
InitList(A);
CeateList(A);

Shell(A); //希尔排序
printList(A);
cout<<"\n请输入要查找的元素：";

int j=0;
cin>>j;
cout<<"该元素所在位置为："<<Search(A,j)<<endl;
return 0;
}
*********************************************************************************************

C语言调试结果：