a_day 阅读(296) 评论(0)

前言:

  昨天下午写好了冒泡排序后,紧跟其后,今天跟新上插入排序算法。

插入排序:它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入

情景描述:

  紧接冒泡排序,每次同学们都屡试不爽,但是学生越来越多了,老师发现每次排完队,就耽搁了大半节课时了,说道:“咱不用冒泡了,有点OUT了,今天来插入排序”。这时体育老师担任起了数学老师的职责,又给同学们讲了种排队方式--插入排序。

  1. 开始以第一位同学为基准,由第二个同学开始向前和第一位同学比较,个头高了不动,低了换位
  2. 第三个同学要先和自己前面的第二位同学比较,如果低了,和第二换位,然后再向前和第一比较,低了再换,否则阻断,不再比较
  3. 从前往后依次执行步骤2,依次出来一位同学,每次和自己前面的同学进行比较,找到一个合适位置插入,其余学生后移

合适位置:前一位同学等于或低于自己身高,并且后一位同学高于自己身高

  按照这个方式,同学们一个个依次找准位置,再也不用每次相邻的都比较,而且找到位置后就不必再往前面比较了......


  上图中,深色部分为每次已排完序的列表,红色指引末端为要插入元素,其余枝节为即将与之一一比较的元素。


代码片段:

 

/**
     * 插入排序,默认第一位已经排好序,从第二位开始依次向前比较,确定自己的位置后插入,即前一位小余或等于当前,且后一位大于当前。
     * 插入后,自己新位置后面的元素依次向后移位, 完成一轮插入排序
     * @param arr
     * @return
     */
    public static int[] insertSort(int[] arr) {
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            if (arr[i - 1] > arr[i]) {
                int k = arr[i];
                int j = i;
                while (j > 0 && arr[j - 1] > k) {
                    arr[j] = arr[j - 1];
                    j--;
                }
                arr[j] = k;
            }
        }
        return arr;
    }

 


优点:容易实现,它借助了"逐步扩大成果"的思想,使有序列表的长度逐渐增加。

缺点:稳定性依据元素的值本身而定,且效率不高

                          

                              写作不易,难免有疏漏和错误,还请慷慨指正,不错请推荐

  ps:欢迎转载,转载请注明出处:http://www.cnblogs.com/liuyitian/p/4054437.html


                                       每天多学一点点     代码少敲一点点