插入排序

package com.company;

import java.util.Arrays;

/**
 * 插入排序
 * 1.默认第一个元素是已经排好序的
 * 2.从第二个元素起，循环放入临沭数据区，并和已经排好序的元素比较，寻找自己的位置
 * 3.找到位置后记录下标，排好序的元素做后移操作
 * 4.最后一个元素会覆盖当前拿出的元素，而要插入数据的位置的元素会有两个
 * 5.此时将临时数据区的元素覆盖插入的位置的数据，完成插入排序
 *
 */

public class InsertSort {
    public static void main(String[] args) {
        System.out.println("============");
        sort(new int[] {1,2,3,5,3});
    }

    public  static  void  sort(int [] arrs) {
        //验证
        if (arrs == null || arrs.length<=1) {
            return;
        }

        int current; //声明当前元素
        //比较
        for (int i = 0 ; i < arrs.length-1 ; i ++ ) {
            //默认第一已经排序了，所以当前操作的元素下标为i+1：current也是临时存储数据区
            current = arrs[i+1];
            // 当前操作的元素前面一个元素的下标
            int preIndex = i; 

            while (preIndex >= 0 && current < arrs[preIndex]){
                //元素下移,将下标为preIndex的元素下移动
                arrs[preIndex+1] = arrs[preIndex];
                //保证从后向前完全遍历比较
                preIndex--;
            }
            arrs[preIndex+1] = current;
        }
        System.out.println(Arrays.toString(arrs));
    }
}