每天虽然还是一如既往的早起,晚睡。但是自己好几天没有刷题, 没有看书了。每天都是在各个KTV,饭店,网吧穿梭。跟那些熟悉却略显陌生的老同学聊着自己近状······感谢老天,下了雨(估计要明天就下雪了)把我从各种酒场中救了出来。忽然感觉其实安静的学习才是一件最享受的事情。今天晚上看了一下排序,整理了一下自己的学习笔记。
插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。
直接插入排序基本思想
1.直接插入排序的基本思想
直接插入排序(Straight Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,将它插入到有序表中的适当位置,使之成为新的有序表,重复n-1次可完成排序过程。把a[i]插入到a[0],a[1],...,a[i-1]之中的具体实施过程为:先把a[i]赋值给变量t,然后将t依次与a[i-1],a[i-2],...进行比较,将比t大的元素右移一个位置,直到发现某个j(0<=j<=i-1),使得a[j]<=t或j为(-1),把t赋值给a[j+1].
2、第i-1趟直接插入排序: 通常将一个记录R[i](i=2,3,…,n-1)插入到当前的有序区,使得插入后仍保证该区间里的记录是按关键字有序的操作称第i-1趟直接插入排序。 排序过程的某一中间时刻,R被划分成两个子区间R[1..i-1](已排好序的有序区)和R[i..n](当前未排序的部分,可称无序区)。 直接插入排序的基本操作是将当前无序区的第1个记录R[i]插人到有序区R[1..i-1]中适当的位置上,使R[1..i]变为新的有序区。因为这种方法每次使有序区增加1个记录,通常称增量法。 插入排序与打扑克时整理手上的牌非常类似。摸来的第1张牌无须整理,此后每次从桌上的牌(无序区)中摸最上面的1张并插入左手的牌(有序区)中正确的位置上。为了找到这个正确的位置,须自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。
一趟直接插入排序方法
1.简单方法 首先在当前有序区R[1..i-1]中查找R[i]的正确插入位置k(1≤k≤i-1);然后将R[k..i-1]中的记录均后移一个位置,腾出k位置上的空间插入R[i]。 注意: 若R[i]的关键字大于等于R[1..i-1]中所有记录的关键字,则R[i]就是插入原位置。
2.改进的方法 一种查找比较操作和记录移动操作交替地进行的方法。具体做法: 将待插入记录R[i]的关键字从右向左依次与有序区中记录R[j](j=i-1,i-2,…,1)的关键字进行比较: ① 若R[j]的关键字大于R[i]的关键字,则将R[j]后移一个位置; ②若R[j]的关键字小于或等于R[i]的关键字,则查找过程结束,j+1即为R[i]的插入位置。 关键字比R[i]的关键字大的记录均已后移,所以j+1的位置已经腾空,只要将R[i]直接插入此位置即可完成一趟直接插入排序。 直接插入排序的效率分析
(1)时间复杂度
从时间分析,首先外层循环要进行n-1次插入,每次插入最少比较一次(正序),移动两次;最多比较i次,移动i+2次(逆序)(i=1,2,…,n-1)。若分别用Cmin ,Cmax 和Cave表示元素的总比较次数的最小值、最大值和平均值,用Mmin
,Mmax 和Mave表示元素的总移动次数的最小值、最大值和平均值,则上述直接插入算法对应的这些量为:Cmin=n-1 Mmin=2(n-1)Cmax=1+2+…+n-1=(n2-n)/2 Mmax=3+4+…+n+1=(n2+3n-4)/2Cave=(n2+n-2)/4 Mmax=(n2+7n-8)/4因此,直接插入排序的时间复杂度为O(n2)。
由上面对时间复杂度的分析可知,当待排序元素已从小到大排好序(正序)或接近排好序时,所用的比较次数和移动次数较少;当待排序元素已从大到小排好序(逆序)或接近排好序时,所用的比较次数和移动次数较多,所以插入排序更适合于原始数据基本有序(正序)的情况.
插入法虽然在最坏情况下复杂性为O(n2),但是对于小规模输入来说,插入排序法是一个快速的排序法。许多复杂的排序法,在规模较小的情况下,都使用插入排序法来进行排序,比如快速排序。
(2)空间复杂度 首先从空间来看,它只需要一个元素的辅助空间,用于元素的位置交换O(1)
(3)稳定性: 插入排序是稳定的,因为具有同一值的元素必然插在具有同一值得前一个元素的后面,即相对次序不变.
(4)结构的复杂性及适用情况 插入排序是一种简单的排序方法,他不仅适用于顺序存储结构(数组),而且适用于链接存储结构,不过在链接存储结构上进行直接插入排序时,不用移动元素的位置,而是修改相应的指针。
最近一直听胡彦斌版的《我的未来不是梦》,很是鼓舞人心。加油,坚持下去!
分享到:
相关推荐
直接插入排序
暑期培训学习笔记之 java\日期排序暑期培训学习笔记之 java\日期排序
Java数据结构与算法学习笔记之排序 冒泡排序,选择排序,插入排序,希尔排序, 归并排序, 快速排序.
Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习...
Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记
LabVIEW学习笔记LabVIEW学习笔记LabVIEW学习笔记LabVIEW学习笔记LabVIEW学习笔记LabVIEW学习笔记
CSS学习笔记CSS学习笔记CSS学习笔记CSS学习笔记
C语言学习笔记C语言学习笔记C语言学习笔记C语言学习笔记
C语言学习笔记 C语言学习笔记 C语言学习笔记 C语言学习笔记
maven学习笔记maven学习笔记maven学习笔记
CCNA学习笔记 CCNA学习笔记 CCNA学习笔记
三、 redis学习笔记之排序 11 四、 redis学习笔记之事务 16 五、 redis学习笔记之pipeline 20 六、 redis学习笔记之发布订阅 23 七、 redis学习笔记之持久化 28 八、 redis学习笔记之主从复制 30 九、 redis学习笔记...
j2ee学习笔记j2ee学习笔记j2ee学习笔记j2ee学习笔记j2ee学习笔记
Jquery学习笔记 Jquery学习笔记 Jquery学习笔记
Java相关课程系列笔记之一Java学习笔记 Java相关课程系列笔记之四JDBC学习笔记 Java相关课程系列笔记之六HTML学习笔记 Java相关课程系列笔记之七CSS学习笔记 Java相关课程系列笔记之八JavaScript学习笔记 Java相关...
计算几何极角排序学习笔记
学习笔记学习笔记学习笔记
docker学习笔记,docker学习笔记,docker学习笔记,docker学习笔记,docker学习笔记,docker学习笔记,docker学习笔记,docker学习笔记,docker学习笔记,docker学习笔记,docker学习笔记,docker学习笔记,docker学习笔记,...
JAVA学习笔记JAVA学习笔记JAVA学习笔记JAVA学习笔记JAVA学习笔记JAVA学习笔记JAVA学习笔记JAVA学习笔记JAVA学习笔记
人工智能学习笔记,人工智能学习笔记,人工智能学习笔记人工智能学习笔记,人工智能学习笔记,人工智能学习笔记人工智能学习笔记,人工智能学习笔记,人工智能学习笔记人工智能学习笔记,人工智能学习笔记,人工智能...