学习之后,自己练习手写一下排序算法,加深印象
原理:将相距某个“增量”的记录组成一个子序列,在各个子序列内分别进行直接插入排序后得到基本有序的结果。所谓基本有序,就是小的关键字在前面,大的基本在后面,不大不小的基本在中间,比如{2,1,3,6,4,7,5,8,9}就可以称为基本有序
#define MAXSIZE 10
#include <stdio.h>
struct a{
int array[MAXSIZE]; //数组用于存储排序数据
int length; //用于存储数组长度信息,
};
void init_array(struct a *L){ //初始化数组
int i;
L->length = MAXSIZE;
for (i=1;i<L->length;i++){ //索引为0的项留作备用
scanf("%d",&(L->array[i]));
}
}
void swap(struct a *L,int i,int j){ //交换数组项
int temp = L->array[i];
L->array[i] = L->array[j];
L->array[j] = temp;
}
void print(struct a *L){ //打印数组项
int i;
for (i=1;i<L->length;i++){
printf("%d ",L->array[i]);
}
}
void ShellSort(struct a *L){ //排序算法
int i,j;
int increment = L->length; //增量初始化为序列的长度
do{
increment = increment/2; //增量减半
for (i=increment+1;i<L->length;i++){ //从第一个序列的第二个数开始,接着是第二个序列的第二个数
if (L->array[i] < L->array[i-increment]){ //如果第二个数比已排好序的序列最后一个数还要小,就执行插入操作
L->array[0] = L->array[i]; //暂存在索引为0的位置
for (j=i-increment;L->array[0] < L->array[j] && j > 0;j-=increment){ //寻找插入位置
L->array[j+increment] = L->array[j]; //依次后移记录位置
}
L->array[j+increment] = L->array[0]; //插入记录
printf("\n");
print(L);
}
}
}while(increment > 1); //当增量为1时,排序完成
}
int main(){
struct a List;
init_array(&List);
printf("排序前:");
print(&List);
ShellSort(&List);
printf("\n排序后:");
print(&List);
return 0;
}
- 可以看到,第一次循环时,增量为5,序列{9,1,5,8,3,7,4,6,2}被划分为{9,7},{1,4},{5,6},{8,2},{3},第一次循环结束后,子序列{9,7}和{8,2}被排序,最终整个序列为{7,1,5,2,3,9,4,6,8}。
- 接着增量减半,变为2,整个序列又被重新划分为{7,5,3,4,8},{1,2,9,6},在第二次循环后变为{3,4,5,7,8},{1.2,6,9}也就是{3,1,4,2,5,6,7,9,8}。
- 最后增量变为1,变成相邻元素之间的交换,排序完成。
算法时间复杂度:O(n3/2),增量的选取至关重要