排序----插入排序

数据结构与算法

1.首发

把一个数组分为两个部分，前面是排序的场所，后面是原数组序列。每次从后面部分选出一个数与前面排好序的序列中的数进行比较，要是没有找到合乎条件的就说明这个数没办法插入，要么比前面排好序的序列所有数都大，要么都小。于是不动这个数，直接进行下一轮比较时，这个数被自动插入。

倘如找到了一个合乎条件的情况，那么保存下当前值。保存当前的索引。从这个索引往后的数值被移动。，。，。插入，。，实在是形容不出来了。

public class Solution {
    public int[] insertSort(int[] nums) {
        if(nums==null||nums.length==0){
            return null;
        }
        for (int i = 1; i < nums.length; i++) {
            int p = 0;
            int temp = 0;
            boolean find = false;
            for (int j = 0; j < i; j++) {
                if (nums[i] < nums[j]) {
                    find = true;
                    temp = nums[i];
                    p = j;
                    break;
                }
            }
            if (find == true) {
            //这里移动的时候注意后面往前，。，。有坑
                for (int k = i; k > p; k--) {
                    nums[k] = nums[k - 1];
                }
                nums[p] = temp;
            }
        }
        return nums;
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 2, 55, 6, 3, 2, 4, 5, 6, 8, 9, 0};
        System.out.println(Arrays.toString(solution.insertSort(nums)));
    }
}

2.重构

public class Solution {
    public int[] insertSort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        if (nums.length == 1) {
            return nums;
        }
        for (int i = 1; i < nums.length; i++) {
            int temp = nums[i];
            int j;
            for (j = i - 1; j >= 0; j--) {
            //这里用temp，不能在使用nums[i],有坑
                if (temp < nums[j]) {
                    nums[j + 1] = nums[j];
                } else {
                    break;
                }
            }
            nums[j + 1] = temp;
        }
        return nums;
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 55, 6, 3, 2, 4, 5, 6, 8, 9, 0};
//        int[] nums = {1, 2, 55, 6, 3};
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.insertSort(nums)));
    }
}