插入排序 | FloatingDream🌞

Insert Sort 排序算法——插入排序

基本介绍

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的

思路图解图

代码

算法代码

    //插入排序
    public static void insertSorting(int [] arr){

        for( int i = 1; i < arr.length; i++) {
            //定义待插入的数
            int insertValue = arr[ i ];
            int insertIndex = i - 1;

            //给insetValue找到插入的位置
            while (insertIndex >= 0 && insertValue < arr[ insertIndex ]) {
                //insertIndex >= 0 保证不越界，
                // insertValue < arr[ insertIndex ]判断待插入的数是否找到合适位置
                //满足，则进行交换
                arr[ insertIndex + 1 ] = arr[ insertIndex ];
                insertIndex--;


            }
            //当while退出说明找到合适的位置
            if ( insertIndex!=i-1 ) {
                arr[ insertIndex + 1 ] = insertValue;
            }
//            System.out.println ( "第"+i+"轮结果"+Arrays.toString ( arr ) );

        }
        System.out.println ( Arrays.toString ( arr ) );
    }

性能测试

public class InsertSorting {
    public static void main ( String[] args ) {
//        int[] arr = {101, 34, 119, 1};
//        insertSorting ( arr );
        //创建80000个数据的数组
        int arr[] = new int[ 80000 ];
        randomArr ( arr );
        System.out.println ("插入排序所用时间" );
        String date1String = Date ( );
        System.out.println ("排序前时间是："+date1String );
        insertSorting ( arr );
        String date2String = Date ( );
        System.out.println ("排序后时间是："+date2String );
    }

    //插入排序
    public static void insertSorting(int [] arr){

        for( int i = 1; i < arr.length; i++) {
            //定义待插入的数
            int insertValue = arr[ i ];
            int insertIndex = i - 1;

            //给insetValue找到插入的位置
            while (insertIndex >= 0 && insertValue < arr[ insertIndex ]) {
                //insertIndex >= 0 保证不越界，
                // insertValue < arr[ insertIndex ]判断待插入的数是否找到合适位置
                //满足，则进行交换
                arr[ insertIndex + 1 ] = arr[ insertIndex ];
                insertIndex--;


            }
            //当while退出说明找到合适的位置
            if ( insertIndex!=i-1 ) {
                arr[ insertIndex + 1 ] = insertValue;
            }
//            System.out.println ( "第"+i+"轮结果"+Arrays.toString ( arr ) );

        }
//        System.out.println ( Arrays.toString ( arr ) );
    }
    private static void randomArr ( int[] arr ) {
        for(int i = 0; i < arr.length;i++){
            arr[ i ] = (int) ( Math.random ( ) * 8000000 );  //会生成【0，8000000）直接的数
        }
    }

    /**
     * 将此时调用函数的时间格式化打出来
     * @return 年-月-日 时-分秒
     */
    private static String Date ( ) {
        Date date1 = new Date ( );  //调函数的当前时间
        SimpleDateFormat simpleFormatter = new SimpleDateFormat ( "HH:mm:ss" );//格式化
        return simpleFormatter.format(date1 );
    }
}