11. 插入排序，及其如何优化插入排序，以及测试它的性能

package com.qin.sort; import java.text.SimpleDateFormat; import java.util.Arrays; import java.util.Date; public class InsertSort { public static void main(String[] args) { int [] arr = {101,34,119,1}; int [] arr2 = {101,34,119,1}; insertSort(arr); insertSort2(arr2); System.out.println("====================="); //速度测试 int [] arr4 = new int [80000]; for (int i = 0 ; i < 80000 ; i++){ arr4[i] = (int)(Math.random() * 80000000);//生成[0,80000000)的随机数 } Date date1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(date1); System.out.println("排序前的时间是:"+date1Str); insertSort2(arr4); Date date2 = new Date(); String date2Str = simpleDateFormat.format(date2); System.out.println("排序后的时间是:"+date2Str); } //插入排序 public static void insertSort(int[] arr){ //使用逐步推倒的方法来讲解，便于理解 //第一轮 {101,34,119,1}=> {34,101,119,1} //定义待插入的数 int insertVal = arr[1]; int insertIndex = 1-1; //给insertVal 找到插入的位置 //1. insertIndex>=0 保证再给insertVal 找插入时，不越界 //2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入的位置 //3. 就需要将[insertIndex] 后移 while (insertIndex>=0 && insertVal < arr[insertIndex]){ arr[insertIndex+1] = arr[insertIndex]; //{101,101,119,1} insertIndex--; // 等于-1 } //当退出while循环时，说明插入的位置找到，insertIndex+1 arr[insertIndex+1] = insertVal; System.out.println("第一轮插入"); System.out.println(Arrays.toString(arr)); //第二轮 insertVal = arr[2]; insertIndex = 2-1; while (insertIndex>=0 && insertVal < arr[insertIndex]){ arr[insertIndex+1] = arr[insertIndex]; insertIndex--; } //当退出while循环时，说明插入的位置找到，insertIndex+1 arr[insertIndex+1] = insertVal; System.out.println("第二轮插入"); System.out.println(Arrays.toString(arr)); //第三轮 insertVal = arr[3]; insertIndex = 3-1; while (insertIndex>=0 && insertVal < arr[insertIndex]){ arr[insertIndex+1] = arr[insertIndex]; // 第一次while循环 {34,101,119,119} insertIndex=1 insertIndex--; // 第二次while循环 {34,101,101,119} insertIndex=0 } // 第三次while循环 {34,34,101,119} insertIndex=-1 //当退出while循环时，说明插入的位置找到，insertIndex+1 arr[insertIndex+1] = insertVal; System.out.println("第三轮插入"); System.out.println(Arrays.toString(arr)); System.out.println("======================="); } //插入排序2 public static void insertSort2(int[] arr){ for (int i = 1; i < arr.length; i++) { //定义待插入的数 int insertVal = arr[i]; int insertIndex = i-1; while (insertIndex>=0 && insertVal < arr[insertIndex]){ arr[insertIndex+1] = arr[insertIndex]; insertIndex--; } //优化 //这里我们判断是否需要赋值 if (insertIndex+1!=i){ arr[insertIndex+1] = insertVal; } //System.out.println("第"+i+"轮插入"); //System.out.println(Arrays.toString(arr)); } } }

结论：这里我们可以看出，插入排序是优于选择排序的，选择排序是优于冒泡排序的，所以插入排序是优于冒泡排序的