老狗啃骨头之算法-插入排序

插入排序（Insertion Sort）

  我们说插入排序，一般是在说直接插入排序，插入排序是一种最直观最简单的排序算法。

  插入排序的算法原理是依次将未排序的数据元素插入已完成排序的有序数列，如此往复，最终完成所有数据的排序。

1：第一位元素由于只有一个，可以看作天然有序，所以从第二位开始；
2：依次，取当前元素向前遍历做对比，如被扫描到的元素大于对比元素，则后移；
3：如被扫描到的元素小于或等于对比元素，则不再向前遍历，插入对比元素；
4：重复2、3步骤，直至所有元素排序结束。

import java.util.Arrays;

/** 
* @author    :Veiking
* @version    :2020年10月15日
* 说明        :直接插入排序算法
*/
public class InsertionSort {
    /**
     * 直接插入排序
     * @param arrays
     * @return
     */
    public static int[] sort(int[] arrays) {
        int temp;
        int index;
        // 从第一个元素开始，随着坐标往后游走，每次操作之后，游标之前的数据元素都是有序的
        for(int i=1; i 0 && temp < arrays[index-1]) {
                arrays[index] = arrays[index-1];
                index--;
            }
            // 当这个逐一对比的元素遇到小于或等于自己的前邻，就找到了它的位置，插入
            arrays[index] = temp;
            // System.out.println("第"+i+"次插入操作结果："+Arrays.toString(arrays));
        }
        return arrays;
    }

    // 执行
    public static void main(String[] args) {
        int[] input = new int[]{3, 7, 2, 6, 1, 5, 4};
        System.out.println("样本初始样本数据："+Arrays.toString(input));
        int[] output = InsertionSort.sort(input);
        System.out.println("插入排序结果数据："+Arrays.toString(output));

    }
}
;>

  我们这里讲的是最基础的插入排序算法，在实际运用中，有种优化过的叫二分插入排序，效率上会提高不少。二分插入排序的核心，就是在遍历之前已完成排序做元素插入的时，找这个插入位置的时候，升级运用二分查找算。
  二分查找算法，以后有机会可以详解，眼下我们看看他的代码实现：

    /**
     * 二分查找插入排序
     * @param arrays
     * @return
     */
    public static int[] dichotomySort(int[] arrays) {
        int temp;
        // 从第一个元素开始，随着坐标往后游走，每次操作之后，游标之前的数据元素都是有序的
        for(int i=1; iinsertIndex) {
                    arrays[subEndIndex] = arrays[subEndIndex-1];
                    subEndIndex--;
                }
            }
            // 处理完之后，插入元素值
            arrays[insertIndex] = temp;
            // System.out.println("第"+i+"次插入操作结果："+Arrays.toString(arrays));
        }
        return arrays;
    }

    /**
     * 核心思想是二分查找，略改造
     * @param arrays
     * @param current
     * @param tempValue
     * @return
     */
    public static int dichotomySearch(int[] arrays, int current, int tempValue) {
        int begin = 0;
        int end = current;
        int middle = 0;

        // 如对比值小于有序数列首元素，则插入位置在首位
        if(tempValue < arrays[begin] ){
            return begin;                
        }
        // 如对比值大于有序数列尾元素，则插入位置在尾数+1，其实也就是当前位置本身，不用动
        if(tempValue > arrays[end]){
            return end+1;                
        }
        // 如查找到等值元素，则位置+1
        while(begin <= end){
            middle = (begin + end) / 2;
            if(arrays[middle] > tempValue){
                //比关键字大则关键字在左区域
                end = middle - 1;
            }else if(arrays[middle] < tempValue){
                //比关键字小则关键字在右区域
                begin = middle + 1;
            }else{
                return middle+1;
            }
        }
        // 如未找到等值，则取前小后大位置加1，为需要插入当前数据的位置
        return  (begin + end) / 2 + 1;
    }
;>

  由于二分查找插算法，不是连续性的遍历，如有等值元素，就有可能导致他们的相对顺序发生改变，故二分插入排序是不稳定的排序算法。

  直接插入排序算法的基本性能，归纳如下图：

1、 时间复杂度

  插入排序，其核心是保证之前每轮处理过的元素都是有序的，只要把当前数据元素插入合适的位置即可，当数据元素本身就是正序的，则排序只需轮一遍，什么都不用做，也就是说，插入排序的最优时间复杂度为O(n)；
  最悲催的情况是这个样本数据正好是倒序，每一轮前面的数据都要往后移，且一个不少的从最后遍历到最前，此时数据元素的对比次数为n×（n-1）/2次，故最坏情况下时间复杂度为O(n2)；至于平均来说，插入排序算法的平均时间复杂度为O(n2)。)；至于平均来说，插入排序算法的平均时间复杂度为O(n2)。
  这里要注意一点：待排数据越接近正序，插入排序的算法性能越好；反之则差。

2、 空间复杂度

  直接插入排序算法，只需额外两个变量，用来存放当前元素及其下标，故认为插入排序算法的空间复杂度为：O(1)。

2、稳定性

  我们通过上边的图解和程序可以看出，在插入排序中，往前遍历的时候，遇到等值的元素就直接插入结束这一轮了，也就是说，经过排序，这些数据元素的相对顺序是不受影响的，所以插入排序属于稳定的排序算法。