数据结构和算法

插入算法

原理

插入排序是使用了增量方法,在已经排序好的子数组A[1..j-1]中插入A[j],产生已经排序好的子数组A[1..j]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int[] datas = new int[]{1, 2, 3, 4, 5, 6};
       for (int i = 1; i < datas.length; i++) {	//次数->n-1
           int k = i;
           int value = datas[i];
           for (int j = i-1; j >= 0; j--) {		//次数->最坏n-1,最好1
               if (datas[j] > value) {
                   datas[k] = datas[j];
                   k = j;
               }
           }
           if (k != i) {
               datas[k] = value;
           }
       }

性能分析

外层循环n-1次,内层循环次数,也是元素的比较次数

最好情况:数组A[n]是已经排序好的,那么元素比较次数是1
最坏情况数组A[n]是反序的,那么元素比较次数是n-1

所以最好情况是n,最坏情况是n^2