插入排序算法是一个对少量元素进行排序的有效算法。插入排序的工作原理与打牌时整理手中的牌的做法类似,开始摸牌时,我们的左手是空的,接着一次从桌上摸起一张牌,并将它插入到左手的正确位置。为了找到这张牌的正确位置,要将它与手中已有的牌从右到左进行比较,无论什么时候手中的牌都是排序好的。
JAVA实现该算法如下:
public void insertSort(int a[]){
int length=a.length; //数组长度
int j; //当前值的位置
int i; //指向j前的位置
int key; //当前要进行插入排序的值
//从数组的第二个位置开始遍历值
for(j=1;j<length;j++){
key=a[j];
i=j-1;
//a[i]比当前值大时,a[i]后移一位,空出i的位置,好让下一次循环的值后移
while(i>=0 && a[i]>key){
a[i+1]=a[i]; //将a[i]值后移
i--; //i前移
}//跳出循环(找到要插入的中间位置或已遍历到0下标)
a[i+1]=key; //将当前值插入
}
}
事例图如下:
insertSort在数组A={5,2,4,6,1,3}上的处理过程,数组的下标出现在巨型的上方,黑色框的值即为key=a[j]。
a[i]即为a[j]左边的值,每次循环key与a[i]进行比较,如果key<a[i],则a[i]移到 i+1处,同时i--向左移动,直到找到a[i]<=key或者i<0,此时将 key插入到a[i+1]处。
问题1:a[i]第一次进行右移时覆盖了a[i+1]值,是否造成了数据丢失?
答:不会造成数据丢失,应为第一次右移前的i+1=j,此时a[j]的值存在了key里了。每次右移都为下一次右移或插入留出了位置,这就是插入排序的关键点所在。
- 大小: 69.6 KB
分享到:
相关推荐
java实现的常用的几种基本排序算法,插入、交换、选择、归并
详解Java常用排序算法-插入排序
1. 一个PPT 用动画演示了 插入排序,直接插入排序,希尔排序,附带讲解。 2. 附带其他几种常用排序的java实现的源码。 3. PPT 还是简洁、美观的,可用作模板。
7大排序算法详解文档,包括冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、基数排序。附带java代码实现,可以直接运行。
主要介绍了直接插入排序算法与相关的Java版代码实现,需要的朋友可以参考下
主要介绍了Java 选择排序、插入排序、希尔算法实例详解,需要的朋友可以参考下
主要为大家详细介绍了Java经典排序算法之二分插入排序,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
主要介绍了java数据结构与算法之插入排序,结合实例形式分析了java插入排序的概念、分类、原理、实现方法与相关注意事项,需要的朋友可以参考下
本文主要介绍了java的七种常见排序算法的实现,对选择排序、插入排序、冒泡排序、归并排序、快速排序、希尔排序、最小堆排序进行原理分析与实例介绍,具有很好的参考价值。下面就跟着小编一起来看下吧
4.4.2 插入排序115 4.5 增强for循环116 4.6 本章练习117 第5章 5.1 面向过程的设计思想120 5.2 面向对象的设计思想120 5.3 抽象121 5.3.1 对象的理解121 5.3.2 Java抽象思想的实现122 5.4 封装124 5.4.1 对象封装的...
Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的氣泡排序 Heap 排序法 - 改良的選擇排序 快速排序法(一) 快速排序法(二) 快速排序法(三) 合併排序法 基數排序法 搜尋 循序搜尋法(使用衛兵...
数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入。 换成链表时,显然无需做这种大量移动,根据每个节点的前驱节点“指针”,向前找到插入点后,直接...
给大家介绍Java中的排序并不是指插入排序、希尔排序、归并排序等具体的排序算法。而是自然排序和比较器排序,文中通过实例代码介绍的很详细,有需要的朋友们可以参考借鉴。
插入排序 希尔排序 归并排序 快速排序 选择排序 奇偶排序 总结 前言:在前端大全中看到这句话,以此共勉。基础决定你可能达到的高度, 而业务决定了你的最低瓶颈 其实javascript算法在平时的编码中用处不大,...
介绍 这些文章是我的编程学习笔记。... 09-- 算法#09--用简单的思维理解选择,插入,冒泡和希尔排序 10-- 算法#10--用简单的思维理解堆排序 算法# 用简单的思维理解归并排序和三向快速排序 12--
25 JAVA8 与元数据.................................................................................................................................25 2.4. 垃圾回收与算法 .................................
平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树(递归定义)的二叉排序树。...
2012-06-11 21:13 31,839 用Visual C++实现排序算法大全.rar 2012-06-11 21:09 27,688 用单片机制作的高精度数显计数器.rar 2012-06-11 21:10 9,654 用单片机实现公历到农历换算的新方法.zip 2012-06-11 21:08 2,318...