# 4. 希尔排序

一句话总结：

> 不断缩小对比范围：一开始是二分之一步那么远的比，到最后是2，相邻的比
>
> 对比后大小违反的交换
>
> 然后退出while jmp!=0

python

```python
data = [16, 25, 39, 27, 12, 8, 45, 63]

SIZE = len(data)

def show(data):
    for i in range(len(data)):
        print(data[i], end=' ')
    print()

def shell(data, size):
    jmp = size // 2
    while jmp != 0:
        for i in range(jmp, size):
            temp = data[i]
            j = i - jmp
            while j >= 0 and data[j] > temp:
                data[j + jmp] = data[j]
                j = j - jmp
            data[j + jmp] = temp
        jmp = jmp // 2


shell(data, SIZE)
show(data)
```

java

```java
/**
 * 希尔排序
 * 先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，
 * 待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序
 *
 * 对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。
 * 希尔排序的出现就是为了改进插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。
 * 希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。
 *
 *
 */
public abstract class Sort<T extends Comparable<T>> {
    public abstract void sort(T[] nums);

    public boolean less(T v,T w){
        return v.compareTo(w)<0;
    }

    public void swap(T[] a,int i,int j){
        T t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}


public class Shell<T extends Comparable<T>> extends Sort<T> {
    @Override
    public void sort(T[] nums) {
        int n=nums.length;
        int step=1;
        while (step<n/3) step=step*3+1;
        System.out.println(step);
        while(step>=1){
            for(int i=step;i<n;i++){
                for (int j=i;j>=step&&less(nums[j],nums[j-step]);j-=step){
                    swap(nums,j,j-step);
                }
            }
            step=step/3;
        }

    }

    public static void main(String[] args){
        Integer[] arr={
                5,1,8,7,10,6,9,5,20,3,0
        };
        Sort<Integer> sort=new Shell<>();
        sort.sort(arr);
        ArrayUtils.printArray(arr);
    }

}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://im-qianuxn.gitbook.io/pytorch/ji-suan-ji/shua-ti/pai-xu-lei/4-xi-er-pai-xu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.