排序算法(Java實現)：Shell排序

　　希爾排序也稱遞減增量排序算法是插入排序的一種高速而穩定的改進版本

　　希爾排序是基於插入排序的以下兩點性質而提出改進方法的

　　插入排序在對幾乎已經排好序的數據操作時 效率高 即可以達到線性排序的效率
但插入排序一般來說是低效的 因為插入排序每次只能將數據移動一位
步長的選擇是希爾排序的重要部分只要最終步長為任何步長序列都可以工作算法最開始以一定的步長進行排序然後會繼續以一定步長進行排序最終算法以步長為進行排序當步長為時算法變為插入排序這就保證了數據一定會被排序
一直較好的增量序列是^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;
         }
    }

　　}

From:http://tw.wingwit.com/Article/program/Java/hx/201311/26576.html