# 



- `[2, 3, 4, 5, 6, 7, 8, 1, ...]` 1 1  2-8  1 
- 
- () 1 1
-  1 

## 


### **Java**

```java
import java.util.Arrays;

public class ShellSort {

    private static int[] shellSort(int[] arr) {
        int n = arr.length;

        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int key = arr[i];
                int j = i;
                while (j >= gap && arr[j - gap] > key) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = key;
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(shellSort(new int[]{1, 2, 7, 9, 5, 8})));
    }
}
```

### **JavaScript**

```js
function shellSort(arr) {
    var len = arr.length;
    var gapSize = Math.floor(len / 2);
    while (gapSize > 0) {
        for (var i = gapSize; i < len; i++) {
            var temp = arr[i];
            var j = i;

            while (j >= gapSize && arr[j - gapSize] > temp) {
                arr[j] = arr[j - gapSize];
                j -= gapSize;
            }
            arr[j] = temp;
        }
        gapSize = Math.floor(gapSize / 2);
    }
    return arr;
}

let arr = [6, 3, 2, 1, 5];
console.log(shellSort(arr));
```

### **Go**

```go
package main

import "fmt"

func shellSort(nums []int) {
	n := len(nums)
	for gap := n / 2; gap > 0; gap /= 2 {
		for i := gap; i < n; i++ {
			j, num := i-gap, nums[i]
			for ; j >= 0 && nums[j] > num; j -= gap {
				nums[j+gap] = nums[j]
			}
			nums[j+gap] = num
		}
	}
}

func main() {
	nums := []int{1, 2, 7, 9, 5, 8}
	shellSort(nums)
	fmt.Println(nums)
}
```


## 



 n  `n^1.25`  `(1.6n)^1.25` 

-  n  n 
-  n  nlogn

O(1)