> For the complete documentation index, see [llms.txt](https://garychang.gitbook.io/data-structure/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://garychang.gitbook.io/data-structure/3-search/3.2-sorting/3.2.4-shell-sort.md).

# 3.2.4 - Shell Sort

### 1. 演算法

比較第$$i$$筆資料與第$$i+$$`span`筆資料，若前者大於後者，則兩者交換。

每一回合(每一個`span`)要做到都沒有發生交換才可以結束。

`span`的型式: $$\[\frac{n}{2^k}]$$ 

```
void Sort(char *arr){
    int n = strlen(arr);
    int span = n/2;
    int flag = 0;
    while(span >= 1){
        while(flag != n-span){ //判斷是否整個回合都沒有swap
            flag = n - span;
            for (int i = 0; i < n-span; i++){
                if (arr[i] > arr[i+span]){  //swap
                    int temp = arr[i];
                    arr[i] = arr[i+span];
                    arr[i+span] = temp;
                    flag--;
                }
            }
        }
        span/=2;
    }
}
```

演算法分析:

$$​input={5,7,8,9,3,1,4,2}$$&#x20;

$$span=\[\frac{n}{2^k}]=\frac{8}{2^1}=4 \quad \Rightarrow {3,1,4,2,5,7,8,9}$$ ，下一回合沒有發生交換，此回合結束。

$$span = \frac{8}{2^2}=2 \quad \Rightarrow {3,1,4,2,5,7,8,9}$$，下一回合沒有發生交換，此回合結束。

$$span = \frac{8}{2^3}=1 \quad \Rightarrow {1,3,2,4,5,7,8,9} \Rightarrow {1,2,3,4,5,7,8,9}$$，下一回合沒有發生交換，此回合結束。

`span`=1，shell sort結束。

### 2.性質

* Time Complexity:&#x20;

  * Avg Case: $$O(n^2)$$&#x20;
  * Worst Case: $$O(n^2)$$&#x20;
  * Best Case: 和`span`的形式有關。 $$O(n^{\frac{3}{2}})$$&#x20;

* Space Complexity: $$O(1)$$&#x20;

Shell sorting is a **unstable** sorting method.