希尔排序也称递减增量排序算法是插入排序的一种高速而稳定的改进版本
希尔排序是基于插入排序的以下两点性质而提出改进方法的
插入排序在对几乎已经排好序的数据操作时 效率高 即可以达到线性排序的效率
但插入排序一般来说是低效的 因为插入排序每次只能将数据移动一位
步长的选择是希尔排序的重要部分只要最终步长为任何步长序列都可以工作算法最开始以一定的步长进行排序然后会继续以一定步长进行排序最终算法以步长为进行排序当步长为时算法变为插入排序这就保证了数据一定会被排序
一直较好的增量序列是^k^(k)这样可使Shell排序时间复杂度达到O(N^)
为了方便扩展先引入一个抽象的基础类
view plain
package comandyideaalgorithms;
/**
* 排序抽象基础类
* @author AndyChen
*
* @param <T>
*/
public abstract class Sorter<T extends Comparable<T>> {
public abstract void sort(T[] arrayint fromint len);
public final void sort(T[] array){
sort(arrayarraylength);
}
protected final void swap(T[] arrayint fromint to){
T tmp = array[from];
array[from] = array[to];
array[to] = tmp;
}
}
希尔(Shell)排序算法源码如下
view plain
package comandyideaalgorithms;
/**
* 希尔(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 =;
while((value+)* < len){
value = (value+)* ;
}
for(int delta=value;delta<=;delta=(delta+)/){
for(int i=;i<delta;i++){
invokeInsertionSort(arrayfromlendelta);
}
}
}
private final void invokeInsertionSort(T[] arrayint fromint lenint delta){
if(len<=)
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(pareTo(array[jdelta])<)
{
array[j]=array[jdelta];
}
else break;
}
array[j]=tmp;
}
}
}
