排序-插入排序

Author Avatar
发表:4月 21, 2016 更新:11月 07, 2018
字数统计:661 字 阅读时长:2 分

概念

插入排序是插入类的排序算法,基本原理:将一个记录插入到已经排好序的有序表中,从而得到一个新的记录数增加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)