希爾排序對於多達數千個資料項的,中等大小規模的數組排序表現良好,希爾排序不像快速排序和其它時間複雜度為O(n*logn)的排序演算法那麼快,因此,對非常大的檔案排序,它不是最優選擇,但是希爾排序比選擇排序和插入排序這種時間複雜度為O(n²)的排序要快的多,並且它非常容易實現,程式碼簡短
希爾排序也是插入排序的一種,在插入排序中,如果最小的數在最後面,則複製的次數太多,而希爾解決了這個問題,它也是n-增量排序,它的思想是透過加大插入排序中元素的間隔,並在這些有間隔的元素中進行插入排序,當這些資料項排過一趟序後,希爾排序演算法會減少資料項的間隔再進行排序,依此進行下去。進行這些排序時資料項之間的間隔稱為增量,並且習慣上以字母h來表示。
對於某個馬上要進行希爾排序的數組,開始的間隔應該更大,然後間隔不段減小,直到間隔變成1.
間隔序列:
間隔序列中的數字素質通常被認為很重要-除了1之外它們沒有公約數,這個約束條件使每趟排序更有可能保持前一趟排序已排好的效果,對於不同的間隔序列,有一個絕對的條件,就是逐漸減少的間隔最後一定要等於1.因此最後一趟是一次普通的插入排序。
下面列出的例子是h=h*3+1的規律得出的:
package com.jll.sort;public class ShellSort { int[] arr; int size; public ShellSort() { super(); } public ShellSort(int size) { this.size = size; arr = new int[size]; } /** * @param args */ public static void main(String[] args) { ShellSort ss = new ShellSort(10); for(int i=0;i<10;i++){ ss.arr[i] = (int) ((Math.random()*100)+1); System.out .print(ss.arr[i]+" "); } ss.shellSort(); System.out.println(); System.out.println("after sort:"); for(int i=0;i<10;i++){ System.out.print(ss.arr[i]+" "); } } public void shellSort(){ int h = 1; while(h<=size /3){ h = h*3+1; } for(;h>0;h=(h-1)/3){ for(int i=h;i<size;i++){ int temp = arr[i]; int j = i; while(j>h-1&&arr[jh]>temp){ arr[j]=arr[jh]; j-=h; } arr[j]=temp; } } } }