插入排序(Insertion Sort)是一种简单直观且稳定的排序算法。

3.3.1、需求

  • 排序前:{4,3,2,10,12,1,5,6}
  • 排序后:{1,2,3,4,5,6,10,12}

3.3.2、排序原理

  • 把所有元素分成两组,已经排序的和未排序的
  • 找到未排序数组中的第一个元素,向已经排序的数组中插入
  • 倒叙遍历已经排序的元素,一次和代插入的元素进行比较,直到找到一个元素小于等待插入的元素,那么就把待插入元素放到这个元素的位置,其他的元素向后移动一位

3.3.3、API设计

构造方法 Insertion():创建Insertion对象
成员方法 public static void sort(Comparable[] a):对数组内的元素进行排序
private static boolean grater(Comparable v,Comparable w):判断v是否大于w
private static void exch(Comparable[] a,int i,int j):交换a数组中,索引i和索引j处的值

3.3.4、代码实现

算法类:

package cn.test.algorithm.sort;

public class Insertion {

    /**
     * 对数组元素进行排序
     *
     * @param a
     */
    public static void sort(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            for (int j = i; j > 0; j--) {
                if (greater(a[j - 1], a[j])) {
                    exch(a, j - 1, j);
                } else {
                    break;
                }
            }
        }
    }

    /**
     * 比较v元素是否大于w元素
     *
     * @return
     */
    private static boolean greater(Comparable v, Comparable w) {
        return v.compareTo(w) > 0;
    }

    /**
     * 交换i和j处的元素值
     *
     * @param a
     * @param i
     * @param j
     */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

测试类:

package cn.test.algorithm.test;

import cn.test.algorithm.sort.Insertion;

import java.util.Arrays;

public class TestInsertion {
    public static void main(String[] args) {
        Integer[] arr = {4, 3, 2, 10, 12, 1, 5, 6};
        Insertion.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

测试结果:

[1, 2, 3, 4, 5, 6, 10, 12]

3.3.5、时间复杂度分析

插入排序使用了双层的for循环,其中内层循环体真正完成了排序代码,所以主要分析内层循环体执行的次数即可。

最坏的情况下,比较次数:

(n-1)+(n-2)+...+2+1=((n-1)+1)*(n-1)/2=n^2/2-n/2

交换次数:

(n-1)+(n-2)+...+2+1=((n-1)+1)*(n-1)/2=n^2/2-n/2

总共执行次数:

n^2/2-n/2+n^2/2-n/2 = n^2-n

根据大O推导法则,时间复杂度为O(n^2)