插入排序(Insertion Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
- 从第一个元素开始,该元素可以认为已经被排序
- 取出下一个元素,在已经排序的元素序列中从后向前扫描
- 如果该元素(已排序)大于新元素,将该元素移到下一位置
- 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置中
- 重复步骤2
public class Insert {
static int array[] = {22,1,23,12,13,88,2};
// 排序整个数组
static void sort(int[] array){
for (int i = 1; i<array.length;i++){
int temp = array[i]; // 将第一个数组理解成已经排序,取出已排序后的数据
int j=i-1;
//与已排序的数逐一比较,大于temp时,该数移后
while((j>=0) && (array[j] > temp))
{
array[j+1] = array[j];
j--;
}
array[j+1] = temp;
}
}
// 对其中一些数组进行排序
static void sort(int[] array, int first,int last){
for (int i = first+1; i<=last;i++){
int temp = array[i];
int j=i-1;
//与已排序的数逐一比较,大于temp时,该数移后
while((j>=first) && (array[j] > temp))
{
array[j+1] = array[j];
j--;
}
array[j+1] = temp;
}
}
static void print(){
for(int k = 0; k < array.length; k++){
System.out.println(array[k]);
}
}
public static void main(String[] args) {
sort(array);
print();
}
}
算法复杂度
如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上(n-1)次。平均来说插入排序算法复杂度为O(n2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。
分享到:
相关推荐
零比特插入算法是一种在数据编码过程中用于实现不同字符集间转换的技术,常见于通信和数据传输领域。在中文环境中,这种算法常用于将非ASCII字符(如汉字)转换为ASCII兼容的格式,以便在网络上传输或者存储。在这个...
渐次插入算法,也称为Incremental Algorithm,是一种逐步构建Delaunay三角网的方法。其基本思路是从第一个点开始,然后依次将后续的点插入到已经构建的三角网中,每次插入新点时,都会检查新点与已有三角形的关系,...
红黑树插入算法 红黑树是一种自平衡二叉查找树,它能够在O(log n)时间内完成插入、删除和查找操作。红黑树的插入算法是指在红黑树中插入新的节点,使得红黑树保持其平衡和性质。 红黑树插入算法的步骤可以分为以下...
### B样条曲线节点插入算法研究及应用 #### 引言 随着计算机图形学的发展,曲线的绘制方式日益多样化,包括但不限于参数三次曲线、Bezier曲线、B样条曲线(B-Spline Curves)以及NURBS(Non-Uniform Rational B-...
### C语言中的直接插入排序算法解析 在计算机科学与编程领域,排序算法是基础且重要的数据处理技术之一,其中直接插入排序(Insertion Sort)是一种简单直观的算法,尤其适用于小规模数据集或部分有序的数据集。...
### B样条曲线节点插入算法研究及应用 #### 一、引言 随着现代工业设计与计算机图形学的发展,各种曲线表示方法应运而生,包括但不限于参数三次曲线、Bézier曲线、B样条曲线(B-spline curves)以及NURBS(Non-...
**B树(B-tree)是一种自平衡的查找树数据...总之,B树插入算法是数据结构和算法学习的重要组成部分,它涉及到多关键字节点的管理和树的平衡保持。通过理解和优化这种算法,我们可以设计出更高效的数据存储和检索系统。
本篇我们将关注一种称为“插入算法”的排列组合实现。 首先,我们需要理解插入算法的基本思想。插入算法是一种基于回溯的策略,它从最简单的排列(如123...n)开始,然后通过插入一个尚未使用的元素来生成新的排列...
研究了求解旅行商问题(TSP)的构建型启发式算法中的最近邻域算法和插入算法的特点, 集最近邻域算法求解速度快、插入算法求解质量高的优点, 提出了一种最近邻域与插入混合...
【实验与比较】在TSPLIB标准库的多个算例上,混合算法的运行时间接近最近邻域算法,对于小规模TSP问题(城市数量小于1000)的解质量与插入算法相当,而在大规模TSP问题中,其解质量优于插入算法。 【结论】混合最近...
本文档《表达式加减运算符插入算法》提供了一个典型的示例,通过系统化的分析和算法设计,解决了如何在数字序列中插入运算符,以达到给定整数目标的问题。本文将深入解读这一算法的设计思路和实现过程。 问题的提出...
根据提供的文件信息,关于“一种提高芯片良率的时序电路缓冲器插入算法”的知识点可以详细说明如下: 1. 芯片良率与工艺参数波动问题 在半导体制造过程中,工艺参数波动会导致芯片良率的下降。随着摩尔定律的推动,...
一维数组插入算法是C语言数据处理中的一个难点,其教学常常面临枯燥和被动的问题。传统的教学方法,即教师为中心的填鸭式教学,难以激发学生的兴趣和主动性,无法让学生深刻理解算法思想。为了解决这一问题,文章...
压缩包内的"数据结构——快排和直接插入算法的性能比较"很可能是包含代码实现和性能测试的资料,可以提供直观的比较结果,帮助我们更好地掌握这两种排序算法的实际表现。通过实际运行和分析这些代码,我们可以深入...
category: 数据结构和算法tags: 插入算法原理插入排序是使用了增量方法,在已经排序好的子数组A[1..j-1]中插入A[j],产生已经排序好的子数组
一种快速的逐点插入算法构建DTM.pdf
本代码采用java实现所罗门I1插入式算法解决带时间窗的vrp问题,求解效果不错,并附有可视化的结果.
Treap树算法,目前实现了节点插入,为算法导论上的算法
插入排序是一种简单直观的排序算法,它的工作原理是通过构造一个有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需要用到O(1)的额外空间...
(1).输入一组整型元素序列,建立顺序表。...输入整型元素序列利用有序表插入算法建立一个有序表。 (7).利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 (8).编写一个主函数,调试上述算法。