排序算法-插入排序

一、插入排序法介绍

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

二、插入排序法思想

插入排序（Insertion Sorting）的基本思想是：把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排 序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

三、插入排序思路图

排序算法-插入排序 - 图1
可以理解成

四、插入排序法应用实例

有一群小牛, 考试成绩分别是 101, 34, 119, 1 请从小到大排序
1.使用逐步推导的方式来讲解，便利理解

  1. public class InsertSort {
  2.     public static void main(String[] args) {
  3.         int[] arr = {101, 34, 119, 1};
  4.         insertSort(arr); //调用插入排序算法
  5.         // System.out.println(Arrays.toString(arr));
  6.     }
  8.     //插入排序
  9.     public static void insertSort(int[] arr) {
  10.         //使用逐步推导的方式来讲解，便利理解
  11.         //第 1 轮 {101, 34, 119, 1}; => {34, 101, 119, 1}
  12.         //{101, 34, 119, 1}; => {101,101,119,1}
  13.         //定义待插入的数
  14.         int insertVal = arr[1];
  15.         int insertIndex = 1 - 1; //即 arr[1]的前面这个数的下标
  16.         //给 insertVal 找到插入的位置
  17.         //说明
  18.         //1. insertIndex >= 0 保证在给 insertVal 找插入位置，不越界
  19.         //2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
  20.         //3. 就需要将 arr[insertIndex] 后移
  21.         while(insertIndex >= 0 && insertVal < arr[insertIndex] ) {
  22.             arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
  23.             insertIndex--;
  24.         }
  25.         //当退出 while 循环时，说明插入的位置找到, insertIndex + 1
  26.         //理解不了，可以 debug
  27.         arr[insertIndex + 1] = insertVal;
  28.         System.out.println("第 1 轮插入");
  29.         System.out.println(Arrays.toString(arr));
  31.         //第 2 轮
  32.         insertVal = arr[2];
  33.         insertIndex = 2 - 1;
  34.         while(insertIndex >= 0 && insertVal < arr[insertIndex] ) {
  35.             arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
  36.             insertIndex--;
  37.         }
  38.         arr[insertIndex + 1] = insertVal;
  39.         System.out.println("第 2 轮插入");
  40.         System.out.println(Arrays.toString(arr));
  42.         //第 3 轮
  43.         insertVal = arr[3];
  44.         insertIndex = 3 - 1;
  45.         while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
  46.             arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
  47.             insertIndex--;
  48.         }
  49.         arr[insertIndex + 1] = insertVal;
  50.         System.out.println("第 3 轮插入");
  51.         System.out.println(Arrays.toString(arr));
  52.     }
  53. }

2.使用 for 循环来把代码简化

  1. public class InsertSort {
  2.     public static void main(String[] args) {
  3.         int[] arr = {101, 34, 119, 1, -1, 89};
  4.         insertSort(arr); //调用插入排序算法
  5.         //System.out.println(Arrays.toString(arr));
  6.     }
  8.     //插入排序
  9.     public static void insertSort(int[] arr) {
  10.         int insertVal = 0;
  11.         int insertIndex = 0;
  12.         //使用 for 循环来把代码简化
  13.         for(int i = 1; i < arr.length; i++) {
  14.             //定义待插入的数
  15.             insertVal = arr[i];
  16.             insertIndex = i - 1; // 即 arr[1]的前面这个数的下标
  17.             // 给 insertVal 找到插入的位置
  18.             // 说明
  19.             // 1. insertIndex >= 0 保证在给 insertVal 找插入位置，不越界
  20.             // 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
  21.             // 3. 就需要将 arr[insertIndex] 后移
  22.             while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
  23.                 arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
  24.                 insertIndex--;
  25.             }
  26.             // 当退出 while 循环时，说明插入的位置找到, insertIndex + 1
  27.             // 举例：理解不了，我们一会 debug
  28.             //这里我们判断是否需要赋值
  29.             if(insertIndex + 1 != i) {
  30.                 arr[insertIndex + 1] = insertVal;
  31.             }
  32.             System.out.println("第"+i+"轮插入");
  33.             System.out.println(Arrays.toString(arr));
  34.         }
  35.     }
  36. }