> For the complete documentation index, see [llms.txt](https://jun-wang.gitbook.io/learnjava/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jun-wang.gitbook.io/learnjava/ji-shu-xue-xi/suan-fa/pai-xu-suan-fa/cha-ru-pai-xu.md).

# 插入排序

## 插入排序思路

通过比较和插入

1. 首先对数组的前两个数据进行从小到大的排序
2. 接着将第3个数据与排序好的两个数据进行比较，插入合适的位置
3. 然后，将第4个数据插入已经排好的前3个数据中
4. 不断重复上述的过程，完成排序

**时间复杂度：O(n^2) 最好情况：O(n) 最坏情况：O(n^2)**

**空间复杂度：O(1)**

**稳定性：稳定**

**复杂性：简单**

## Java代码实现

```java
package com.wangjun.arithmetic;

import java.util.Arrays;

/*
 * 插入排序
 */
public class SortInsert {

    public static void main(String[] args) {
        int[] arr = {2,3,7,5,43,8,9,0,3,1};
        SortInsert ss = new SortInsert();
        ss.sortInsert(arr);
        System.out.println(Arrays.toString(arr));
    }

    /*
     插入排序，通过比较和插入：
     1，首先对数组的前两个数据进行从小到大的排序
     2，接着将第3个数据与排序好的两个数据进行比较，插入合适的位置
     3，然后，将第4个数据插入已经排好的前3个数据中
     4，不断重复上述的过程，完成排序
     */
    public void sortInsert(int[] arr) {
        int len = arr.length;
        for(int i = 1; i < len; i++) {
            int tem = arr[i];
            int j = i - 1;
            while(j >= 0 && tem < arr[j]) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = tem;
        }
    }

}
```