本文實例講述了java數據結構與算法之希爾排序。分享給大家供大家參考，具體如下：
這里要介紹的是希爾排序（縮小增量排序法）。
希爾排序：通過比較相距一定間隔的元素來工作；各趟比較所用的距離（增量）隨著算法的進行而減小，直到只比較相鄰元素的最后一趟排序為止。是插入排序的一種，是針對直接插入排序算法的改進。
算法思想：先將要排序的序列按某個增量d分成若干個子序列，對每個子序列中全部元素分別進行直接插入排序，然后再用一個較小的增量對它進行分組，在每組中再進行排序。當增量減到1時，整個要排序的數被分成一組，排序完成。注意：增量的取值——一般的初次取序列的一半為增量，以后每次減半，直到增量為1。
算法實現代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
package exp_sort;public class ShellSort { public static void shell(int array[]) { int j; int average; //設置增量的值 for (average = array.length / 2; average > 0; average /= 2) { //步長 for (int i = average; i < array.length; i++) { //子序列進行直接插入排序 int temp = array[i]; for (j = i; j >= average && temp < array[j - average]; j -= average) { array[j] = array[j - average]; } array[j] = temp; } } for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println("\n"); } public static void main(String[] args) { // TODO Auto-generated method stub int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 }; shell(array); }} |
算法分析：該算法是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數很少，速度很快；當元素基本有序了，步長很小，插入排序對于有序的序列效率很高。所以，希爾排序的時間復雜度會比O(n^2)好一些，為O(n^1.5)，排序效率比插入排序高很多。由于多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩定性就會被打亂，所以shell排序是不穩定的。希爾排序沒有快速排序算法快 O(N*(logN))，因此對中等大小規模的數據排序比較適用，對規模非常大的數據排序不是最優選擇。但是比O(N^2)復雜度的算法快得多。并且希爾排序非常容易實現，算法代碼短而簡單。 此外，希爾算法在最壞的情況下和平均情況下執行效率相差不是很多，與此同時快速排序在最壞的情況下執行的效率會非常差。
希望本文所述對大家java程序設計有所幫助。
