排序–希爾排序
- 2019 年 10 月 22 日
- 筆記
圖片轉載於https://www.cnblogs.com/chengxiao/p/6104371.html
1、什麼是希爾排序？
希爾排序也是一種插入排序，他是第一個打破時間複雜度O(n^2）的排序方法，它與插入排序的不同之處在於，它會優先比較距離較遠的元素。希爾排序又叫縮小增量排序。
2、希爾排序的思想：
希爾排序是把元素按下標的一定增量進行分組，對每組使用直接插入排序演算法排序；
隨著增量逐漸減少，當增量減至 1 時，整個文件恰被分成一組，演算法便終止
3、程式碼逐步實現：
排序的元素： int[] arr={8,9,1,7,2,3,5,4,6,0};
3.1 交換法實現
//第一步 for (int i=5;i<arr.length;i++){ //i的初始值為初始增量 10/2=5，分為5組，每組兩個元素 for (int j=i-5;j>=0;j-=5){ //j是距離i為5元素，那麼，0和5一組，6和2一組，以此類推，每組比完之後，回退到上一組重新比較，具體用法看第二輪 if (arr[j+5]<arr[j]){ //比較大小，交換 temp=arr[j]; arr[j]=arr[j+5]; arr[j+5]=temp; } } } System.out.println(Arrays.toString(arr));
//第二次 for (int i=2;i<arr.length;i++){ //這裡的2是上次的5/2=2，所以分為兩組，一組5個 for (int j=i-2;j>=0;j-=2){//距離為2的元素，j-=2是每次比完這一輪重新指向上一分組比較，例如[3,1]和[1,0]兩組，比完[1,0]是[0,1],在和前面比較排序，最後為[0,1,3] if (arr[j+2]<arr[j]){ temp=arr[j]; arr[j]=arr[j+2]; arr[j+2]=temp; } } } System.out.println(Arrays.toString(arr));
//第三次 for (int i=1;i<arr.length;i++){ //i是2/2=1，一共是一組 for (int j=i-1;j>=0;j-=1){ if (arr[j+1]<arr[j]){ temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } } System.out.println(Arrays.toString(arr));
最後把上面的程式碼整合起來：
//匯總（交換法，花費時間長） for (int a=arr.length/2;a>0;a/=2){ //a是增量 for (int i=a;i<arr.length;i++){ for (int j=i-a;j>=0;j-=a){ if (arr[j+a]<arr[j]){ temp=arr[j]; arr[j]=arr[j+a]; arr[j+a]=temp; } } } System.out.println(Arrays.toString(arr));
上面才用交換的方式實現的排序花費時間大，不推薦使用，按照交換的思路繼續，替換成插入法
3.2 插入法實現：
1 //匯總（基於插入，花費時間短） 2 for (int gap=arr.length/2;gap>0;gap/=2){ 3 for (int i=gap;i<arr.length;i++){ 4 int j=i-gap; 5 int temp=arr[i]; 6 while (j>=0 && temp<arr[j]){ 7 arr[j+gap]=arr[j]; 8 j-=gap; 9 } 10 arr[j+gap]=temp; 11 } 12 System.out.println(Arrays.toString(arr)); 13 14 }
從3-10行都是插入法來實現的，可以看出，希爾排序就是對排序的元素進行分組，大大提升了時間
4、時間複雜度
O(n^（1.3—2）)
