---
# System prepended metadata

title: 希爾排序法(Shell Sort)

---

# 希爾排序法(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^)