排序算法(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;
3. /**
4. * 排序抽象基礎類
5. * @author Andy.Chen
6. *
7. * @param <T>
8. */
9. public abstract class Sorter<T extends Comparable<T>> {
11. public abstract void sort(T[] array,int from,int len);
13. public final void sort(T[] array){
14. sort(array,0,array.length);
15. }
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. }
23. }

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

1. package com.andyidea.algorithms;
3. /**
4. * 希爾(Shell)排序算法
5. * @author Administrator
6. *
7. * @param <T>
8. */
9. public class ShellSort<T extends Comparable<T>> extends Sorter<T> {
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. }
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. }
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. }
45. }

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

算法描述

歸並操作的過程如下：

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

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

1. package com.andyidea.algorithms;
3. import java.lang.reflect.Array;
5. /**
6. * 歸並排序法
7. * @author Andy.Chen
8. *
9. * @param <T>
10. */
11. public class MergeSort<T extends Comparable<T>> extends Sorter<T> {
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. }
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. }
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. }
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. }
68. }