插入排序详解(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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:选择排序详解(Java实现)
下一篇:冒泡排序详解(Java实现)

发表评论

最新留言

表示我来过!
[***.240.166.169]2024年03月10日 19时43分34秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

php语言冒泡法,PHP 冒泡排序法 2019-04-21
php如何数组去重复,PHP如何去除数组重复元素? 2019-04-21
java转换ab的值,查看新闻/公告--[整理]Java将AB1234形式的16进制字符串转换为10进制数值,考虑字节序的影响.... 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
linux vim编辑kconfig 无法wq,Linux-4.9.2内核在mini2440上的移植(三)——编译环境测试... 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
iphone通讯录 android,3个方法,教你如何快速而又有效的将联系人从iPhone转移到安卓... 2019-04-21
android horizontalscrollview 滑动事件,ScrollView的滑动监听(以HorizontalScrollView为例) 2019-04-21
win7自定义html为桌面,Win7系统自定义桌面主题的方法 2019-04-21
单系统 台电x80pro_台电x80 pro (ID:E3E6)安装remix OS系统教程整理 2019-04-21
linux存储pdf伟岸_python的reportlab库介绍、制作pdf和作图 2019-04-21
安徽信息技术初中会考上机考试模拟_2020年中小学寒假、考试时间定下了! 2019-04-21
ubuntu 退出anaconda环境_从零开始深度学习第15讲:ubuntu16.04 下深度学习开发环境搭建与配置... 2019-04-21