欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

shell(希尔)排序

程序员文章站 2022-07-08 13:10:28
...

       shell排序是一种插入排序算法,它出自D.L.Shell,因此而得名。Shell排序又称作缩小增量排序。Shell排序的执行时间依赖于增量序列。

先取一个增量序列(例如:5,3,1)将一串需排序的数列先按照5分组,每组三个数。对每组三个数进行排序。接下来按照3分组,每组五个数。对每组五个数进行排序。接下来是1 也就是进行直接插入排序。

Shell排序的执行时间依赖于增量序列。

好的增量序列的共同特征:

① 最后一个增量必须为1;

② 应该互素。

接下来用图来演示一下shell排序

首先有这么一组数列

shell(希尔)排序

1>先分成五组然后进行排序

shell(希尔)排序

2>再分成三组进行 排序

shell(希尔)排序

接下来通过两次分组排序我们会发现这个数列已经接近与有序

3>这个时候我们再对它进行直接插入排序

shell(希尔)排序

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));
	}
}

运行结果

shell(希尔)排序