InsertSort

package Sort;
/**
 * 最坏情况：当待排序序列为逆序状态，首先遍历整个序列，之后一个一个地将待插入元素放在已排好序的序列最前面，之后的所有元素都需要向后移动一位，时间复杂度为O(n^2)
 * 最好情况：当待排序序列为正序状态，则遍历完整个序列，当插入元素时，只比较一次就够了，所以时间复杂度为O(n)
 * 稳定性:  当待插入元素与有序序列中比较的元素相等时，将待插入元素直接插入在该相等元素的后面。所以，两个元素位置的前后顺序没有改变，故插入排序是稳定的
 * */

public class InsertSort {

    public static void main(String[] args) {
        int[] arr = new int[]{18, 4, 69, 3, 10, 20, 87, 33};
        insertSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }

    public static void insertSort(int[] arr) {
        if (arr.length == 1 || arr == null) {
            return;
        }
        //  从前面第二个元素开始，和前面的有序表进行比较
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i]; // 记录要插入的值，将待插入的值取出并保存在temp中，防止数据丢失
            int j = i - 1; // 从后往前遍历
            for (; j >= 0; j--) {
                if (arr[j] > temp) {
                    arr[j + 1] = arr[j]; // 后移一个位置
                } else {
                    arr[j + 1] = temp; // 直接将待插入的元素，插入有序表的尾部
                    break;
                }
            }
            arr[j+1] = temp; // 这个位置还是有点晕
        }
    }
}