插入排序属于内部排序法，是对欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的算法。
1、思路实现
插入排序（Insertion sorting）的基本思想：把n个代排序的元素看为一个有序和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序中取出第一个元素，把它的排序码依次与有序元素的排序码进行比较，将它插入到有序表中适当的位置，使之成为新的有序表。（感觉有点不好理解）
2、看一下图理解
当然看图就可以知道，这个当中第一个也是不用比较的，总体的也是实现数组大小减1的次数比较。
package cn.mldn;
import java.util.Arrays;
public class insertSort {
public static void main(String[] args) {
int[] arr = {101,34,118,1};
insertSort(arr);
}
public static void insertSort(int[] arr) {
//使用逐步推导的方法讲解理解{101,34,118,1};
//第一轮，给{101,34,118,1};=>{34,101,118,1};
int insertVal = arr[1];//定义待插入的数
int insertIndex = 1 - 1;//待插入数的索引
//给insertVal 找到插入的位置，
// 1）而insertIndex >= 0这句话主要是保证了不越界
// 2）insertVal < arr[insertIndex]满足则待插入的数据还没有找到适当的位置，
// 3）上面情况符合后这种情况就要arr[insertIndex]后移一个位置
while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];//arr[insetIndex]
insertIndex--;
System.out.println("哈哈哈");
}
//当退出循环后，则插入的位置找到，insertIndex + 1，即上面的操作后，
// 数组相当于这样了{101,101,118,1}
arr[insertIndex + 1] = insertVal;
System.out.println(Arrays.toString(arr));
//第二轮
insertVal = arr[2];
insertIndex = 2 - 1;
while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];//arr[insertIndex]
insertIndex --;
System.out.println("哈哈哈");
}
arr[insertIndex + 1] = insertVal;
System.out.println(Arrays.toString(arr));
//第三轮
insertVal = arr[3];
insertIndex = 3 - 1;
while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];//arr[insertIndex]
insertIndex --;
System.out.println("哈哈哈");
}
arr[insertIndex + 1] = insertVal;
System.out.println(Arrays.toString(arr));
}
}
2、精简版
public class insertSort {
public static void main(String[] args) {
int[] arr = {101,34,118,1};
insertSort(arr);
}
public static void insertSort(int[] arr) {
System.out.println(Arrays.toString(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];//arr[insertIndex]
insertIndex --;
System.out.println("哈哈哈");
}
arr[insertIndex + 1] = insertVal;
}
System.out.println(Arrays.toString(arr));
}
}
3、从大到小版
public class insertSort {
public static void main(String[] args) {
int[] arr = new int[8];
for (int i = 0; i < 8; i++) {
arr[i] = (int)(Math.random()*80000);//生成0到80000的数
}
//2、输出时间
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) {
for (int i = 1; i < arr.length ; i++) {
int insertVal = arr[i];
int insertIndex = i - 1;
//仅仅是改变一下insertVal < arr[insertIndex]，为insertVal > arr[insertIndex]
while(insertIndex >= 0 && insertVal > arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];//arr[insertIndex]
insertIndex --;
}
arr[insertIndex + 1] = insertVal;
}
}
}
三、性能测试
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class insertSort {
public static void main(String[] args) {
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int)(Math.random()*80000);//生成0到80000的数
}
//2、输出时间
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);
}
public static void insertSort(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];//arr[insertIndex]
insertIndex --;
}
arr[insertIndex + 1] = insertVal;
}
}
}
效果：仅仅是一秒就把80000个数据排序完成了
