时间复杂度
当数据正序时,执行效率最好,每次插入都不用移动前面的元素,时间复杂度为O(N)。
当数据反序时,执行效率最差,每次插入都要前面的元素后移,时间复杂度为O(N2)。
所以,数据越接近正序,直接插入排序的算法性能越好。
空间复杂度
由直接插入排序算法可知,我们在排序过程中,需要一个临时变量存储要插入的值,所以空间复杂度为 1 。
算法稳定性
直接插入排序的过程中,不需要改变相等数值元素的位置,所以它是稳定的算法。
完整参考代码
JAVA版本
代码实现
1 packagenotes.javase.algorithm.sort;
2
3 importjava.util.Random;
4
5 public classInsertSort{
6
7 public voidinsertSort(int[]list){
8 //打印第一个元素
9System.out.format("i=%d: ",0);
10printPart(list,0,0);
11
12 //第1个数肯定是有序的,从第2个数开始遍历,依次插入有序序列
13 for(inti=1;i<list.length;i++){
14 intj=0;
15 inttemp=list[i];//取出第i个数,和前i-1个数比较后,插入合适位置
16
17 //因为前i-1个数都是从小到大的有序序列,所以只要当前比较的数(list[j])比temp大,就把这个数后移一位
18 for(j=i-1;j>=0&&temp<list[j];j--){
19list[j+1]=list[j];
20}
21list[j+1]=temp;
22
23System.out.format("i=%d: ",i);
24printPart(list,0,i);
25}
26}
27
28 //打印序列
29 public voidprintPart(int[]list,intbegin,intend){
30 for(inti=0;i<begin;i++){
31System.out.print(" ");
32}
33 for(inti=begin;i<=end;i++){
34System.out.print(list[i]+" ");
35}
36System.out.println();
37}
38
39 public static voidmain(String[]args){
40 //初始化一个随机序列
41 final intMAX_SIZE=10;
42 int[]array=new int[MAX_SIZE];
43Randomrandom=newRandom();
44 for(inti=0;i<MAX_SIZE;i++){
45array[i]=random.nextInt(MAX_SIZE);
46}
47
48 //调用冒泡排序方法
49InsertSortinsert=newInsertSort();
50System.out.print("排序前: ");
51insert.printPart(array,0,array.length-1);
52insert.insertSort(array);
53System.out.print("排序后: ");
54insert.printPart(array,0,array.length-1);
55}
56}
运行结果
排序前:6335631064
i=0:6
i=1:36
i=2:336
i=3:3356
i=4:33566
i=5:333566
i=6:1333566
i=7:01333566
i=8:013335666
i=9:0133345666
排序后:0133345666
参考资料
《数据结构习题与解析》(B级第3版)
http://www.cnblogs.com/huangxincheng/archive/2011/11/20/2255695.html
相关阅读
欢迎阅读 程序员的内功——算法 系列
示例源码:https://github.com/dunwu/algorithm-notes
优质内容筛选与推荐>>
1、《有关程序员的性别、年龄、个性、编程方法的话题》(2010/01/31)2、如何获取TypedArray?3、Spring-2-官网学习4、Python字符串5、链表逆序