【插入排序算法】初学算法之排序--直接插入排序-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

【插入排序算法】初学算法之排序--直接插入排序

简介: 前言:   厚厚一本《算法第四版》,看到五分之一就已经收益良多,而前五分之一又大部分是关于排序,有冒泡排序、快速排序、堆排序、直接插入排序、希尔排序等等,理解起来也不算特别的难,今天就跟大家分享其中的一种 —— 直接插入排序算法,这里我实现了javascript和java两个语言版本。

前言:

  厚厚一本《算法第四版》,看到五分之一就已经收益良多,而前五分之一又大部分是关于排序,有冒泡排序、快速排序、堆排序、直接插入排序、希尔排序等等,理解起来也不算特别的难,今天就跟大家分享其中的一种 —— 直接插入排序算法,这里我实现了javascript和java两个语言版本。

 

思路:

  在生活中,如果我们要对扑克牌按大小排序,我们会怎么排呢? 

    ① 首先找出一张牌 放在桌子上

    ② 拿出第二张牌,比第一张小就放上面,比第一张大就放下面

    ③ 拿出第三张牌,比第一张小就放上面,比第一张大就和第二张对比 ,比第二张小放上面,比第二长大再和下一张对比......

    ④ 重复步骤 最终扑克牌排序就完成了

  从这三个步骤我们可以得出一些结论

    ① 放在桌子上的牌,总是有序的。

    ② 拿出的牌与前一张对比 直到遇到比那张小的 就放在上面 

实现:

  直接插入排序要点 : 每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。

更清楚一点说: 将当前排序的数组元素,放到前面已经有序的元素的适当位置,循环到全部有序为止;

   javascript实现:

      

function insertSort(arr){
                for(var i = 1;i<arr.length;i++){
                    var temp = arr[i];  //待排序元素
                    var j = i;
                    while(j>0){   
                        if( temp < arr[j-1] ){ //如果前一个数比它自己大 
                            var a = arr[j-1];                //交换它和它前一个元素
                                arr[j-1] = arr[j];
                                arr[j] = a;            
                                j--;        //交换了j  j的位置--
                        }else{
                            j=0; //当找到比它小的数 则结束这次排序 
                        }
                    }
                }
                return arr;
            }

当输入 数组 [6,1,2,7,9,3,4,5,10,8,8,9] 时,得到的结果是 [1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10]

再分析一下while中的步骤:

  

function insertSort(arr){
               //arr = [6,1,2,7,9,3,4,5,10,8,8,9]
                for(var i = 1;i<arr.length;i++){
                    var temp = arr[i];  // 例如i=1的话  temp = arr[1];
                    var j = i;                
                    while(j>0){   
                        if( temp < arr[j-1] ){ // 1 < 6  等于 true
                            var a = arr[j-1];                
                                arr[j-1] = arr[j];
                                arr[j] = a;            //交换1 - 6
                                j--;        //i--  i=0 结束本次循环  这时候 arr = [1,6,2,7....] 再找到2 依次循环 
                        }else{
                            j=0; 
                        }
                    }
                }
                return arr;
            }

java的实现:

  

public class SortUtil {
    //直接插入排序算法
    public static void sort(Comparable[] a){
        for(int i=1;i<a.length;i++){
            Comparable tem = a[i];  //待排序元素
            int j = i;
            
            while(j>0){
                if(less(tem,a[j-1])){  //less比较元素 tem比前一个小的话 
                    exch(a,j,j-1);
                    j--;
                }else{
                    j=0;
                }
            }
        }
    }
   /*
     * compareTo 比较方法
     * @param {Comparable} v 如果v小于w  返回true
     * @param {Comparable} w 如果v大于等于w  返回false
     * @return {boolean} 返回比较的值
     *      * */
    public static boolean less(Comparable v,Comparable w){
        return v.compareTo(w) < 0;
    }
    /*
     * compareTo 交换元素
     * @param {Comparable[]} a 要交换的可排序数组
     * @param {int} i 交换1下标
     * @param {int} j 交换2下标
     *      * */
    public static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    public static void show(Comparable[] a){
        for(int i=0;i<a.length;i++){
            StdOut.print(a[i]+" ");
            StdOut.println();
        }
    }
    /*
     * compareTo 测试元素是否有序
     * @param {Comparable[]} a 可排序数组
     * @return {boolean} 是否是有序数组 
     * * */
    public static boolean isSorted(Comparable[] a){
        for(int i=1;i<a.length;i++){
            if(less(a[i],a[i-1])){
                return false;
            }
        }
        return true;
    }
    /*
     * compareTo 将int[]转换成Integer[] 
     * @param {int[]} a int数组
     * @return {Integer[]} 转换后的Integer[] 
     * * */
    public static Integer[] intTo(int[] a){
        Integer[] con = new Integer[a.length];
            for(int i=0;i<a.length;i++){
                con[i] = new Integer(a[i]);
            }
        return con;
    }
    //main
        public static void main(String[] args){
            Integer[] a = intTo(In.readInts(args[0]));
            runTime runtime = new runTime();
            sort(a);
            if(!isSorted(a)){StdOut.println("sort is error");System.exit(0);};
            StdOut.println(runtime.End());
        }
}

 

总结:

  ① 抓住要点,每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。

  ② 学习时进行步骤分析,将数组按逻辑的方式人工排序一次,分析它的步骤,最终转化成代码实现 

  直接插入排序算法是希尔排序的基础方法,算法的大门前总有走不完的阶梯,只有坚持不懈、努力学习,才能登高而望,一览众山小。

======================================================== 转载请注明出处。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章