插入排序

插入排序思路

通过比较和插入

1. 首先对数组的前两个数据进行从小到大的排序

2. 接着将第3个数据与排序好的两个数据进行比较，插入合适的位置

3. 然后，将第4个数据插入已经排好的前3个数据中

4. 不断重复上述的过程，完成排序

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

空间复杂度：O(1)

稳定性：稳定

复杂性：简单

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;
        }
    }

}