插入排序的算法原理比较简单,通过一点点构建有序序列来达到排序的目的。比如给出一个数组a,长度为5,那么首先会将第一个元素作为一个已经排序的序列,然后从第二个元素开始向已经排序的序列(就是第一个元素)从后向前扫描,如果比这个序列中的元素小的话,就插入到相应元素的前面,而插入后需要后移元素。然后第三个元素再从这两个元素组成的有序序列的后面扫描,找到比它小的位置后就插入,否则继续向前扫描,以此类推。
一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
- 从第一个元素开始,该元素可以认为已经被排序
- 取出下一个元素,在已经排序的元素序列中从后向前扫描
- 如果该元素(已排序)大于新元素,将该元素移到下一位置
- 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置中
- 重复步骤2
如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找排序。
算法复杂度
如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数减去(n-1)次。平均来说插入排序算法复杂度为O(n2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。
下面的是用JAVA实现的三种方式
package sort;
import java.util.Arrays;
public class InsertSort {
public static void main(String args[])
{
int array[]={49,38,65,97,76,13,27};
insertSort(array,0,array.length-1);
System.out.println("----------最终结果----------");
System.out.println(Arrays.toString(array));
}
public static void insertSort(int array[],int first,int last)
{
int i,j;
int temp;
for(i=first+1;i<=last;i++)
{
temp = array[i];
j=i-1;
//与已排序的数逐一比较,大于temp时,该数后移
while((j>=first)&&(array[j]>temp))
{
array[j+1]=array[j];
j--;
}
//被排序数放在正确的位置
array[j+1]=temp;
System.out.println(Arrays.toString(array));
}
}
}
运行结果:
[38, 49, 65, 97, 76, 13, 27]
[38, 49, 65, 97, 76, 13, 27]
[38, 49, 65, 97, 76, 13, 27]
[38, 49, 65, 76, 97, 13, 27]
[13, 38, 49, 65, 76, 97, 27]
[13, 27, 38, 49, 65, 76, 97]
----------最终结果----------
[13, 27, 38, 49, 65, 76, 97]
结果分析:
int array[]={49,38,65,97,76,13,27};
1、在方法insertSort()中需要传递三个参数,第一个参数是要排序的数组,第二个参数是数组的第一个元素下表,
即0,第三个元素是数组的最后一个下表,即array.length-1
2、方法体中
第一次:首先将array[i]赋值给temp,其实也就是第2个元素array[1]=38.
此时array[0]=49(看做一个有序序列),然后while中判断如果array[0]>temp,即49>38.
则将array[0]赋给array[1],即array[1]=49,此时j--后j的值变成了-1,然后再array[j+1]=temp,即
array[0]=38,这样其实就是将要排序的数放到了正确的位置。
第二次:i=2,temp=array[2],即65是待排序的数组,其中38、49为有序序列。j=1,while循环里,
array[1]=49,temp=65,array[1]<temp,所以不执行while循环,直接将temp的值65放在array[2]的
位置。
依次类推,如果发现向前扫描的时候,元素比要插入的元素大,就继续向前找,直到找到一个
第一个比它小的数,然后插入。
程序2:
package sort;
import java.util.Arrays;
public class InsertSort2 {
public static void main(String args[])
{
Comparable c[]={49,38,65,97,76,13,27};
insertSort(c);
System.out.println(Arrays.toString(c));
}
public static void insertSort(Comparable data[])
{
for(int i=1;i<data.length;i++)
{
Comparable key = data[i];
int position = i;
while(position>0&&data[position-1].compareTo(key)>0)
{
data[position]=data[position-1];
position--;
}
data[position]=key;
}
}
}
运行结果:
[13, 27, 38, 49, 65, 76, 97]
分析:这里用到了Comparable类,主要是在比较数值的时候用到了compareTo方法进行两个元素的比较
第三种实现方式:
package sort;
import java.util.Arrays;
public class InsertSort3 {
public static void main(String args[])
{
int array[]={49,38,65,97,76,13,27};
insertSort(array,array.length-1);
System.out.println("------------排序后的结果------------");
System.out.println(Arrays.toString(array));
}
public static void insertSort(int array[],int size)
{
int i,j,temp;
for(i=1;i<size;i++)
{
//取出一个数字用来排序,第一个元素array[0]看成一个已经排序的序列
temp=array[i];
//在排序序列中查找位置
for(j=i-1;j>=0&&temp<(array[j]);--j)
{
array[j+1]=array[j];//向后移动数据
}
array[j+1]=temp;//插入数据到序列
System.out.println(Arrays.toString(array));
}
}
}
运行结果:
[38, 49, 65, 97, 76, 13, 27]
[38, 49, 65, 97, 76, 13, 27]
[38, 49, 65, 97, 76, 13, 27]
[38, 49, 65, 76, 97, 13, 27]
[13, 38, 49, 65, 76, 97, 27]
------------排序后的结果------------
[13, 38, 49, 65, 76, 97, 27]
可以看到,运行结果比第一种方式要好一些,不过原理都是一样的
分享到:
相关推荐
详解Java常用排序算法-插入排序
基于python的排序算法-插入排序Insertion Sort
理解插入排序算法-讲解
NULL 博文链接:https://xieyan30.iteye.com/blog/1922400
经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - 归并排序Merge sort 经典排序算法 - 冒泡排序Bubble sort 经典排序算法 - ...
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
自己看书时写的排序算法:插入排序 CPP文件
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
C语言版的排序方法---插入排序,非常有用的代码,可以实际中使用。
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
算法-数据结构和算法-11-插入排序.rar
此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!
该资源提供了Java中实现插入排序的全面指南。文档中涵盖了插入排序的基本概念,包括如何对数组进行排序以及如何在Java中实现插入排序。此外,文档还包括一个逐步指南,介绍了如何在Java中实现插入排序,包括详细的...
C语言实现常见排序算法。编译环境:VS2010。 包括: 冒泡排序 快速排序 直接插入排序 Shell排序 直接选择排序 堆排序 归并排序(递归和非递归两种) 桶式排序 基数排序:顺序和静态队列两种方法 索引排序(采用简单...
排序算法 —— 直接插入排序(图文超详细)
七大排序算法如下: 交换排序:快速排序quicksort,冒泡排序bubblesort 选择排序:直接选择排序selectionsort,堆排序maxheapsort 插入排序:直接插入排序insertsort,希尔排序shellsort 合并排序:归并排序...
NULL 博文链接:https://hoxis.iteye.com/blog/2034252
十大经典排序算法 ... (2)排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部...常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法-理论基础- 排序- 直接插入排序(包含源程序).rar