直接插入排序详解编程语言
编程语言 详解 直接 插入排序
2023-06-13 09:20:22 时间
基本思想
每一趟将一个待排序的记录,按其关键字的大小插入到已经排好序的一组记录的适当位置上,直到所有待排序记录全部插入为止。
排序过程
1.初始化无序区、有序区,待排序数组的第一个元素为有序区,剩余元素为无序区;
2.遍历无序区,将无序区每一个元素插入到有序区的正确位置上;
Java算法实现
![直接插入排序详解编程语言](http://blog.ytso.com/zb_users/plugin/LazyLoad/usr/loading.gif)
![直接插入排序详解编程语言](http://blog.ytso.com/zb_users/plugin/LazyLoad/usr/loading.gif)
/** * 排序接口类 * Created by zhouyh on 2018/5/25. */ public abstract class ISort { public abstract int[] sort(int[] array); } /** * 直接插入排序 * Created by zhouyh on 2018/5/25. */ public class DirectInsertSort extends ISort { @Override public int[] sort(int[] array) { int tmp; for (int i=1; i array.length; i++){ tmp = array[i]; //array[i]的拷贝 //如果右侧无序区第一个元素 array[i] array[i-1] 小于左侧有序区最后一个元素 //需要将左侧有序区比array[i]大的元素后移 if (array[i] array[i-1]){ int j = i-1; while (j =0 tmp array[j]){ array[j+1] = array[j]; j--; } array[j+1] = tmp; } } return array; } }
性能分析
时间复杂度,在比较的数组有序的情况下,为O(n),即此刻比较次数n-1次,移动次数0;在最坏的情况下,即数组逆序的情况下,为O(n^2),平均时间复杂度为O(n^2)
空间复杂度,直接排序的过程中,仅用到了一个临时变量,空间复杂端为O(1)
稳定性,直接插入排序为稳定排序,即排序前后的元素位置还是保持和排序前的前后顺序一致,例{2①,45,12,2④,3},排序后{2①,2④,3,12,45},其中两个2的前后顺序保持一致。
使用场景
在数组包含的元素数量较小情况下,可以选择插入排序,元素数量较大的情况下,不适用,因此时移动元素的次数较多;
在数组基本有序的情况下,适合使用插入排序,此时时间复杂度基本上为O(n)
原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/7489.html
cjava相关文章
- c语言之父是谁-知名编程语言的发展简史
- checkbox 全选和全不选jQuery代码实现详解编程语言
- JavaScript学习总结(八)——JavaScript数组详解编程语言
- node中使用consolidate后报错Cannot find module ‘ejs’详解编程语言
- Linux python 自动补全详解编程语言
- html表格的基本用法详解编程语言
- 如何把JAVA工程生成一个.JAR文件,而不是一堆JAR(ECLIPSE生成JAR)详解编程语言
- jQuery提交form表单详解编程语言
- jquery选择器之层级过滤选择器详解编程语言
- linux中安装eclipse,安装好之后不能直接建servlet,不能直接在jsp页面中run on server.权限在作怪,我猜的,详解编程语言
- NIO之直接缓冲区与非直接缓冲区详解编程语言
- EL表达式无法显示,直接显示${xxx}详解编程语言
- Java移位运算符详解实例编程语言
- abap perform的using与changing区别详解编程语言
- 直接选择排序详解编程语言
- ALV直接返回选择屏幕详解编程语言
- php cli传递参数的方法详解编程语言
- win7 安装php插件imagick详解编程语言
- php 开启微信公众号开发者模式详解编程语言
- SAP 自开发程序显示多条消息详解编程语言
- 屏幕字段不允许直接输入,只能通过SearchHelp(F4)详解编程语言
- 使用a href 文件下载 IE直接打开 内容乱码详解编程语言