排序算法-插入排序

插入排序的思想是，先看数组的第一个元素，把它作为一个有序序列，再看第二个元素，与第一个元素进行比较与交换，这样子前两个元素就成为了一个有序序列。继续看第三个元素，与第二个、第一个元素进行比较、交换，让前三个元素形成一个有序序列。以此类推...
但是需要注意的是，当我们要把第n的元素插入时，需要先与第n-1个元素比较，如果不小于说明第n个元素的位置已经找到了，为什么呢，因为第n个元素前面的元素已经是一个有序序列了，第n个元素不大于前面的元素，那么它也不大于其他前面的元素，所以它所在的位置就是加入它然后成为一个有序序列的位置。

    // 插入排序
    public static void insertionSort(int[] arr) {
        // 从1开始循环，第一个元素默认有序
        for (int i = 1; i < arr.length; i++) {
            // 为下标为i的元素找它的位置
            for (int j = i; j > 0; j--) {
                // 如果下标为i的元素比它前面的元素小
                if (arr[j] < arr[j - 1]) {
                    // 与它前面的元素交换
                    // 这样子下标为i的元素就到了它的前一个元素的位置
                    int swaper = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = swaper;
                } else {
                    // 如果不满足就说明已经找到了位置
                    // 因为它前面的元素组成的序列已经是有序的了
                    break;
                }
            }
        }
    }

通过上面的代码，我们发现其中有可以优化的地方
交换操作要执行三个语句，我们其实不需要这么多的交换操作，只需要把当前要插入的数字保存起来，然后看前面的数字是否大于这个数字，如果大于直接覆盖这个值就好了，具体看代码。

    // 插入排序的优化版本
    public static void insertionSort(int[] arr) {
        // 从1开始循环，第一个元素默认有序
        for (int i = 1; i < arr.length; i++) {
            // 保存需要插入元素的值
            int temp = arr[i];
            // j为要插入元素的位置
            int j;
            for (j = i; j > 0; j--) {
                // 如果下标为i的元素比它前面的元素小
                if (temp < arr[j - 1]) {
                    arr[j] = arr[j - 1];
                } else {
                    // 如果不满足就说明已经找到了位置
                    // 因为它前面的元素组成的序列已经是有序的了
                    break;
                }
            }
            arr[j] = temp;    
        }
    }

这样子我们循环里就只有简单的赋值操作了，提高了效率。

对比选择排序，不能有效的利用元素本来的部分有序这个性质，所以在基本有序的序列里，插入排序的效率十分高。