- 若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行希尔排序，首次增量为5，写出每步过程及结果。
排序前:[10,7,36,4,8,56,10,11,77,15]
-------增量d=5-------
数组情况:[10,7,36,4,8,56,10,11,77,15]
未排序分组:
第0分组[10,56]
第1分组[7,10]
第2分组[36,11]
第3分组[4,77]
第4分组[8,15]
排序后分组:
第0分组[10,56]
第1分组[7,10]
第2分组[11,36]
第3分组[4,77]
第4分组[8,15]
数组情况:[10,7,11,4,8,56,10,36,77,15]
-------增量d=3-------
数组情况:[10,7,11,4,8,56,10,36,77,15]
未排序分组:
第0分组[10,4,10,15]
第1分组[7,8,36]
第2分组[11,56,77]
排序后分组:
第0分组[4,10,10,15]
第1分组[7,8,36]
第2分组[11,56,77]
数组情况:[4,7,11,10,8,56,10,36,77,15]
-------增量d=1-------
数组情况:[4,7,11,10,8,56,10,36,77,15]
未排序分组:
第0分组[4,7,11,10,8,56,10,36,77,15]
排序后分组:
第0分组[4,7,8,10,10,11,15,36,56,77]
数组情况:[4,7,8,10,10,11,15,36,56,77]
排序后:[4,7,8,10,10,11,15,36,56,77]
#define SHELL_MAX_SIZE 10
/*
定义希尔排序的数据结构
*/
typedef struct{
int data[SHELL_MAX_SIZE];//定义数组
int lenth;//当前数组的长度
}Shell;
/*
希尔排序:执行的时间依赖于增量数组.
增量数组:
1.建议是降序的.会按照增量的数组顺序做每次的插入排序.
2.尽量避免增量序列中的增量为互为倍数情况.
3.最后一个肯定是1,因为最后一次操作是要将整个数组进行排序.
优势在于:按照前面增量进行排序后,有形成阶段范围的有序,减少了比较次数和移动结点次数
shell:待排序数组信息
d[]:增量的数组,会按照增量的数组顺序做每次的插入排序.最后一个元素肯定是1.
dSize:增量数组的长度
*/
void shellSort(Shell shell,int d[],int dSize);
/*
希尔排序中的一次排序
每个分组内使用插入排序进行排序
shell:希尔数据对象
d:增量.分组中元素相差的间距
*/
Shell shellOnceSort(Shell shell,int d);
/*
打印数组中的分组
shell:希尔数据对象
d:增量.分组中元素相差的间距
第0组:[0,0+dk,0+2*dk,0+3*dk,....]
第1组:[1,1+dk,1+2*dk,1+3*dk,....]
第d-1组:[2,2+dk,2+2*dk,2+3*dk,....]
*/
void printShellGroup(Shell shell,int d);
/*
打印Shell数据
*/
void printShell(Shell shell,int start,int end);
/*
希尔排序
shell:待排序数组信息
d[]:增量的数组,会按照增量的数组顺序做每次的插入排序.
dSize:增量数组的长度
*/
void shellSort(Shell shell,int d[],int dSize){
printf("排序前:");
printShell(shell,0,shell.lenth-1);
int i=0;
//遍历增量数组
for(i=0;i<dSize;i++){
//按照增量分组,组内进行排序进行排序
shell= shellOnceSort(shell, d[i]);
}
printf("排序后:");
printShell(shell,0,shell.lenth-1);
}
/*
希尔排序中的一次排序
每个分组内使用插入排序进行排序
shell:希尔数据对象
d:增量.分组中元素相差的间距
*/
Shell shellOnceSort(Shell shell,int d){
//1.按照增量d将待排序数组分成d-1组.0~d-1
//2.开始遍历角标范围:d~shell.length.往每个分组中使用插入排序进行插入.
//默认情况
//第0组:有序:[0] 无序:[0+dk,0+2*dk,0+3*dk,....]
//第1组:有序:[1] 无序:[1+dk,1+2*dk,1+3*dk,....]
//第d-1组:有序:[d-1] 无序:[2+dk,2+2*dk,2+3*dk,....]
printf("-------增量d=%d-------\n",d);
printf("数组情况:");
printShell(shell, 0, shell.lenth-1);
printf("未排序分组:\n");
printShellGroup(shell, d);
int i,j;
int temp;//插入排序用到的临时变量
//3.[d~shell.lenth-1]是无序的,那么就遍历此范围,插入到自己所属的分组中
for(i=d;i<shell.lenth;i++){
//3.1:分组内进行插入排序
if(shell.data[i]<shell.data[i-d]){
temp=shell.data[i];
j=i-d;
//3.2.此时需要找到组内插入的位置
while (j>=0 && temp<shell.data[j]) {
//寻找插入的位置,并且组内进行移动数据
shell.data[j+d]=shell.data[j];
//组内往前查找
j=j-d;
}
//3.3找到了组内插入的位置,将值插入即可
shell.data[j+d]=temp;
}
}
//4.打印当前增量排序后情况
printf("排序后分组:\n");
printShellGroup(shell, d);
printf("数组情况:");
printShell(shell, 0, shell.lenth-1);
return shell;
}
/*
打印分组情况
*/
void printShellGroup(Shell shell,int d){
int i,j;
for(i=0;i<d;i++){
printf("第%d分组[",i);
for(j=i;j<shell.lenth;j+=d){
if(j==i){
printf("%d",shell.data[j]);
}else{
printf(",%d",shell.data[j]);
}
}
printf("]\n");
}
}
/*
打印Shell数据
*/
void printShell(Shell shell,int start,int end){
printf("[");
for(int i=start;i<=end;i++){
if(i==start){
printf("%d",shell.data[i]);
}else{
printf(",%d",shell.data[i]);
}
}
printf("]\n");
}
int main(int argc, const char * argv[])
{
Shell shell={{10,7,36,4,8,56,10,11,77,15},10};
//增量数组
int ds[]={5,3,1};
//希尔排序
shellSort(shell,ds,3);
return 0;
}