希尔排序算法Java实现

希尔排序算法是插入排序的一种改进，希尔排序将数组的下标按照一定的增量排序，将一个数组分成几个部分，对其中各个部分都只用使用插入排序的思想，当在当前增量情况下各个部分排序完成，则按照一定规则缩小增量，直至增量为一时，数组就只有一个部分，完成这部分的排序即可完成数组的排序。增量选取无硬性要求，在这里增量选择为3*k+1，即1,4,7,10,13......

 

public class Shell {
	
	public static void shellS(Comparable[] a) {
		int k =0;
		while (3*k < a.length) {  //根据数组长度确定出初始增量值k
			k = 3*k +1;
		}
		
		while(k>=1){        //循环直至最终增量为1
			
			for(int i =k+1;i<a.length;i++){     //插入排序的思想
				for(int j =i;j>k&&less(a[j],a[j-k]);j-=k){
					exch(a,j,j-k);
				}
			}
			
			k = k/3;           //更新k值
		}
	}
	private static void exch(Comparable[] a, int i, int j) {  //交换数组a中第i和j两个元素
		Comparable c =a[i];
		a[i] =a[j];
		a[j] =c;
	}
 
	private static boolean less(Comparable c1, Comparable c2) { //判断c1是否小于c2
		return c1.compareTo(c2)<0;
	}
	
	public static void main(String[] args) {
		Integer[] a ={1,2,3,2,1,6,7,8,5,3,2,5,3,6,3};
		shellS(a);
		for(Integer i:a){
			System.out.println(i);
		}
	}

}

输出结果如下，按升序排列：

1
1
2
2
2
3
3
3
3
5
5
6
6
7
8