时间复杂度:由于希尔排序的时间复杂度依赖于增量序列的函数,时间复杂度分析起来比较困难。当n在某个特定范围内的时候,希尔排序的时间复杂度约为O()。
空间复杂度:O(1)
算法稳定性:不稳定
算法原理:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<d(t-1)<....d2<d1),即所有记录放在同一组中进行直接插入排序为止。
图示:
代码:
public static void shell_sort(int array[]){
int len=array.length;
int step=len>>1;//int step=len/2;
while(step>=1){
for(int i=step;i<len;i++){
for(int j=i;j>=step;j-=step){
if(array[j]<array[j-step]){
swap(array,j,j-step);
}else{
break;//每次内层循环比较一次即可,因为前面已经排好序了
}
}
}
step>>=1;
}
}
private static void swap(int[] array, int i, int j) {
int a=array[i];
array[i]=array[j];
array[j]=a;
}