排序算法(Java實現)：Shell排序和歸並排序

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

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

• 插入排序在對幾乎已經排好序的數據操作時， 效率高， 即可以達到線性排序的效率
• 但插入排序一般來說是低效的， 因為插入排序每次只能將數據移動一位

步長的選擇是希爾排序的重要部分。只要最終步長為1任何步長序列都可以工作。算法最開始以一定的步長進行排序。然後會繼續以一定步長進行排序，最終算法以步長為1進行排序。當步長為1時，算法變為插入排序，這就保證了數據一定會被排序。
一直較好的增量序列是2^k-1,2^(k-1)-1,.....7,3,1,這樣可使Shell排序時間復雜度達到O(N^1.5)。
為了方便擴展，先引入一個抽象的基礎類：
[html]

1. package com.andyidea.algorithms;  
2.   
3. /**  
4.  * 排序抽象基礎類  
5.  * @author Andy.Chen  
6.  *  
7.  * @param <T>  
8.  */  
9. public abstract class Sorter<T extends Comparable<T>> {  
10.       
11.     public abstract void sort(T[] array,int from,int len);  
12.       
13.     public final void sort(T[] array){  
14.         sort(array,0,array.length);  
15.     }  
16.       
17.     protected final void swap(T[] array,int from,int to){  
18.         T tmp = array[from];  
19.         array[from] = array[to];  
20.         array[to] = tmp;  
21.     }  
22.   
23. }  

希爾(Shell)排序算法源碼如下：
[html]

1. package com.andyidea.algorithms;  
2.   
3. /**  
4.  * 希爾(Shell)排序算法  
5.  * @author Administrator  
6.  *  
7.  * @param <T>  
8.  */  
9. public class ShellSort<T extends Comparable<T>> extends Sorter<T> {  
10.   
11.     @Override  
12.     public void sort(T[] array, int from, int len) {  
13.         int value =1;  
14.         while((value+1)*2 < len){  
15.             value = (value+1)*2 - 1;  
16.         }  
17.           
18.         for(int delta=value;delta<=1;delta=(delta+1)/2-1){  
19.             for(int i=0;i<delta;i++){  
20.                 invokeInsertionSort(array,from,len,delta);  
21.             }  
22.         }  
23.     }  
24.       
25.     private final void invokeInsertionSort(T[] array,int from,int len,int delta){  
26.         if(len<=1)  
27.             return;  
28.          T tmp=null;  
29.          for(int i=from+delta;i<from+len;i+=delta)  
30.          {  
31.              tmp=array[i];  
32.              int j=i;  
33.              for(;j>from;j-=delta)  
34.              {  
35.                  if(tmp.compareTo(array[j-delta])<0)  
36.                  {  
37.                      array[j]=array[j-delta];  
38.                  }  
39.                  else break;  
40.              }  
41.              array[j]=tmp;  
42.          }  
43.     }  
44.   
45. }  

歸並排序，是建立在歸並操作上的一種有效的排序算法。該算法是采用分治法的一個非常典型的應用。也叫歸並算法，指的是將兩個已經排序的序列合並成一個序列的操作。歸並排序算法依賴歸並操作。

算法描述

歸並操作的過程如下：

1. 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列
2. 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
3. 比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置
4. 重復步驟3直到某一指針達到序列尾
5. 將另一序列剩下的所有元素直接復制到合並序列尾

歸並排序算法源碼如下： [html]

1. package com.andyidea.algorithms;  
2.   
3. import java.lang.reflect.Array;  
4.   
5. /**  
6.  * 歸並排序法  
7.  * @author Andy.Chen  
8.  *  
9.  * @param <T>  
10.  */  
11. public class MergeSort<T extends Comparable<T>> extends Sorter<T> {  
12.   
13.     @SuppressWarnings("unchecked")  
14.     @Override  
15.     public void sort(T[] array, int from, int len) {  
16.         if(len<=1)  
17.             return;  
18.         T[] temp = (T[])Array.newInstance(array[0].getClass(), len);  
19.         mergeSort(array, from, from+len-1, temp);  
20.     }  
21.       
22.     /**  
23.      * 分成兩組排序  
24.      * @param array  
25.      * @param from  
26.      * @param to  
27.      * @param temporary  
28.      */  
29.     private final void mergeSort(T[] array,int from,int to,T[] temporary){  
30.         if(to<=from)  
31.             return;  
32.         int middle = (from+to)/2;  
33.         mergeSort(array, from, middle, temporary);  
34.         mergeSort(array, middle+1, to, temporary);  
35.         merge(array, from, to, middle, temporary);  
36.     }  
37.       
38.     /**  
39.      * 把排序好的序列合並  
40.      * @param array  
41.      * @param from  
42.      * @param to  
43.      * @param middle  
44.      * @param temporary  
45.      */  
46.     private final void merge(T[] array,int from,int to,int middle,T[] temporary){  
47.         int k=0;  
48.         int leftIndex=0;  
49.         int rightIndex=to-from;  
50.         System.arraycopy(array, from, temporary, 0, middle-from+1);  
51.         for(int i=0;i<to-middle;i++){  
52.             temporary[to-from-i]=array[middle+i+1];  
53.         }  
54.           
55.         while(k<to-from+1){  
56.             if(temporary[leftIndex].compareTo(temporary[rightIndex])<0)  
57.             {  
58.                 array[k+from]=temporary[leftIndex++];  
59.             }  
60.             else  
61.             {  
62.                 array[k+from]=temporary[rightIndex--];  
63.             }  
64.             k++;  
65.         }  
66.     }  
67.   
68. }