排序--插入排序

版权声明：本文源自简书tianma，转载请务必注明出处：http://www.jianshu.com/p/8d4b55986106

概念

插入排序是插入类的排序算法，基本原理：将一个记录插入到已经排好序的有序表中，从而得到一个新的记录数增加1的有序表。
具体算法：
整个序列分为两部分，左边部分为已排序的子序列，右边部分为未排序的子序列，取出第1个未排序元素存放在临时变量tmp中，在已经排序的元素序列中从后往前遍历，逐一比较，如果遍历到的元素大于tmp，则将该元素替换下一个位置的元素，直至遍历到的元素小于或等于tmp为止。相当于将未排序的第一个元素插入到已排序的数组中，故以插入排序为名。

演示

比如我们待排序的数组是 {0, 5, 3, 4, 6, 2}
第1趟排序，5大于0，无需插入： 0 5 3 4 6 2
第2趟排序，3小于5，需要插入： 0 3 5 4 6 2
第3趟排序，4小于5，需要插入： 0 3 4 5 6 2
第4趟排序，6大于5，无需插入： 0 3 4 5 6 2
第5趟排序，2小于6，需要插入： 0 2 3 4 5 6

Java实现#####

// 定义接口
interface Sorter {
    /**
     * 将数组按升序排序
     */
    int[] sort(int[] arr);

    /**
     * 交换数组arr中的第i个位置和第j个位置的关键字
     */
    default void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
//插入排序
class InsertSorter implements Sorter {

    @Override
    public int[] sort(int[] arr) {
        insertSort(arr);
        return arr;
    }

    private void insertSort(int[] arr) {
        int len = arr.length;
        int i, j;
        int tmp;
        for (i = 1; i < len; i++) { // 从下标1开始遍历,因为下标0的已经排好序
            if (arr[i] < arr[i - 1]) {
                // 如果当前下标对应的记录小于前一位记录,则需要插入,否则不需要插入，直接将记录数增加1
                tmp = arr[i]; // 记录下标i对应的元素
                for (j = i - 1; j >= 0 && arr[j] > tmp; j--) {
                    arr[j + 1] = arr[j]; // 记录后移
                }
                arr[j + 1] = tmp; // 插入正确位置
            }
        }
    }
}

复杂度

时间复杂度：
最好情况：当待排序的序列为顺序表时，会进行n-1次比较，0次替换，复杂度为O(n)；
最坏情况：当待排序的序列为逆序表时，会进行2+3+...+n=(n+2)*(n-1)/2次比较，2+3+...+n = (n+2)*(n-1)/2次替换，复杂度为O(n^2)；
平均情况：平均比较次数约为n^2/2, 平均移动次数为n^{2/2，复杂度为O(n}2)。

空间复杂度：
最好情况=最坏情况=平均情况=O(1)