本文共 3598 字,大约阅读时间需要 11 分钟。
插入式排序属于内部排序法,是对于欲排序的元素以插入的方式找寻该元素的适当位置,以达到排序的目的。
插入排序(InsertionSorting)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表,
开始时有序表中只包含一个元素,
无序表中包含有n-1个元素,
排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。
package com.sukang.sort;import java.text.SimpleDateFormat;import java.util.Arrays;import java.util.Date;/** * @description: * @author: sukang * @date: 2020-07-09 9:02 */public class InsertSort { public static void main(String[] args) { //创建要给80000个的随机的数组 int[] arr = new int[80000]; for (int i = 0; i < 80000; i++) { arr[i] = (int)(Math.random()*8000000);//生成一个[0,8000000)数 } //没排序之前数组遍历 System.out.println("排序前的数组" + Arrays.toString(arr)); Date date1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(date1); System.out.println("排序前的时间是=" + date1Str); insertSort(arr); Date date2 = new Date(); String date2Str = simpleDateFormat.format(date2); System.out.println("排序后的时间是="+date2Str); //排序之后数组遍历 System.out.println("排序后的数组" + Arrays.toString(arr)); } public static void insertSort(int[] arr){ int insertVal = 0; int insertIndex = 0; for (int i = 1; i < arr.length; i++) { //定义待插入的数 insertVal = arr[i]; insertIndex = i-1;//即arr[1]的前面这个数的下标 //给insertVal找到插入的位置 //说明 //1.insertIndex>=0保证在给insertVal找插入位置,不越界 //2.insertVal= 0 && insertVal < arr[insertIndex]){ arr[insertIndex + 1] = arr[insertIndex];//arr[insertIndex] insertIndex--; } //当退出while循环时,说明插入的位置找到,insertIndex+1 //这里我们判断是否需要赋值 if(insertIndex + 1 != i){ arr[insertIndex + 1] = insertVal; } /* //使用逐步推导的方式来讲解,便于理解 //第1轮{101,34,119,1}; => {34,101,119,1} //{101,34,119,1}; => {101,101,119,1} //定义待插入的数 int insertVal = arr[1]; int insertIndex = 1-1;//即arr[1]的前面这个数的下标 //给insertVal找到插入的位置 //说明 //1.insertIndex >= 0保证在给insertVal找插入位置,不越界 //2.insertVal < arr[insertIndex]待插入的数,还没有找到插入位置 //3.就需要将arr[insertIndex]后移 while(insertIndex >= 0 && insertVal < arr[insertIndex]){ arr[insertIndex + 1] = arr[insertIndex];//arr[insertIndex] insertIndex--; } //当退出while循环时,说明插入的位置找到,insertIndex + 1 //举例:理解不了,我们一会debug arr[insertIndex + 1] = insertVal; System.out.println("第1轮插入"); System.out.println(Arrays.toString(arr)); //第2轮 insertVal = arr[2]; insertIndex = 2-1; while(insertIndex >= 0 && insertVal < arr[insertIndex]) { arr[insertIndex+1] = arr[insertIndex];//arr[insertIndex] insertIndex--; } arr[insertIndex + 1] = insertVal; System.out.println("第2轮插入"); System.out.println(Arrays.toString(arr)); //第3轮 insertVal = arr[3]; insertIndex = 3-1; while(insertIndex >= 0 && insertVal < arr[insertIndex]){ arr[insertIndex + 1] = arr[insertIndex];//arr[insertIndex] insertIndex--; } arr[insertIndex + 1] = insertVal; System.out.println("第3轮插入"); System.out.println(Arrays.toString(arr)); */ } }}
运行结果
转载地址:http://konti.baihongyu.com/