3.3、插入排序(Insertion Sort)

插入排序（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设计

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)