李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
Java
正文
数据结构和算法学习--插入排序
Leefs
2020-02-01 PM
1387℃
0条
# 数据结构和算法学习--插入排序 ### 一、插入排序介绍 插入式排序属于内部排序法,是对于欲排序的元素以插入的方式找寻该元素的适当位置,以达到排序的目的。 ### 二、插入排序法思想 插入排序(Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,元素表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。 ### 三、插入排序思路图 ![16.插入排序算法01.png][1] ### 四、插入排序法应用实例 有一群小牛,考试成绩分别是101,34,119,1请从小到大排序 **代码** ```java public class InsertSort { public static void main(String[] args) { int[] arr={101,34,119,1,-1,89}; insertSort(arr); } //插入排序 public static void insertSort(int[] arr){ int insertVal=0; int insertIndex=0; //使用for循环 for(int i=1;i
=0 && insertVal < arr[insertIndex]){ arr[insertIndex+1]=arr[insertIndex]; insertIndex--; } if(insertIndex +1 != i){ arr[insertIndex+1]=insertVal; } System.out.println(Arrays.toString(arr)); } } } ``` > 运行结果 ``` [34, 101, 119, 1, -1, 89] [34, 101, 119, 1, -1, 89] [1, 34, 101, 119, -1, 89] [-1, 1, 34, 101, 119, 89] [-1, 1, 34, 89, 101, 119] ``` **完整代码** ```java public class InsertSort2 { public static void main(String[] args) { //int[] arr = {101, 34, 119, 1, -1, 89}; // 创建要给80000个的随机的数组 int[] arr = new int[80000]; for (int i = 0; i < 80000; i++) { arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数 } System.out.println("插入排序前"); Date data1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(data1); System.out.println("排序前的时间是=" + date1Str); insertSort(arr); //调用插入排序算法 Date data2 = new Date(); String date2Str = simpleDateFormat.format(data2); System.out.println("排序前的时间是=" + date2Str); //System.out.println(Arrays.toString(arr)); } //插入排序 public static void insertSort(int[] arr) { int insertVal = 0; int insertIndex = 0; //使用for循环来把代码简化 for(int i = 1; i < arr.length; i++) { //定义待插入的数 insertVal = arr[i]; insertIndex = i - 1; // 即arr[1]的前面这个数的下标 // 给insertVal 找到插入的位置 // 说明 // 1. insertIndex >= 0 保证在给insertVal 找插入位置,不越界 // 2. insertVal < arr[insertIndex] 待插入的数,还没有找到插入位置 // 3. 就需要将 arr[insertIndex] 后移 while (insertIndex >= 0 && insertVal < arr[insertIndex]) { arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex] insertIndex--; } // 当退出while循环时,说明插入的位置找到, insertIndex + 1 // 举例:理解不了,我们一会 debug //这里我们判断是否需要赋值 if(insertIndex + 1 != i) { arr[insertIndex + 1] = insertVal; } //System.out.println("第"+i+"轮插入"); //System.out.println(Arrays.toString(arr)); } /* //使用逐步推导的方式来讲解,便利理解 //第1轮 {101, 34, 119, 1}; => {34, 101, 119, 1} //{101, 34, 119, 1}; => {101,101,119,1} //定义待插入的数 int insertVal = arr[1]; int insertIndex = 1 - 1; //即arr[1]的前面这个数的下标 //给insertVal 找到插入的位置 //说明 //1. insertIndex >= 0 保证在给insertVal 找插入位置,不越界 //2. insertVal < arr[insertIndex] 待插入的数,还没有找到插入位置 //3. 就需要将 arr[insertIndex] 后移 while(insertIndex >= 0 && insertVal < arr[insertIndex] ) { arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex] insertIndex--; } //当退出while循环时,说明插入的位置找到, insertIndex + 1 //举例:理解不了,我们一会 debug arr[insertIndex + 1] = insertVal; System.out.println("第1轮插入"); System.out.println(Arrays.toString(arr)); //第2轮 insertVal = arr[2]; insertIndex = 2 - 1; while(insertIndex >= 0 && insertVal < arr[insertIndex] ) { arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex] insertIndex--; } arr[insertIndex + 1] = insertVal; System.out.println("第2轮插入"); System.out.println(Arrays.toString(arr)); //第3轮 insertVal = arr[3]; insertIndex = 3 - 1; while (insertIndex >= 0 && insertVal < arr[insertIndex]) { arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex] insertIndex--; } arr[insertIndex + 1] = insertVal; System.out.println("第3轮插入"); System.out.println(Arrays.toString(arr)); */ } } ``` > 运行结果 ``` 插入排序前 排序前的时间是=2020-02-01 22:41:27 排序前的时间是=2020-02-01 22:41:28 ``` [1]: https://lilinchao.com/usr/uploads/2020/02/72330779.png
标签:
数据结构和算法
,
排序
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:
https://lilinchao.com/archives/534.html
上一篇
数据结构和算法学习--选择排序
下一篇
数据结构和算法学习--希尔排序
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
31
其它
25
GO
43
标签云
Spark Streaming
随笔
Java编程思想
LeetCode刷题
高并发
Netty
Elastisearch
Java工具类
FileBeat
Spark
nginx
SpringCloudAlibaba
Nacos
队列
SpringBoot
散列
Azkaban
Zookeeper
MyBatisX
RSA加解密
栈
Scala
Typora
VUE
CentOS
前端
国产数据库改造
Docker
Spark Core
Thymeleaf
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞