排序算法-插入排序

排序算法-插入排序，java实现插入排序，算法图形化图解排序步骤。

---

排序思想

1. 认定数组前n-1的元素是有序的，在拿第n个元素时，与前n-1个元素做比较，插入相应的位置
2. 开始时，从第二个元素开始拿，与第一个元素比较，比第一个元素大插在它的右边，小插到左边
3. 再拿第三个元素，与前两个元素比较，插入适当的位置，依次类推，直到数组排序完成。

算法图形化

测试数据：data[]=${arr}

代码实现

排序代码：

/**
 * @description 插入排序算法实现
 * @author dxy
 * @date 2019-12-13
 */
@Service("insertionSortService")
public class InsertionSortServiceImpl implements IInsertionSortService {

    //步骤-全
    private static Integer allStep = 0;
    //步骤-真实的交换，去除不交换的步骤
    private static Integer realStep = 0;

    /**
     * 插入排序算法：
     * 1.认定数组前n-1的元素是有序的，在拿第n个元素时，与前n-1个元素做比较，插入相应的位置
     * 2.开始时，从第二个元素开始拿，与第一个元素比较，比第一个元素大插在它的右边，小插到左边
     * 3.再拿第三个元素，与前两个元素比较，插入适当的位置，依次类推，直到数组排序完成。
     * @param
     * @throws Exception
     */
    @Override
    public List<InsertionSortResult> sort(Comparable[] arrays) throws Exception {

        //将数组随机打乱
        //StdRandom.shuffle(arrays);

        List<InsertionSortResult> resultList  = new ArrayList<>();
        //打印数组
        SortUtil.show(arrays);

        //数组长度
        int arrLength = arrays.length;
        //元素从第2个开始拿，所有遍历arrLength-1即可
        for (int i = 0; i < arrLength-1; i++) {
            //拿的元素与前面的所有元素比较
            for (int j = i+1; j > 0; j--) {
                //如果拿的元素与比较的元素小，则交换位置
                if(SortUtil.less(arrays[j], arrays[j-1])) {

                    //交换
                    SortUtil.exch(arrays, j, j - 1);
                    //打印数组
                    SortUtil.show(arrays);

                }else{

                    //由于前面的数组是有序的，在与比较元素相比大的话即已插入正确的位置，即可退出循环比较
                    break;
                }
            }
        }

        //验证是否有序
        assert SortUtil.isSorted(arrays);

        return resultList;

    }

 }

工具类：

/**
 * @description 排序工具类
 * @author dxy
 * @date 2019-12-11
 */
public class SortUtil {

    /**
     * 元素比较
     * @param var0
     * @param var1
     * @return var0<var1 则返回true
     */
    public static boolean less(Comparable var0, Comparable var1) {
        return var0.compareTo(var1) < 0;
    }

    public static boolean less(Object v, Object w, Comparator comparator) {
        return comparator.compare(v, w) < 0;
    }

    /**
     * 元素比较
     * @param var0
     * @param var1
     * @param var2
     * @return
     */
    public static boolean less(Comparable[] var0, int var1, int var2) {
        return var0[var1 - 1].compareTo(var0[var2 - 1]) < 0;
    }


    /**
     * 元素交换
     * @param var0 数组
     * @param var1 下标1
     * @param var2 下标2
     */
    public static void exch(Object[] var0, int var1, int var2) {
        Object var3 = var0[var1];
        var0[var1] = var0[var2];
        var0[var2] = var3;
    }

    /**
     * 数组是否有序
     * @param var0
     * @return
     */
    public static boolean isSorted(Comparable[] var0) {
        return isSorted(var0, 0, var0.length - 1);
    }

    public static boolean isHsorted(Comparable[] var0, int var1) {
        for(int var2 = var1; var2 < var0.length; ++var2) {
            if (less(var0[var2], var0[var2 - var1])) {
                return false;
            }
        }

        return true;
    }

    /**
     * 判断数组中元素1到元素2是否有序
     * @param var0 数组
     * @param var1 元素1
     * @param var2 元素2
     * @return
     */
    public static boolean isSorted(Comparable[] var0, int var1, int var2) {
        for(int var3 = var1 + 1; var3 <= var2; ++var3) {
            if (less(var0[var3], var0[var3 - 1])) {
                return false;
            }
        }

        return true;
    }

    /**
     * 遍历打印数组换行
     * @param var0
     */
    public static void showLn(Comparable[] var0) {
        for(int var1 = 0; var1 < var0.length; ++var1) {
            System.out.println(var0[var1]);
        }

    }

    /**
     * 遍历打印数组不换行
     * @param var0
     */
    public static void show(Comparable[] var0) {
        for(int var1 = 0; var1 < var0.length; ++var1) {
            System.out.print(var0[var1]+"  ");
        }
        System.out.println();

    }
}