插入排序

插入排序，如果你打过扑克，你就会非常熟悉：当我们摸排的时候，第一张牌是 8，第二张牌如果是 7，我们会放在 8 的前面，否则会放到后面。插入排序和这个非常类似。

我们将数组中的元素，分成“已排序区间”和“未排序区间”。

刚开始的时候，已排序区间的个数是 1. 我们从 2 开始，从右往左进行比较，如果后面的较小，就进行交换，直到后面的数字比前面的数字大，就停止比较。

如下图所示：

在第四次比较中，我们将 1 这个元素，逐步移动到了最前面。

在第五次比较中，我们将 3 这个元素，逐步移动到了下标为 1（从 0 开始） 的这个位置。

…….

代码：

public class 插入排序 {
    public static void main(String[] args) {
        int[] arr = {5, 1, 11, 2, 0, 6, 9, 4};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int num = arr[i];
            int j = i - 1;
            while (j >= 0) {
                // 如果该数, 已经比前面的数字大了,就停止循环(因为是升序).
                if (arr[j] > num) {
                    arr[j + 1] = arr[j];
                    j--;
                }
                else {
                   break;
                }
            }
            // + 1; 补偿最后 j--
            arr[j + 1] = num;
        }
    }
}

排序算法三问

1. 是原地排序算法吗？

是的。

2 是稳定的排序算法吗？

只要代码实现时，不要把相等的元素进行调换，就是稳定的。

2. 时间复杂度是多少？

最好时间复杂度，数组本身有序，啥也不干，$O(n)$.

最坏时间复杂度，全部逆序，$O(n^2)$.

平均时间复杂度，我们知道，往有序数组插入一条数据时间复杂度是 $O(n)$.，如果将整个半无序数组遍历一遍进行有序插入，那就是 $O(n^2)$.