前言：希爾排序（shell sort）是插入排序的一種,，它是簡(jiǎn)單插入排序經(jīng)過(guò)改進(jìn)之后的一個(gè)更高效的算法，這個(gè)排序方法又稱(chēng)為縮小增量排序,。

希爾排序思想介紹

簡(jiǎn)單來(lái)說(shuō),，希爾排序是將較大的數(shù)據(jù)集合邏輯上分割成若干個(gè)小的集合，然后對(duì)每個(gè)分組分別進(jìn)行插入排序,。

例如,，假設(shè)待排序元素序列有n個(gè)元素，首先取一個(gè)整數(shù)increment（小于n）作為間隔將全部元素分為increment個(gè)子序列,，在每一個(gè)子序列中分別實(shí)行直接插入排序,。然后縮小間隔increment，重復(fù)上述子序列劃分和排序工作,。直到最后取increment=1,，將所有元素放在同一個(gè)子序列中排序?yàn)橹埂?

算法說(shuō)明：

待排序數(shù)據(jù)：12，1,，6,，7，4,，10,，5，9

第一次的增量為數(shù)組元素的長(zhǎng)度/2，即increment=4,，得到四個(gè)分組：

分組一：12,，             4

分組二：      1，              10

分組三：          6,，                  5

分組四：             7,，                    9

對(duì)這四個(gè)分組分別進(jìn)行插入排序，最終得到：

4,，1,，5，7,，12，10,，6,，9

第二次比較，increment取上次值的一半,，即increment=2,，得到兩個(gè)分組：

分組一：4，  5,，  12,， 6

分組二：    1， 7,，  10,， 9

對(duì)這兩個(gè)分組分別進(jìn)行插入排序，最終得到：

4,， 1,， 5，7,， 6,，9，12,，10

第三次比較,，increment=1，即只有一個(gè)分組：

分組一：4,，1,，5，7,，6,，9，12，10

　　   對(duì)其進(jìn)行插入排序,，最終得到：

1,，4，5,，6,，7，9,，10,，12

希爾排序的代碼實(shí)現(xiàn)

1. public static void shellSort(int[] arr){  

2.     int temp = 0;  

3.     int j = 0;  

4.     //增量初始值是長(zhǎng)度的一半，增量每次變?yōu)樵瓉?lái)的一半  

5.     for(int inc = arr.length/2 ; inc >= 1 ; inc /= 2){  

6.         for(int i = inc ; i < arr.length; i++){  

7.             temp = arr[i];  

8.             //將當(dāng)前數(shù)與減去增量之后位置的數(shù)進(jìn)行比較,，如果大于,，則后移  

9.             for(j = i - inc; j >=0; j -= inc){  

10.                 if(arr[j] > temp){  

11.                     arr[j + inc] = arr[j];  

12.                 }else{  

13.                     break;  

14.                 }  

15.             }  

16.             arr[j + inc]=temp;  

17.         }  

18.     }  

19. }  

總結(jié)

希爾排序是插入排序的改進(jìn)，但是希爾排序中使用到了多次插入排序,，在不同的插入排序過(guò)程中,，相同的元素在各自的插入排序中可能會(huì)移動(dòng)，造成排序的穩(wěn)定性被打亂,，所以希爾排序是不穩(wěn)定的,。