排序算法(Java实现)：Shell排序

欢迎进入Java社区论坛，与200万技术人员互动交流 >>进入

希尔排序，也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。一直较好的增量序列是2^k-1,2^(k-1)-1,…..7,3,1,这样可使Shell排序时间复杂度达到O(N^1.5)。为了方便扩展，先引入一个抽象的基础类：view plainpackage com.andyidea.algorithms;

/*** 排序抽象基础类* @author Andy.Chen** @param <T>*/public abstract class Sorter<T extends Comparable<T>> {

public abstract void sort(T[] array,int from,int len);

public final void sort(T[] array){ sort(array,0,array.length); }

protected final void swap(T[] array,int from,int to){ T tmp = array[from]; array[from] = array[to]; array[to] = tmp; }

}希尔(Shell)排序算法源码如下：view plainpackage com.andyidea.algorithms;

/*** 希尔(Shell)排序算法* @author Administrator** @param <T>*/public class ShellSort<T extends Comparable<T>> extends Sorter<T> {

@Override public void sort(T[] array, int from, int len) { int value =1; while((value+1)*2 < len){ value = (value+1)*2 – 1; }

for(int delta=value;delta<=1;delta=(delta+1)/2-1){ for(int i=0;i<delta;i++){ invokeInsertionSort(array,from,len,delta); } } }

private final void invokeInsertionSort(T[] array,int from,int len,int delta){ if(len<=1) return; T tmp=null; for(int i=from+delta;i<from+len;i+=delta) { tmp=array[i]; int j=i; for(;j>from;j-=delta) { if(tmp.compareTo(array[j-delta])<0) { array[j]=array[j-delta]; } else break; } array[j]=tmp; } }

}