插入排序demon

插入排序demon

public class InsertSortDemon {
    //从前往后找
    public static void sort(List<Integer> numbers){
        /**
         * 将数组看为 有序的部分和无序的区间
         * 将无序的区间插入到有序的区间
         * 起始时候 有序区间是第一个数据
         */
        for (int i = 1; i < numbers.size(); i++) {
            for (int j = 0; j < i; j++) {
                int tmp = numbers.get(i);
                if(tmp < numbers.get(j)){
                    numbers.remove(i);
                    numbers.add(j,tmp);
                    break;
                }
            }
        }
    }

    //从后往前找
    public static void sort2(List<Integer> numbers){
        /**
         * 将数组看为 有序的部分和无序的区间
         * 将无序的区间插入到有序的区间
         * 起始时候 有序区间是第一个数据
         */
        for (int i = 1; i < numbers.size(); i++) {
            int j = i - 1;
            int tmp = numbers.get(i);
            for (; j >= 0; j--) {
                if(tmp > numbers.get(j)){
                    break;
                }
            }
            if(j + 1!= i){
                Integer value = numbers.remove(i);
                numbers.add(j+1,value);
            }
        }
    }

    public static void main(String[] args) {
        List<Integer> nums = Lists.newArrayList(1,2,4,6,8,3,5,9,7);
        InsertSortDemon.sort(nums);
        System.out.println(nums);
    }
}

运行结果

[1, 2, 3, 4, 5, 6, 7, 8, 9]

可以看出 插入排序是
原地排序
不需要二外的存储空间，空间复杂度是o(1)
是稳定的排序算法
最好时间复杂度 o(n)
最坏时间复杂度 O(n^2)
平均时间复杂度 O(n^2)