# 3. 插入排序

一句话总结：

> 初始时是1个元素（数组的第一个元素）
>
> 然后不断往后面遍历\[1,n]，和前面比他大的元素交换，直到遇到前面更小的停止

python

```python
import Sort

class Solution(Sort):
    def sort(self, nums):
        n = len(nums)
        for i in range(1, n):
            for j in range(i, 0, -1):# 每次从0-i位选择一个地方插入新数据
                if self.less(nums[j], nums[j - 1]):
                    self.swap(nums, j, j - 1)
                else:# 因为前面的都是排序的，当不满足小于时直接停止继续往下选择插入位
                    break


if __name__ == '__main__':
    arr = [5, 1, 8, 7, 10, 6, 9, 5, 20, 3, 0]
    print(arr)
    sort = Solution()
    sort.sort(arr)
    print(arr)
'''
[5, 1, 8, 7, 10, 6, 9, 5, 20, 3, 0]
[0, 1, 3, 5, 5, 6, 7, 8, 9, 10, 20]
'''
```

java

```java
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 Insertion<T extends Comparable<T>> extends Sort<T> {
    @Override
    public void sort(T[] nums) {
        int n=nums.length;
        for(int i=1;i<n;i++){
            for(int j=i;j>0&&less(nums[j],nums[j-1]);j--){
                swap(nums,j,j-1);
            }
        }
    }

    public static void main(String[] args){
        Integer[] arr={
                5,1,8,7,10,6,9,5,20,3,0
        };
        Sort<Integer> sort=new Insertion<>();
        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/3-cha-ru-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.