数据结构与算法——插入排序

也称为直接插入排序、简单插入排序等。插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间

算法要点

1. 将一个序列中的数据分成两个部分，从前到后依次为有序序列和无序序列
2. 遍历拿到每一个无序序列中的元素，将其与有序序列中的元素从后到前依次比较，如果逆序，则将有序序列中的数据向后移动一位，否则，将拿到的元素放在当前有序序列元素的后面
3. 直到将所有的无序序列全部插入到有序序列中

• 时间复杂度为O(n^2)
• 开始时，可以将序列中的第一个元素算作有序序列，其他的元素算作无序序列

动图演示

代码示例

package Sort;

public class Sort {
    /**
     * 插入排序(从小到大排序)
     *
     * @param data int[] 数据
     *
     * @return int[]
     **/
    public int[] insertionSort(int[] data)
    {
        //记录带插入的数据及索引
        int insertionValue;
        int insertIndex;
        for (int i = 1; i < data.length; i++) {
            insertionValue = data[i];
            insertIndex = i;
            //这里第一次写的时候用的是for，出现了很多中情况：
            //  1.如果找到了插入的位置，则插入
            //  2.如果所有的有序序列全部遍历完成，则插入到序列头部分
            // 后续改版使用while，方便了不少
            while (insertIndex > 0) {
                if (insertionValue < data[insertIndex - 1]) {
                    data[insertIndex] = data[insertIndex - 1];
                } else {
                    break;
                }
                insertIndex--;
            }
            data[insertIndex] = insertionValue;
        }
        return data;
    }
}