Java 插入排序

插入排序 O(n^2)

插入排序（Insertion Sort）的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。是稳定的排序方法。

• 时间复杂度
  1，平均和最坏情况下的，时间复杂度为：O(n^2)，从下面代码可以看出，是两个嵌套的for循环
  ps：(最坏的O(n^2)情况就是,每个数都需要跟前面的数进行交换)；
  2，最好情况下的时间复杂度为：O(n)（当前序列已排好序情况下）；

• 排序思路
  1、从头开始，往左侧对比，如果当前比左侧数小，则交换位置.
  2、经过步骤1，当前数的左侧一定是 有序的 .
  3、如果 当前数 > 左侧数 （左侧已经有序）, 那么直接跳出内层循环，继续下次即可.

代码实现：

private static void insertSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        System.out.println("排序前： " + Arrays.toString(arr));


        //1, 从角标为1 开始
        for (int i = 1; i < arr.length; i++) {

            //2，往左侧 找到比自己小的数，形成从大到小有序数列.
            for (int j = 0; j < i; j++) {

                //3，如果此时，右侧 > 左侧(左侧已经有序) ，则跳出循环
                if (arr[i] > arr[j]) {
                    break;
                }

                //4，交换位置
                if (arr[j] > arr[i]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }

        }

        System.out.println("排序后： " + Arrays.toString(arr));
    }

从代码可以看出，大致思路是将数组中的每一个元素跟他前面所有的元素相比，如果 小就交换位置，循环完所有的数据。