排序算法-插入排序（Java实现）

基本思想

通过构建有序数列，对于未排序元素，在已排序数列中从后往前扫描，找到相应位置并插入。

---

简单点~

实现过程

1.将一个具有n个元素的待排序数列分成两个子数列，一个有序和一个无序。
2.刚开始，我们将左边第一个元素看成一个有序数列，右边n-1个元素看成无序数列。
3.从右边无序数列中取出一个元素，在已排序数列中从后往前扫描（比较），找到相应的位置并插入，使插入后有序数列仍然有序。
4.重复第3步，直到完成整个排序过程。

---

过程演示

图片来源网络，侵删

过程演示

---

代码实现

public class InsertSort {
public static void main(String[] args) {
    int[] arr = new int[] {3,5,7,8,9,3,4,52,1,3};
    insertSort(arr);
    System.out.println(Arrays.toString(arr));
}
public static void insertSort(int[] arr) {
    //从i=1 开始，因为单独一个元素arr[0]是有序的；
    for(int i = 1;i < arr.length;i++) {
        //从无序数列中取出一个元素赋值给temp
        int temp = arr[i];
        int t = i-1;
        //不断往前寻找，直到找到比temp小的值或者t小于0为止
        while(t >= 0 && arr[t] > temp) {
            arr[t + 1] = arr[t];
            t--;
        }
        //将temp插在其之后
        arr[t+1] = temp;
        
    }
}

}

---

本篇完，如果有错误的地方欢迎大家指正
不定时发发笔记，欢迎大家来搞~
我的公众号：Java小部落