插入排序就是把当前待排序的元素插入到一个已经排好序的列表里面。 一个非常形象的例子就是右手抓取一张扑克牌,并把它插入左手拿着的排好序的扑克里面。
插入排序的最坏运行时间是O(n2), 所以并不是最优的排序算法。
如果输入数组已经是排好序的话,插入排序出现最佳情况,其运行时间是输入规模的一个线性函数。
如果输入数组是逆序排列的,将出现最坏情况。平均情况与最坏情况一样,其时间代价是Θ(n2)。
简单例子:
public class Demo6 { public static void main(String[] args) { //定义一个整型数组 int[] nums = new int[]{4,3,-1,9,2,1,8,0,6}; //打印没有进行排序的数组 System.out.println("没有排序之前的结果:" + Arrays.toString(nums)); for(int index=0; index<nums.length; index++) { //获得需要插入的数值 int key = nums[index]; //取得下标值 int position = index; /循环比较之前排序好的数据,找到合适的地方插入 while(position >0 && nums[position-1] > key) { nums[position] = nums[position-1]; position--; } nums[position] = key; } //打印排序后的结果 System.out.println("排序后的结果:" + Arrays.toString(nums)); } }
文章名称:java数据结构之插入排序-创新互联
标题链接:https://www.cdcxhl.com/article14/copcge.html
成都网站建设公司_创新互联,为您提供搜索引擎优化、做网站、全网营销推广、网站设计、网站排名、网站制作
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联