当前位置:首页软件开发Java → 排序算法-直接插入排序

排序算法-直接插入排序

时间:2020-08-12 18:12:00来源:互联网我要评论(0)

直接插入排序

思想:

每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。

第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。         算法复杂度:如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。 最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。 最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。        插入排序的赋值操作是比较操作的次数减去(n-1)次。平均来说插入排序算法复杂度为O(n2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。
package com.liuhao;

public class InsertionSort {

    /**
     *  直接插入排序
     *  基本思想:在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,
     *  现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,
     *  直到全部排好顺序。
     * @param a
     * @return
     */
    public int[] insertSort(int a[]){
       
        int temp = 0;
       
        for(int i=1; i<a.length; i++){
            int j = i-1;
            temp = a[i];
           
            for(;j>=0 && a[j]>temp; j--){
                a[j+1] = a[j];
            }
           
            a[j+1] = temp;
        }
       
        return a;
    }
}

相关文章

网友评论

热门评论

最新评论

发表评论 查看所有评论()

昵称:
表情: 高兴 可 汗 我不要 害羞 好 下下下 送花 屎 亲亲
字数: 0/500 (您的评论需要经过审核才能显示)

关于万荚 | 联系方式 | 发展历程 | 版权声明 | 帮助(?) | 网站地图 | 友情链接

Copyright 2005-2020 16WJ.COM 〖万荚网〗 版权所有 桂ICP备18000060号 |

声明: 本站所有文章来自互联网 如有异议 请与本站联系