输入: n个数<a1, a2, ..., an>
输出:输入序列的一个排列(即重新排序)<a1', a2', ..., an'>,使得a1' <= a2' <= ... <= an'
伪代码就不在赘述,详细见算法导论书第二版
用java代码实现如下
public class InsertionSort {
public static void insert(Integer[] input) {
for(int i = 1; i < input.length; i ++) {
int current = input[i];
//把current插入到input[0...i-1]中
int j = i - 1;
while((j >= 0) && input[j] > current ) {
input[j + 1] = input[j];
j = j -1;
}
input[j + 1] = current;
}
for(int i = 0; i < input.length; i ++) {
System.out.println(input[i] + ", ");
}
}
public static void main(String[] args) {
Integer[] input = new Integer[]{
3,5,7,1,6,9,4,2,8
};
insert(input);
}
}
算法复杂度:O(n2)
分享到:
相关推荐
自学算法导论中前几章,并自己写的排序算法源码包括gtest的测试用例。 详细介绍看我博客 http://blog.csdn.net/ceofit 一、选择法排序、冒泡排序、插入法排序 http://blog.csdn.net/ceofit/article/details/7397020 ...
中科大软件学院 算法导论课程实验 正式题目一 常见排序算法的实现与性能比较 实验报告 包括合并排序、插入排序、希尔排序、快速排序、冒泡排序、桶排序
主要是对算法导论中的插入算法的实现;
中科大软件学院 算法导论课程实验 正式题目一 常见排序算法的实现与性能比较 Visual Studio 2012 项目包 包括合并排序、插入排序、希尔排序、快速排序、冒泡排序、桶排序
包括源码:常用排序算法(插入、堆、归并、快速)、装配线问题、最长公共子序列问题、矩阵连乘问题、 优先队列、huffman编码、贪心算法,全部用Java实现的。 算法导论答案
《算法导论》中一个很经典的算法,排序中的插入排序。一个插入排序的样例。
这些代码是对算法导论上对排序部分的总结,实现了以下排序方法:插入排序,合并排序,堆排序,快速排序,计数排序,每种实现都有详细的注释和相应的测试程序,可查找http://blog.csdn.net/china8848<br>中对相关问题...
算法导论中的一些算法的c++的实现,主要有插入排序、堆排序、基数排序、计数排序、快速排序、桶排序、动态规划-矩阵链乘法等
《算法导论》将严谨性和全面性融为一体。 本书深入讨论各类算法,并着力使这些算法的设计和分析能为各个层次的读者接受。各章自成体系,可以作为独立的学习单元。算法以英语和伪代码的形式描述,具备初步程序设计...
2.1 插入排序 2.2 算法分析 2.3 算法设计 2.3.1 分治法 2.3.2 分治法分析 第3章 函数的增长 3.1 渐近记号 3.2 标准记号和常用函数 第4章 传归式 4.1 代换法 4.2 递归树方法 4.3 主方法 4.4 主定理的证明 4.4.1 取...
中科大算法导论实验,包括代码报告和可执行文件,vc++6.0下编程,c语言代码。 实验部分 一、要求 1.算法设计与分析1班,10月21日(周日)开始上课,晚上19:00-22:00。连续八周每周日在明德楼103实验室上实验课。 2...
这是算法导论第一次实验代码,题目:当输入数据已经“几乎有序时”,插入排序很快,在实际应用中,我们可以利用这一特点来提高快速排序的速度。当对一个长度小于k的子数组调用快速排序时,让它不做任何排序就返回。当...
直接插入排序通过键盘输入建立数组,再经过直接插入排序算法进行排序。在VS上X64编译通过。直接插入排序算法理论参考《算法导论》和张琨的《数据结构与算法分析(C++语言版)》
3、实验1:比较普通快速排序和随机快速排序; 实验2:动态规划实现0-1背包和贪心算法实现部分背包; 实验3:贪心算法实现一个任务的调度问题; 实验4:实现红黑树和AVL树的初始化、插入、删除操作。
2.1 插入排序 2.2 算法分析 2.3 算法设计 2.3.1 分治法 2.3.2 分治法分析 第3章 函数的增长 3.1 渐近记号 3.2 标准记号和常用函数 第4章 递归式 4.1 代换法 .4.2 递归树方法 4.3 主方法 *...
序论:算法分析,插入排序法(Insertion Sort),合并排序(Merge Sort) 阅读:1-2章 发测验 0 2 演示课 1 算法的正确性 发《作业 1》 3 第二课 渐进表示(Asymptotic Notation)。递归公式(Recurrences):置换法,...
2.1 插入排序 2.2 算法分析 2.3 算法设计 2.3.1 分治法 2.3.2 分治法分析 第3章 函数的增长 3.1 渐近记号 3.2 标准记号和常用函数 第4章 递归式 4.1 代换法 .4.2 递归树方法 4.3 主方法 *...
《算法导论》第二章,合并排序与插入排序,C语言源码。
算法导论讲义,第一部分,插入排序,算法复杂度等