1、插入排序法介绍
插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
2、插入排序法思想
插入排序（Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
3、插入排序思路图
4、插入排序法应用实例
把101, 34, 119, 1 请从小到大排序
逐步推导的方式 【画图理解】
第一轮
//第一轮{101,34,119,1} ===> {34,101,119,1}; //定义待插入的数据 int insertValue = arr[1]; int insertIndex = 1-1; //即arr[1]的前面位置这个数的下标 //给insertValue找到插入的位置 //insertIndex >= 0 保证给insertValue插入位置时，不越界 //insertValue < arr[insertIndex] 待插入的数，还没有找到适当的位置 //就需要将arr[insertIndex]后移 while(insertIndex >= 0 && insertValue < arr[insertIndex]){ arr[insertIndex+1] = arr[insertIndex]; insertIndex--; } //当退出while循环的时候，说明插入的位置已经找到，insertIndex+1 arr[insertIndex+1] = insertValue; System.out.println("第一轮："); for(int i=0;i<arr.length;i++){ System.out.print(arr[i]+" "); } System.out.println();第二轮
//第二轮 //定义待插入的数据 insertValue = arr[2]; insertIndex = 2-1; //即arr[2]的前面位置这个数的下标 while(insertIndex >= 0 && insertValue < arr[insertIndex]){ arr[insertIndex+1] = arr[insertIndex]; insertIndex--; } arr[insertIndex+1] = insertValue; System.out.println("第二轮："); for(int i=0;i<arr.length;i++){ System.out.print(arr[i]+" "); } System.out.println();第三轮
//第三轮 //定义待插入的数据 insertValue = arr[3]; insertIndex = 3-1; //即arr[3]的前面位置这个数的下标 while(insertIndex >= 0 && insertValue < arr[insertIndex]){ arr[insertIndex+1] = arr[insertIndex]; insertIndex--; } arr[insertIndex+1] = insertValue; System.out.println("第三轮："); for(int i=0;i<arr.length;i++){ System.out.print(arr[i]+" "); } System.out.println();最终代码
for(int i=1;i<arr.length;i++){ //第一轮{101,34,119,1} ===> {34,101,119,1}; //定义待插入的数据 int insertValue = arr[i]; int insertIndex = i-1; //即arr[1]的前面位置这个数的下标 //给insertValue找到插入的位置 //insertIndex >= 0 保证给insertValue插入位置时，不越界 //insertValue < arr[insertIndex] 待插入的数，还没有找到适当的位置 //就需要将arr[insertIndex]后移 while(insertIndex >= 0 && insertValue < arr[insertIndex]){ arr[insertIndex+1] = arr[insertIndex]; insertIndex--; } //当退出while循环的时候，说明插入的位置已经找到，insertIndex+1 //优化 if(insertIndex+1 == i){ arr[insertIndex+1] = insertValue; } // System.out.println("第"+i+"轮："); // for(int k=0;k<arr.length;k++){ // System.out.print(arr[k]+" "); // } // System.out.println(); }测试时间
//测试80000个数据 int arr[] = new int[80000]; for(int i=0;i<80000;i++){ arr[i] = (int)(Math.random()*800000); //随机生成【0.80000】 } //写一个测试时间 Date date1 = new Date(); SimpleDateFormat simple1 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String str1 = simple1.format(date1); System.out.println("排序前的时间："+str1); insertSort(arr); Date date2 = new Date(); String str2 = simple1.format(date2); System.out.println("排序前的时间："+str2);-------------------------------------------------------------------------------------------------------------------------------------------------------------------------个人认为上面这种写法不太好理解，又学习了另一种写法，思路是一样的
【升序】 //默认第一个数是有序的，后面n-1个数据是无序的，将第二个数和第一个数进行比较，把第二个数插入到合适的位置 //此时前两个数已经是有序的，将第三个数和前两个数进行比较，把第三个数插入到合适的位置...... public static void InsertSortTest01(int[] arr){ int j; for(int i=1;i<arr.length;i++){ //当前的数比它前一个数小的时候，就将当前的数插入到合适的位置 if(arr[i]<arr[i-1]){ int temp = arr[i]; //记录当前要插入的数据 for(j=i-1;j>=0 && temp < arr[j];j--){ arr[j+1] = arr[j]; } //这个for循环出来就两个情况 //1是到数组头部了,此时j=-1 //2是temp>arr[j],那么就把temp插入到ar[j]的下一个位置 arr[j+1] = temp; } } }
