一个Java小白通向数据结构算法之旅(6) - 插入排序

用户2032165

发布于 2018-06-05 16:55:31

4530

发布于 2018-06-05 16:55:31

文章被收录于专栏：cmazxiaoma的架构师之路cmazxiaoma的架构师之路

前言

过几天就是双11了，现在的我已经没有任何购物的欲望了。也许会在双11，买几本书，充实一下自己，仅此而已。

timg.jpg

插入排序的优点

在一般情况下，插入排序是基本排序算法中最好的一种。虽然插入排序算法需要O(N^2)的时间，但是一般情况下，它要比冒泡排序快一倍，比选择排序还要快一些。

提取思想

我们可以认为插入排序是局部有序。左边是局部有序，右边是无序的。
假如在一串数字中，我们选择了一个标记的数字。在这个作为标记的数字左边的所有数字都已经是局部有序了。这意味着这一部分人之间是按顺序排列的，但是这些数字在队列中的最终的位置还没有确认。因为当没有被排序的数字插入到它们中间的时候，它们的位置还需要发生变化。
我们要在局部有序中的适当位置插入被标记的数字。需要把部分已经排序的数字右移以腾出空间。首先让标记的数字出列，然后将局部有序中最大的数字移动原来被标记的数字所在位置，次大的数字移动原来最大的数字所在的位置，以此类推。

手写代码

public class InsertSortDemo {

    public static int[] a = { 11, 20, 5, 4, 8, 14, 2, 10, 20, 9 };

    public static void main(String[] args) {
        // commonInsertSort();
        binaryInsertSort();
        display();
    }

    // 普通插入
    public static void commonInsertSort() {
        int count = a.length;

        for (int i = 0; i < count; i++) {
            int value = a[i];
            int j = i - 1;

            while (j >= 0 && a[j] > value) {
                a[j + 1] = a[j];
                j--;
            }

            a[j + 1] = value;
        }
    }

    // 二分法插入
    public static void binaryInsertSort() {
        int count = a.length;
        int insertValue;

        for (int i = 0; i < count; i++) {
            int start = 0;
            int end = i - 1;
            int mid;
            insertValue = a[i];

            while (start <= end) {
                mid = start + (end - start) / 2;

                if (insertValue > a[mid]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }

            for (int k = i; k > start; k--) {
                a[k] = a[k - 1];
            }

            a[start] = insertValue;
        }
    }

    public static void display() {
        int count = a.length;

        for (int i = 0; i < count; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println("");
    }
}

这里的插入排序分别为普通的插入排序和二分法插入排序。
打印输出结果。

image.png

插入排序的效率

在第一趟排序中，它最多比较一次，第二趟最多比较2次，以此类推，最后一趟最多，比较N - 1次。因此是 N * (N - 1) / 2。然而在每一趟排序发现插入点之前，平均只有全体数据项的一半进行了比较，我们除以2就是N * (N - 1) / 4。
复制的次数大致等于比较的次数。因为一次复制和一次比较的时间耗费不同，所以插入排序相对于冒泡排序快一倍，比选择排序略快。
对于已经有序或者基本有序的数据来说，插入排序要好的多。当数据有序的时候，while循环的条件总为假，所以它变成了外层循环中的一个简单的语句，执行 N - 1次。在这种情况下，算法运行时间只需要O(N）的时间。如果数据基本有序，插入排序几乎只需要O(N)的时间。
对于逆序排列的数据，每次比较和移动都会执行，所以插入排序不比冒泡排序快。