shell(希尔)排序
程序员文章站
2022-07-08 13:10:28
...
shell排序是一种插入排序算法,它出自D.L.Shell,因此而得名。Shell排序又称作缩小增量排序。Shell排序的执行时间依赖于增量序列。
先取一个增量序列(例如:5,3,1)将一串需排序的数列先按照5分组,每组三个数。对每组三个数进行排序。接下来按照3分组,每组五个数。对每组五个数进行排序。接下来是1 也就是进行直接插入排序。
Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征:
① 最后一个增量必须为1;
② 应该互素。
接下来用图来演示一下shell排序
首先有这么一组数列
1>先分成五组然后进行排序
2>再分成三组进行 排序
接下来通过两次分组排序我们会发现这个数列已经接近与有序
3>这个时候我们再对它进行直接插入排序
java代码实现
public class Test2 {
public static void shellSort(int[] array){
int[] d = {5,3,1};
for(int i = 0;i < d.length;i++){
shell(array,d[i]);
}
}
private static void shell(int[] array, int gap) {
int tmp = 0,j;
for(int i = gap;i < array.length;i++){
tmp = array[i];
for(j = i-gap;j >= 0;j = j-gap){
if(array[j] > tmp){
array[j+gap] = array[j];
}else{
break;
}
}
array[j+gap] = tmp;
}
}
public static void main(String[] args) {
int[] array={4,3,5,6,234,56,2};
shellSort(array);
System.out.println(Arrays.toString(array));
}
}
运行结果
上一篇: 关于Jmeter后端监听器统计TPS的坑
下一篇: 苹果手机原彩显示设置教程分享