概念

上篇文章我們討論了快速排序，其核心思想是給定一個(gè)pivot, 每次將待排的序列拆分為兩部分，左邊序列<=pivot, 右邊序列>pivot， 然后遞歸對(duì)左右進(jìn)行排序?？焖倥判?qū)懙膹?fù)雜點(diǎn)在partition上。對(duì)pivot的選擇，影響到快排的時(shí)間復(fù)雜度。
本文我們將討論插入排序。插入排序非常簡(jiǎn)單，對(duì)小的數(shù)據(jù)量很高效穩(wěn)定，且只需要O(1)的輔助空間。但其時(shí)間復(fù)雜度為O(n^2) , 在最好的情況下達(dá)到O(n)。

插入排序

假如有一組亂序序列：a1, a2, a3 ... an，現(xiàn)在要將它從小到大的排序。

思想

1. 對(duì)將排序的數(shù)據(jù)進(jìn)行遍歷
2. 對(duì)單個(gè)遍歷的數(shù)據(jù)，找到在已經(jīng)排好序中的位置，然后插入這個(gè)位置

注：對(duì)Step 2中，如何查找某個(gè)數(shù)據(jù)在已經(jīng)排好序中的位置，有一種改進(jìn)的二分查找。在Java庫中TimSort，就使用了該算法。這是對(duì)少量數(shù)據(jù)排序的最好算法，時(shí)間復(fù)雜度O(n log n)，但最壞的情況下O(n^2) 。在代碼binaryInsertionSort方法中實(shí)現(xiàn)。

案列

待排序列：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;
        }
    }
···