排序算法之插入排序

概念

上篇文章我们讨论了快速排序，其核心思想是给定一个pivot, 每次将待排的序列拆分为两部分，左边序列<=pivot, 右边序列>pivot， 然后递归对左右进行排序。快速排序写的复杂点在partition上。对pivot的选择，影响到快排的时间复杂度。
本文我们将讨论插入排序。插入排序非常简单，对小的数据量很高效稳定，且只需要O(1)的辅助空间。但其时间复杂度为O(n^2) , 在最好的情况下达到O(n)。

插入排序

假如有一组乱序序列：a1, a2, a3 ... an，现在要将它从小到大的排序。

思想

1. 对将排序的数据进行遍历
2. 对单个遍历的数据，找到在已经排好序中的位置，然后插入这个位置

注：对Step 2中，如何查找某个数据在已经排好序中的位置，有一种改进的二分查找。在Java库中TimSort，就使用了该算法。这是对少量数据排序的最好算法，时间复杂度O(n log n)，但最坏的情况下O(n^2) 。在代码binaryInsertionSort方法中实现。

案列

待排序列：5， 2， 4， 6， 1， 3

insertion sort.png

代码

 public void testInsertionSort() {
        int[] arr1 = {5, 2, 4, 6, 1, 3};
        insertionSort(arr1);
        Arrays.stream(arr1).forEach(System.out :: println);
    }

    public void insertionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i ++) {
            if (arr[i + 1] > arr[i]) {
                continue;
            }
            for (int j = i + 1; j > 0; j --) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
        }
    }


    public void binaryInsertionSort(int[] arr) {
        if (arr.length == 1) {
            return;
        }

        for (int i = 0; i < arr.length - 1; i ++) {
            int left = 0;
            int right = i + 1;
            int pivot = arr[right];

            while (left < right) {
                int mid = (left + right) >>> 1;
                if (arr[mid] > pivot)
                    right = mid;
                else
                    left = mid + 1;
            }

            int n = i + 1 - left;
            System.arraycopy(arr, left, arr, left + 1, n);
            arr[left] = pivot;
        }
    }
···