数据结构与算法：直接插入排序

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。算法适用于少量数据的排序，时间复杂度O(n^2)。是稳定的排序方法。

直接插入排序的过程

默认为0位置开始是排好序的，接着0-1位置的数排序，只需判断1位置的数比0位置的数大，0-2位置数排序，需要2位置的数依次与1位置数和0位置数比较，若大于1位置的数，则0~2是排好序的，否则，2位置和1位置数交换，再和0位置数比较，在判断是否需要交换。0 - 2位置数据有序后再处理0 - 3的数据方法和前面的一样……直到整个数组有序。如果一个数组有n个元素，则需要进行n-1次的排序过程。

例如,已知待排序的一组记录是：60,71,49,11,24,3,66。7个元素需要进行6次排序。排序过程如下图示：

微信图片_20190715221452.png
微信图片_20190715221458.png

算法实现

/*
 * 默认为0位置开始是排好序的，接着0-1位置的数排序，只需判断1位置的数比0位置的数大，
 * 0-2位置数排序，需要2位置的数依次与1位置数和0位置数比较，若大于1位置的数，则0~2是排好序的，
 * 否则，2位置和1位置数交换，再和0位置数比较，在判断是否需要交换。
 * 0 - 2位置数据有序后再处理0 - 3的数据方法和前面的一样……直到整个数组有序。
 * 如果一个数组有n个元素，则需要进行n-1次的排序过程。
 * */
public static void insertSort(int[] arr) {
        if(arr == null || arr.length < 2)return;
        //需要进行n-1次的排序过程。
        for(int i = 1; i < arr.length; i++) {
            /*
             * 当前元素下标大于等于0且比其前面的元素小
             * 就交换，否则直接退出这次排序过程
             * */
            for(int j = i-1; j >=0 && arr[j+1] < arr[j]; j--) {
                int temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
        
}