# 希爾排序法(Shell Sort)
希爾排序（Shellsort），也稱遞減增量排序演算法，是插入排序的一種更高效的改進版本。
是基於插入排序的以下兩點性質而提出改進方法的：
* 插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序O(n)的效率
* 但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位
## 思路
1. 步長設為陣列長度除以2，且每輪步長都會再除以2，直至以1為步長進行排序。
2. 以步長分割的每組數之間進行直接插入排序。
3. 當以1步長進行排序時即為簡單插入排序。
## 舉例說明
有一組數為 `[13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10]`
為了讓大家比較好理解，第一輪我們先以5步長分割這組數，此時看起來像是這樣的
```
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
```
我們將每一"行"進行直接插入排序
```
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
```
此時串起來應為 [10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45]
第二輪我們以3步長分割
```
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
```
一樣每行進行直接插入排序
```
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
```
此時串起來應為 [10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94]
最後以1步長排序，此時就是簡單插入排序了。
## 應用實例
有一陣列為 `int [] arr = {13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10};`，請從小到大排序，分別使用：
1. Shell Sort時，對有序序列在插入時採用交換法
2. Shell Sort時，對有序序列在插入時採用移動法
並比較這兩種方法之間的速度。
### 交換式
```java=
package Sort;
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
int [] arr = {13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10};
shellsort(arr);
}
public static void shellsort(int [] arr) {
int temp = 0; // 用來保存當前的數值
int step = arr.length /2 ; // 步長為陣列長度除以2
int count = 0; // 用於紀錄做了幾輪排序而已,不重要
while (step >= 1) {
for(int i = step; i < arr.length; i++) {
// 遍歷各組中所有的元素 , 步長為 arr.length/2
for(int j = i - step; j >= 0; j -= step) {
// 如果當前元素大於加上步長後的那個元素,說明需要交換
if(arr[j] > arr[j+step]) {
temp = arr[j];
arr[j] = arr[j+step];
arr[j+step] = temp;
}
}
}
step = step / 2; // 每輪步長再繼續除以2
count++;
System.out.println("第 "+(count)+" 輪希爾排序後為 "+Arrays.toString(arr));
}
}
}
```
output
```java=
第 1 輪希爾排序後為 [13, 14, 45, 27, 73, 25, 39, 10, 65, 23, 94, 33, 82, 25, 59, 94]
第 2 輪希爾排序後為 [13, 14, 39, 10, 65, 23, 45, 27, 73, 25, 59, 33, 82, 25, 94, 94]
第 3 輪希爾排序後為 [13, 10, 39, 14, 45, 23, 59, 25, 65, 25, 73, 27, 82, 33, 94, 94]
第 4 輪希爾排序後為 [10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94]
```
**速度測試**
一樣使用八萬筆數據做測試
```java=
package Sort;
import java.text.SimpleDateFormat;
// import java.util.Arrays;
import java.util.Date;
public class ShellSort {
public static void main(String[] args) {
int arr[] = new int[80000];
for(int i=0; i < 80000; i++) {
arr[i] = (int)(Math.random()*80000);
}
Date date1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String dateStr = simpleDateFormat.format(date1);
System.out.println("排序前時間是 = "+dateStr);
// int [] arr = {13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10};
shellsort(arr);
Date date2 = new Date();
dateStr = simpleDateFormat.format(date2);
System.out.println("排序後時間為 = "+dateStr);
}
public static void shellsort(int [] arr) {
int temp = 0;
int step = arr.length /2 ;
int count = 0;
while (step >= 1) {
for(int i = step; i < arr.length; i++) {
// 遍歷各組中所有的元素 , 步長為 arr.length/2
for(int j = i - step; j >= 0; j -= step) {
// 如果當前元素大於加上步長後的那個元素,說明需要交換
if(arr[j] > arr[j+step]) {
temp = arr[j];
arr[j] = arr[j+step];
arr[j+step] = temp;
}
}
}
step = step / 2;
count++;
// System.out.println("第 "+(count)+" 輪希爾排序後為 "+Arrays.toString(arr));
}
}
}
```
output
```java=
排序前時間是 = 2021-06-09 00:57:14
排序後時間為 = 2021-06-09 00:57:18
```
不知道大家有沒有發現到，同樣八萬筆數據剛剛插入排序法花費 2 秒，而希爾作為改進版插入排序法會花費 4 秒鐘，反而更慢呢？代表說一定是因為這個 **交換** 造成了效能降低，其實並沒有真正用到插入排序法，因為插入排序是移動式的，所以我們需要對其進行優化。
### 移動式
其實就是不要發現一個逆序就交換一個
```java=
public static void shellsort2(int [] arr) {
int temp = 0;
int step = arr.length /2 ;
int count = 0;
int j;
while(step >= 1) {
for(int i = step; i < arr.length; i++) {
j = i;
temp = arr[j];
if(arr[j] < arr[j - step]) {
while(j - step >= 0 && temp < arr[j - step]) {
//移動
arr[j] = arr[j - step];
j -= step;
}
// 當退出while循環,就給temp找到插入的位置
arr[j] = temp;
}
}
step = step / 2;
count++;
System.out.println("第 "+(count)+" 輪希爾排序後為 "+Arrays.toString(arr));
}
}
```
output
```java=
第 1 輪希爾排序後為 [13, 14, 45, 27, 73, 25, 39, 10, 65, 23, 94, 33, 82, 25, 59, 94]
第 2 輪希爾排序後為 [13, 14, 39, 10, 65, 23, 45, 27, 73, 25, 59, 33, 82, 25, 94, 94]
第 3 輪希爾排序後為 [13, 10, 39, 14, 45, 23, 59, 25, 65, 25, 73, 27, 82, 33, 94, 94]
第 4 輪希爾排序後為 [10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94]
```
**速度測試**
```java=
public static void main(String[] args) {
// int [] arr = {13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10};
int arr[] = new int[80000];
for(int i = 0; i < 80000; i++) {
arr[i] = (int)(Math.random() * 80000);
}
Instant startTime = Instant.now();
shellsort2(arr);
Instant endTime = Instant.now();
System.out.println("共耗時：" + Duration.between(startTime, endTime).toMillis() + " 毫秒");
}
```
output
```java=
共耗時：15 毫秒
共耗時：15 毫秒
共耗時：14 毫秒
共耗時：13 毫秒
共耗時：12 毫秒
```
同樣八萬筆亂數資料做希爾排序，交換式需要四秒，而移動式甚至一秒都不需要。
## 時間複雜度
假設今天要對一陣列使用希爾排序法由小到大排序。
### 最佳：O(n)
### 平均：O(n^2^) ~ O(n^1.5^)
依選用的步長而定。
### 最差：O(n^5/4^)
Sign in with Wallet
Connect another wallet