排序演算法：Java實現希爾排序
- 2021 年 10 月 29 日
- 筆記
希爾排序的思路是先分組再整合
先對下標進行分組，比如當數組長度為20時，一開始選定一個間隔值為10
對數組進行排序，每隔10個元素比較大小並交換，以下標為間隔，1和11比較、2和12比較……10和20比較
然後間隔值減半，從10到5，(1,6,11,16)比較、（2,7,12,17）比較…..(5,10,15,20)比較
間隔值逐步減半，再從5到2，從2到1，間隔值為1時也就是整個數組的元素進行排序
因為一開始分組交換時，沒有顧及到不同組之間元素的前後關係，所以這是一個不穩定的排序演算法
程式碼示例
1 public class ShellSortDemo { 2 public static void main(String[] args) { 3 4 5 6 int[] arr = new int[20]; 7 int[] arr1 = new int[arr.length]; 8 for (int i = 0; i < arr.length; i++) { 9 arr[i] = new Random().nextInt() % 1000; 10 arr1[i] = arr[i]; 11 } 12 System.out.println(Arrays.toString(arr)); 13 shellSort(arr); 14 sort(arr1); 15 System.out.println(Arrays.toString(arr)); 16 } 17 18 public static void shellSort(int[] arr){ 19 20 /** 21 * 雖然嵌套了三個循環，但是數據的交換次數並不多 22 */ 23 int second = 0; 24 for (int gap = arr.length/2; gap >= 1 ; gap/=2) { 25 for (int i = gap; i < arr.length; i++) { 26 int j = i; 27 //分組後，每一組先排序前面的，再排序後面的 28 while (j-gap >= 0 && arr[j] < arr[j-gap]){ 29 second++; 30 swap(arr,j,j-gap); 31 j -= gap; 32 } 33 } 34 } 35 System.out.println("希爾排序交換次數："+second); 36 } 37 38 /** 39 * 基本的冒泡排序 40 */ 41 public static void sort(int[] arr){ 42 int second = 0; 43 for (int i = 0; i < arr.length - 1; i++) { 44 for (int j = 0; j < arr.length -1; j++) { 45 if(arr[j] > arr[j+1]){ 46 swap(arr,j,j+1); 47 second++; 48 } 49 } 50 } 51 System.out.println("冒泡排序交換次數："+second); 52 53 } 54 public static void swap(int[] arr,int a,int b){ 55 int tmp = arr[a]; 56 arr[a] = arr[b]; 57 arr[b] = tmp; 58 } 59 }
希爾排序程式碼主要是三個循環和一個判斷，雖然寫了三個循環，但是比較了一下，數據交換次數比冒泡排序少了很多。
