[数据结构与算法]插入排序以及改进

插入排序

思想：用后一项元素与当前项进行比较，如果后一项<当前项，交换位置，保证每一次遍历最小元素归位

插入排序：

/**
     * 插入排序
     * 用后一项元素与当前项进行比较，如果后一项<当前项，交换位置，保证每一次遍历最小元素归位
     * 此处：从小到大排序
     * @param array
     */
    public static void insertSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            //后一项元素 j = i +1;
            for (int j = i + 1; j > 0 ; j--) {
                //后一项与当前项比较
                if(array[j] < array[j - 1]){
                    Swap.swap(array,j,j-1);
                }
            }
        }
    }

改进：

 /**
     * 改进
     * 第一次遍历时直接从i=1开始，默认第0项已经归位
     * @param array
     */
    public static void insertSort2(int[] array){
        //i=1 : 默认第0项已经归位
        for (int i = 1; i < array.length; i++) {
            int j = 0;
            int current =  array[i];
            // i-1 当前项的上一项，上一项与当前项比较满足: array[j] > current
            for (j = i - 1; j >= 0 && array[j] > current ; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = current;
        }
    }

示例：

public class InsertSort {
    public static void main(String[] args) {
//        insertSort(Swap.array);
        insertSort2(Swap.array);
        Swap.print(Swap.array);
    }

    /**
     * 插入排序
     * 用后一项元素与当前项进行比较，如果后一项<当前项，交换位置，保证每一次遍历最小元素归位
     * 此处：从小到大排序
     * @param array
     */
    public static void insertSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            //后一项元素 j = i +1;
            for (int j = i + 1; j > 0 ; j--) {
                //后一项与当前项比较
                if(array[j] < array[j - 1]){
                    Swap.swap(array,j,j-1);
                }
            }
        }
    }

    /**
     * 改进
     * 第一次遍历时直接从i=1开始，默认第0项已经归位
     * @param array
     */
    public static void insertSort2(int[] array){
        //i=1 : 默认第0项已经归位
        for (int i = 1; i < array.length; i++) {
            int j = 0;
            int current =  array[i];
            // i-1 当前项的上一项，上一项与当前项比较满足: array[j] > current
            for (j = i - 1; j >= 0 && array[j] > current ; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = current;
        }
    }
}

工具:

public class Swap {

    /**
     * 数组
     */
    static int[] array = {8,2,5,9,3,10,22,1,87};


    /**
     * 交换
     * @param array 数组
     * @param x 交换元素下标
     * @param y 交换元素下标
     */
    public static void swap(int[] array,int x,int y){
        int temp = array[x];
        array[x] = array[y];
        array[y] = temp;
    }

    /**
     * 打印数组元素 遍历
     * @param array
     */
    public static void print(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.print(" " + array[i]);
        }
    }
}