插入排序(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)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。
分享到:
相关推荐
顺序表上的插入算法,实现了顺序插入的功能,简单易懂,完全采用C语言
红黑树插入算法C++实现
中国科学技术大学的算法课程,红黑树插入算法实验报告
利用渐次插入算法,根据坐标数据生成简易Delaunay三角网。
本文讲解了用C语言实现直接插入法的算法的代码实现。
红黑树插入算法红黑树插入算法红黑树插入算法
研究了求解旅行商问题(TSP)的构建型启发式算法中的最近邻域算法和插入算法的特点, 集最近邻域算法求解速度快、插入算法求解质量高的优点, 提出了一种最近邻域与插入混合...
B样条曲线节点插入算法研究及应用B样条曲线节点插入算法研究及应用B样条曲线节点插入算法研究及应用
计算机网络作业,大学网络课程实验!
LagrangeInsert 拉格朗日插入算法 程序是用VC6.0编与
B tree 的一个插入算法 C++完成,面向对象特性很突出,值得学习,但是代码可能需要一点点优化,需要继续改进,但是基本结构已经很不错
7中间的排序和插入算法
B_树的插入算法,分裂(详细的C++代码)
表达式加减运算符插入算法.doc
数据结构——快排和直接插入算法的性能比较,实现了快排和插入算法的性能比较。
category: 数据结构和算法tags: 插入算法原理插入排序是使用了增量方法,在已经排序好的子数组A[1..j-1]中插入A[j],产生已经排序好的子数组
B样条曲线节点插入算法研究及应用,给学习nurbs或计算机图形学的人一点帮助
一种快速的逐点插入算法构建DTM.pdf
链表结点插入算法
一种提高芯片良率的时序电路缓冲器插入算法.pdf