插入排序_直接插入

public class 插入排序 {
    public static void main(String[] args) {
        int[] ints = {155, 55, 44, 56, 76, 13, 18, 55};
        int[] ints1 = insertionSort(ints);
        System.out.println(Arrays.toString(ints1));
    }
    public static int[] insertionSort(int[] arr) {
        // 非空判断
        if (arr.length == 0) {
            System.out.println("数组不能为空");
            return arr;
        }
        // 定义两个指针
        int current, pre;
        for (int i = 0; i < arr.length - 1; i++) {
            // current当前值
            current = arr[i + 1];
            // pre指向被比的值
            pre = i;
            // 循环判断current是否比左边的值小，小的话进行位置交换
            while (pre >= 0 && current < arr[pre]) {
                // 进行位置交换，为什么不用i呢，避免指针污染
                arr[pre + 1] = arr[pre];
                // pre-1，指向左边下一个要比的值
                pre--;
            }
            // pre！=i，说明发生了位置变换
            if (pre != i) {
                arr[pre + 1] = current;
            }
        }
        return arr;
    }
}