基本思想
第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。
直接插入排序属于稳定的排序,最坏时间复杂性为O(n^2),空间复杂度为O(1)。
演示网址:http://www.yxqzzx.cn/teacher/ShowArticle.asp?ArticleID=417
举例说明:
待排序数组R[7,3,4,1,5,8]
第1趟排序:
3 | 7 3 4 1 5 8
3 | 7 7 4 1 5 8
3 | 3 7 4 1 5 8
第2趟排序:
4 | 3 7 4 1 5 8
4 | 3 7 7 1 5 8
4 | 3 4 7 1 5 8
第3趟排序:
1 | 3 4 7 1 5 8
1 | 3 4 7 7 5 8
1 | 3 4 4 7 5 8
1 | 3 3 4 7 5 8
1 | 1 3 4 7 5 8
第4趟排序:
5 | 1 3 4 7 5 8
5 | 1 3 4 7 7 8
5 | 1 3 4 5 7 8
第4趟排序:
R[i-1]<R[i]不需要排序。
从上面的步骤可以看出,直接插入排序的过程为:从数组第一个元素开始,两两相邻的元素进行比较,找出其中的小的元素作为哨兵,并记录位置j,然后从位置j开始,j--到数组起始位置,进行数据交换。
/**
* 直接插入排序
*
* @param unsorted
*/
public static void insertion_sort(int[] unsorted) {
for (int i = 1; i < unsorted.length; i++) {
if (unsorted[i - 1] > unsorted[i]) {
int temp = unsorted[i];
int j = i;
while (j > 0 && unsorted[j - 1] > temp) {
unsorted[j] = unsorted[j - 1];
j--;
}
unsorted[j] = temp;
}
}
}
分享到:
相关推荐
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
直接插入排序、折半插入排序、希尔排列
直接插入排序 选择排序 堆排序 归并排序 快速排序 冒泡排序等七种排序方法
C语言版的排序方法---插入排序,非常有用的代码,可以实际中使用。
数据结构(c语言版)严蔚敏 吴伟民编著 中直接插入排序、折半排序、shell排序、冒泡排序、快速排序、选择排序、堆排序的实现、归并排序,使用c语言实现
算法-理论基础- 排序- 直接插入排序(包含源程序).rar
java代码-直接插入排序-----
插入排序之直接插入排序.cpp
交换排序 选择排序 冒泡排序 插入排序
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
用函数实现直接插入排序,并输出每趟排序的结果. Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出一趟排序结果,数据之间用一个空格分隔 Sample Input 10 ...
数据结构 综合排序 冒泡排序 直接插入排序 快速排序 希尔排序,完整的代码,有每种排序时间的比较
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
直接插入排序、希尔排序、冒泡排序、直接选择排序、堆排序、归并排序
随机生成小于5000的数 根据操作通过不同的方法排序 泡泡排序 直接插入排序 折半插入排序 希尔排序 直接选择排序 统计时间 比较次数和交换次数 保存为txt文件
提供8种排序算法中的直接插入排序,供大家学习参考