希尔排序及希尔排序java代码

原文链接：http://www.orlion.ga/193/

由上图可看到希尔排序先约定一个间隔（图中是4），然后对0、4、8这个三个位置的数据进行插入排序，然后向右移一位对位置1、5、9进行插入排序按照此规律直到全部参与了排序。然后将间隔约定为4-1=3，然后继续进行如上的排序方法。具体过程如下：

9 1 2 3 0 4 5 7 6 8?

Setp 1 经过间隔为4排序后变成 : 0 1 2 3 6 4 5 7 9 8

Setp 2 经过间隔为3排序后变成 : 0 1 2 3 6 4 5 7 9 8

Setp 3 经过间隔为2排序后变成 : 0 1 2 3 5 4 6 7 9 8

Setp 4 经过间隔为1排序后变成 : 0 1 2 3 4 5 6 7 9 8

?

减小间隔：对于大的数组一开始的间隔也应该比较大，而且间隔的缩减幅度也应该变大了，比如对于一个1000大小的数组进行排序可以采用间隔为:364、121、40、13、4、1，这里的间隔序列由knuth提出，数列以逆向的形式从1开始，通过递归表达式h=3*h+1来产生，初始值为1.(其他方法也可以产生序列)如下表

?

下面是希尔排序java代码

public?static?void?shellSort(long[]?arr?,?int?eleNum){
????int?i,j;
????long?temp;
????//?先求出h
????int?h?=?1;
????while(h?<?eleNum?/?3)
	h?=?3?*?h?+?1;?//?1、4
????while?(h?>?0)?{
	for(i?=?h?;?i?<?eleNum?;?i?=?i?+?h)?{
	????//?对子数组进行排序
	????temp?=?arr[i];
	????j?=?i;
	????while(j?>?h-1?&&?temp?<=?arr[j-h])?{
	????????arr[j]?=?arr[j-h];
		j-=h;
	????}
	????????arr[j]?=?temp;
????????}
	h?=?(h-1)/3;
????}
????System.out.println(Arrays.toString(arr));
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!