一.排序方法
基本思想:被排列的数组data[0...n]。初始时,data[0]自成1个有序区,无序区为data[1..n];从i=1起直至i=n为止,依次将data[i]插入当前的有序区data[0..i-1]中,生成含n个记录的有序区。
- 将待插入元素data[i]从右向左依次与有序区中记录data[j](j=i-1,i-2,…,0)进行比较。
- 若data[j]大于data[i],则将data[j]后移一个位置。
- 若data[j]小于或等于data[i],则查找过程结束,j+1即为data[i]的插入位置。
二.动画演示
http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/insertsort.htm
三.Java代码
public static int[] insertSort(int[] data) {
int temp = 0;
for (int i = 1; i < data.length; i++) {
if (data[i - 1] > data[i]) {
temp = data[i];
int j = i - 1;
for (; j >= 0 && data[j] > temp; j--) {
data[j + 1] = data[j]; // 后移
}
data[j + 1] = temp;
}
}
return data;
}
四.时间复杂度和稳定性
- 最好时间复杂度
- 若文件的初始状态是正序的,所需的关键字比较次数C和记录移动次数M。
- Cmin
=n-1=0(n)
- Mmin
=0
- 直接插入排序最好的时间复杂度为O(n)
- 最坏时间复杂度
- 若初始文件是反序的,所需的关键字比较次数C和记录移动次数M。
- Cmax
=(n+2)(n-1)/2=O(n2
)
- Mmax
=(n-1)(n+4)/2=O(n2
)
- 直接插入排序的最坏时间复杂度为O(n2
)
- 平均时间复杂度
- O(n2
)
- 算法的空间复杂度:算法所需的辅助空间是一个监视哨,辅助空间复杂度S(n)=O(1)。是一个就地排序。
- 直接插入排序是稳定的。
分享到:
相关推荐
本资源为数据结构与算法第三章(排序)的作业程序代码。包含以下的两个程序: 3.4 rk作哨兵直接插入排序 3.8 双向起泡 北工大电控学院《数据结构与算法》课程的其它章节程序实验及作业代码亦已在本站上传,需要的...
使用C语言写的直接插入排序算法,简单易懂,希望对大家学习有帮助
南昌大学科学技术学院实验报告,《数据结构》课程设计是为训练学生的数据组织能力和提高程序设计能力而设置的增强实践能力的课程...目的:学习数据结构课程,旨在使学生学会分析研究数据对象的特性,学会数据的组织方法
包含的九种内部排序有:直接插入排序、折半排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、链式基数排序(有简单介绍各个排序方法的时间复杂度)。 每一种排序算法,基本以 “小标题-算法...
数据结构-3期(KC002) 直接插入排序算法.docx 学习资料 复习资料 教学资源
用flash方式演示各种数据结构基础算法3——排序部分,很直观,合适基础学习者使用。里面包括:堆排序.swf,规并排序.swf,基数排序.swf,快速排序.swf,冒泡排序.swf,桶式排序法.swf,希尔排序.swf,直接插入排序....
希尔排序算法描述如下:将一个数据序列分成若干组,每组由若干相隔一段距离(称为增量)的元素组成,在一个组内采用直接插入排序算法进行排序; 增量初值通常为数据序列长度的一半,以后每趟增量减半,最后值为1....
排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序。 内部排序是数据记录在内存中进行排序。 而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要...
2.4.3 三种基本结构和改进的流程图 28 2.4.4 用N-S 流程图表示算法 29 2.4.5 用伪代码表示算法 30 2.4.6 用计算机语言表示算法 31 2.5 结构化程序设计方法 31 3 数据类型、运算符与表达式 3.1 C语言的数据类型 32 ...
光盘内容可在DOS环境下运行的以类C语言描述的“数据结构算法动态模拟辅助教学软件,以及在Windows环境下运行的以类PASCAL或类C两种语言描述的“数据结构算法动态模拟辅助教学软件”。 本书可作为计算机类专业或信息...
主要介绍了C++实现选择排序、直接插入排序、冒泡排序的代码示例,相当简洁直观,也是算法和数据结构学习中的基础,需要的朋友可以参考下
本书后附有光盘,光盘中含有可在DOS环境下运行的以类C语言描述的“数据结构算法动态模拟辅助教学软件,以及在Windows环境下运行的以类PASCAL或类C两种语言描述的“数据结构算法动态模拟辅助教学软件”。本书可作为...
2.4.3 三种基本结构和改进的流程图 28 2.4.4 用N-S 流程图表示算法 29 2.4.5 用伪代码表示算法 30 2.4.6 用计算机语言表示算法 31 2.5 结构化程序设计方法 31 3 数据类型、运算符与表达式 3.1 C语言的数据类型 32 ...
实现直接插入排序、折半插入、冒泡、快速、直接选择、堆、归并排序算法。比较各种 算法的运行速度和时间复杂度,是否为稳定排序。分析每一趟排序结果。
光盘内容可在DOS环境下运行的以类C语言描述的“数据结构算法动态模拟辅助教学软件,以及在Windows环境下运行的以类PASCAL或类C两种语言描述的“数据结构算法动态模拟辅助教学软件”。 目录: 第1章 绪论 1.1 什么...
10.2.1 直接插入排序 10.2.2 其他插入排序 10.2.3 希尔排序 10.3 快速排序 10.4 选择排序 10.4.1 简单选择排序 10.4.2 树形选择排序 10.4.3 堆排序 10.5 归并排序 10.6 基数排序 10.6.1 多关键字的排序 10.6.2 链式...
数据结构算法演示 1. 顺序表 (1)在顺序表中插入一个数据元素(ins_sqlist) (2)删除顺序表中一个数据元素(del_sqlist) (3)合并两个有序顺序表(merge_sqlist) 2. 链表 (1)创建一个单链表(Crt_LinkList) ...
通过SWF动画来演示数据结构查找,排序等原理,对于学习数据结构的同学非常有用。B-树的删除.swfB树的生成.swf查找中序线索二叉树后继.swf串的顺序存单链表结点的插入.swf单链表结点的删除.swf堆排序.swf二叉排序树的...