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

希尔排序算法Java实现

程序员文章站 2024-02-23 09:55:40
...

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

 

相关标签: 算法 Java