插入排序法

in 算法与数据结构 with 0 comment

插入排序(Insertion Sort)

上一篇记录了选择排序,本篇章记录的是插入排序 插入排序的核心:在一个有序列表中不断插入新的值,放到指定位置 有序列表:开始可以定义列表中arr[0]为有序的 时间复杂度:O(N^2)

分析

1.int[] arr = {1,0,2,4}; 假定arr[0] = 1为有序序列 抽取arr[1] = 0 开始排序,判断大小,比arr[0]小,交换位置(这里从小到大)

得到arr = {0,1,2,4}; 抽取arr[2] = 2 开始排序,判断大小,不需要交换位置 以此类推

插入排序实现

模拟一下每一躺循环的过程

public void insort(){
        //第一趟,如果第二个数比第一个数小,将第一个数后退一个位置(将第二个数插进去)1024
        if (arrays[0] > arrays[1]){
            temp = arrays[1];
            arrays[1] = arrays[0];
            arrays[0] = temp;
        }


        //第二趟拿第3个数和已经排序好的  第12位数比较

        //如果第3位小于第二位数,交换
        if (arrays[2] > arrays[1]){

        }else {
            temp = arrays[2];
            arrays[2] = arrays[1];

            if (temp > arrays[0]) {
                arrays[1] = temp;
            } else {//交换过后在拿第2位和第1位比较
                int insertTemp0 = arrays[0];
                arrays[0] = temp;
                arrays[1] = insertTemp0;
            }
        }


        //第三躺拿第四个数和已经排序好的 第123位比较

        //如果第4位小于第三位数,交换
        if(arrays[3] > arrays[2]){

        }else {

            temp = arrays[3];
            arrays[3] = arrays[2];

            if (temp > arrays[1]) {
                arrays[2] = temp;
            } else {
                int insertTemp1 = arrays[1];
                arrays[1] = temp;
                arrays[2] = insertTemp1;


                if (temp > arrays[0]) {
                    arrays[2] = insertTemp1;
                } else {
                    int insertTemp2 = arrays[0];
                    arrays[0] = temp;
                    arrays[1] = insertTemp2;
                }
            }
        }

        System.out.println(Arrays.toString(arrays));


    }

总结一下

插入排序代码优化

public String insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {//i表示摸到的牌下标
            insertSTemp = arr[i];
            int j = i-1;//j表示已排序好的牌下标

            while (j >= 0 && arr[j] > insertSTemp){//循环摸到的牌和已排序好的进行比较,j是负数说明没牌比较了,arr[j]<temp说明不用交换
                arr[j+1] = arr[j];//摸到的牌和已排序的牌交换
                j--;//继续往前面一张比较
            }
            arr[j+1] = insertSTemp;//比较并且交换完毕后,把摸到的牌放入正确的位置
        }
        return Arrays.toString(arr);
    }

不一定是最好的实现方式,有错误请指出,不胜感激! 插入排序:ShutDown...

0评论