1、希爾排序的效能簡介
希爾排序是插入排序的改進型，也因此，它的空間復雜度是O（1），不過有趣的是，希爾排序的平均時間復雜度計與其增量有關，算起來較為復雜，dalao們的研究認為是O[n^(1.3 ~ 2)]之間，
其實相比于快排、歸并、堆排這些平均之間復雜度為O [ nlog(n) ]的線性對數階排序，希爾排序并不占優勢（因為希排有亞二次時間界），但作為第一批突破第二次時間屏障的演算法之一的存在，我jio得還是要重溫一下經典（其實是面試愛考ORZ），
2、本文中的一些定義
2.1——有序區與無序區
在本文中，對于一個任意一個無序的的序列：
如， [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ]
我們把這個序列從邏輯上分為有序區和無序區，并默認在開始排序前，第一個元素為有序區，其余為無序區，
如， [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ] （綠色為有序區，紅色為無序區）
在我們對其逐漸有序化的時候，依次從無序區中取出其第一個元素并插入有序區：
如， [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ] （有序區會增加，無序區會減少，同時無序區第一個元素前的元素必然在有序區）
2.2——按增量（gap）劃分多個序列
一個序列可以按增量（gap）在邏輯上劃分為gap個序列（關于的gap的取值，第一次取序列長度一半，之后再取用gap前要除2）：
如， [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ] gap = 9/2 = 4 ，即在邏輯上分成4組小序列，同一小序列內的、邏輯上相鄰的元素，在序列中的小標差為gap：
如， [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ] 比如紅色小序列應該是[ 5, 7, 3 ],它們在原序列中的小標為0、4、8，相差為gap
3、希爾排序的流程
第一步，在邏輯上按gap將序列劃分為gap個小序列，（第一次時取增量（gap）為序列長度的一半）
如， [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ]
第二步，一個指標從序列的無序區（由各個小序列的無序區組成）由左向右遍歷，遍歷到的元素，將其插入對應小序列的有序區”
如， [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ] 指標最開始指向序列無序區第一個即7，7在第一個小序列里，把它插入第一個小序列的有序區，
如， [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ] 指標+1指向無序區新的第一個元素4，4在第二個小序列里， 把它插入第二個小序列的有序區，
如， [ 5, 4, 9, 8, 7, 6, 1, 2, 3 ] 注意，這里是插入到第二個小序列的有序區，所以4、6換位，然后指標+1，，，，操作同上
第三步，gap/=2后若小于1就結束了，否則回呼第一步，
4、代碼
1 import java.util.Arrays; 2 public class Main { 3 public static void shellSort(int[] arr) { 4 int temp; 5 //控制增量（gap），增量將不斷/2直到小于1，（序列會在邏輯上按gap劃分為gap個小序列） 6 for (int gap = arr.length/2; gap >0; gap/=2) { 7 //遍歷無序區（最開始>=gap的下標都屬于無序區） 8 //變數p_in_unorder始終指向當前序列的無序區的第一個元素的下標 9 for (int p_in_unorder = gap; p_in_unorder < arr.length; p_in_unorder++) { 10 /* 11 *p_in_order是小序列有序區內的下標指標 12 *p_in_unorder - gap 是當前小序列有序區的最后一個 13 *把當前無序區第一個元素插入對應小序列有序區 14 */ 15 for (int p_in_order = p_in_unorder-gap ; p_in_order >= 0 ; p_in_order-=gap) { 16 if(arr[p_in_order]>arr[p_in_order+gap]){ 17 temp = arr[p_in_order]; 18 arr[p_in_order] = arr[p_in_order+gap]; 19 arr[p_in_order+gap] = temp; 20 } 21 } 22 } 23 } 24 } 25 26 public static void main(String[] args) { 27 int[] arr = new int[]{5,6,9,8,7,4,1,2,3}; 28 shellSort(arr); 29 System.out.println(Arrays.toString(arr)); 30 } 31 }
最后，如果小伙伴覺得這篇博文對你有幫助的話，就點個推薦吧
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/6729.html
標籤：其他