插入排序详解(Java实现)
发布日期:2021-07-26 07:20:47
浏览次数:2
分类:技术文章
本文共 1475 字,大约阅读时间需要 4 分钟。
一、基本思想
插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
二、算法描述
1.从第一个元素开始,该元素可以认为已经被排序;
2.取出下一个元素,在已经排序的元素序列中从后向前扫描; 3.如果该元素(已排序)大于新元素,将该元素移到下一位置; 4.重复步骤3,直到找到已排序的元素小于或者等于新元素的位置; 5.将新元素插入到该位置后; 重复步骤2~5。三、算法分析
插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
四、算法代码实现
package sort;public class InsertSort { public static void main(String[] args) { int[] array = {53,68,32,96,58,12,25,68,99}; System.out.println("原序列:"); for (int i : array) { System.out.print(i+" "); } System.out.println(); insertSort(array); System.out.println("排序后:"); for (int i : array) { System.out.print(i+" "); } } public static void insertSort(int[] a){ int preIndex, current; //i作为本次循环确定取出的元素值下标 for (int i = 1; i < a.length; i++) { //preIndex:为记录当前下标i需要从后往前的下标值 preIndex = i - 1; //取出本次循环最后一个下标i的元素值 current = a[i]; //当比较的preIndex值还没越界,并且下标preIndex的元素值大于本次比较值current时 //preIndex下标元素值后移,同时preIndex--,继续比较下一次 while (preIndex >= 0 && a[preIndex] > current) { a[preIndex + 1] = a[preIndex]; preIndex--; } //当preIndex检索的值已经移动完毕或者没有移动,需要将当前比较的current值重新插入序列中 a[preIndex + 1] = current; } }}
五、结果值查看
原序列:53 68 32 96 58 12 25 68 99 排序后:12 25 32 53 58 68 68 96 99
转载地址:https://blog.csdn.net/qq_38741971/article/details/81662860 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年03月10日 19时43分34秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
php语言冒泡法,PHP 冒泡排序法
2019-04-21
php如何数组去重复,PHP如何去除数组重复元素?
2019-04-21
ui php h5,画出自己的UI组件的详情
2019-04-21
linux服务文件编写,linux编写systemd下服务脚本
2019-04-21
hdfs linux 目录是否存在,Linux中判断hdfs文件是否存在
2019-04-21
linux学习需要什么基础,学linux需要什么基础?
2019-04-21
高斯勒让德在c语言中的程序,c语言:用递归方法编写程序,求n阶勒让德多项式的值...
2019-04-21
c语言单片机电子时钟,新人求个51单片机的电子时钟汇编语言(C语言的还没学到)...
2019-04-21
c++语言文件流,C++文件流
2019-04-21
android 动态毛玻璃,Android毛玻璃背景效果简单实现代码
2019-04-21
android 按钮提示,的Android按钮工具提示
2019-04-21
win7自定义html为桌面,Win7系统自定义桌面主题的方法
2019-04-21
linux存储pdf伟岸_python的reportlab库介绍、制作pdf和作图
2019-04-21
安徽信息技术初中会考上机考试模拟_2020年中小学寒假、考试时间定下了!
2019-04-21