插入排序属于内部排序法,是对要排序的元素已插入的方式找寻这个元素的适当位置,以达到排序的目的.

算法描述

把N个待排序的元素看成为一个有序表和一个无序表,开始有序表中只有一个元素,也就是要排序的数组的第一个元素,无序表中有N-1个元素,排序的过程中每次从无序表里面取出第一个元素,把这个元素和有序表每个元素做比较,来插入到合适的位置(比如说元素是4 ,从有序表里面找到3这个元素,发现比3大,接着找,找到了6,发现比6小,那么这个元素4就插入到3和6之间)

动图演示

3.插入排序（Insertion Sort） - 图1

算法分析

最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

代码实现

1.最初不用for循环的时候

  1.     public static void main(String[] args) {
  2.         int[] arr = {5, 3, 4, 2, 1};
  5.         //使用逐步推导的方式来讲解，便利理解
  7.         doInsertSort(arr, 1);
  8.         doInsertSort(arr, 2);
  9.         doInsertSort(arr, 3);
  10.         doInsertSort(arr, 4);
  13.     }
  15.     /**
  16.      * num  排序的次数
  17.      */
  18.     private static void doInsertSort(int[] arr, int num) {
  19.         //定义待插入的数
  20.         int insertVal = arr[num];
  21.         int insertIndex = num - 1; //即arr[1]的前面这个数的下标
  23.         //给insertVal 找到插入的位置
  24.         // 如果要插入的元素比当前元素小,就接着往前查找
  25.         while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
  27.             // 比要插入的元素大,就交换一下位置,  比如说 5比3大,就交换位置为 3 ,5
  28.             arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
  29.             insertIndex--;
  30.         }
  31.         //当退出while循环时，说明插入的位置找到, insertIndex + 1
  32.         arr[insertIndex + 1] = insertVal;
  34.         System.out.println("第" + num + "轮插入");
  35.         System.out.println(Arrays.toString(arr));
  36.     }

结果:

  1. 第1轮插入
  2. [3, 5, 4, 2, 1]
  3. 第2轮插入
  4. [3, 4, 5, 2, 1]
  5. 第3轮插入
  6. [2, 3, 4, 5, 1]
  7. 第4轮插入
  8. [1, 2, 3, 4, 5]

2.使用for循环简化步骤一

  2.     public static void main(String[] args) {
  3.         int[] arr = {5, 3, 4, 2, 1};
  5.         for (int i = 1; i < arr.length ; i++) {
  6.             doInsertSort(arr, i);
  7.         }
  8.     }
  10.     /**
  11.      * num  排序的次数
  12.      */
  13.     private static void doInsertSort(int[] arr, int num) {
  14.         //定义待插入的数
  15.         int insertVal = arr[num];
  16.         int insertIndex = num - 1; //即arr[1]的前面这个数的下标
  18.     // 如果要插入的元素比当前元素小,就接着往前查找
  19.         while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
  20.        // 比要插入的元素大,就交换一下位置,  比如说 5比3大,就交换位置为 3 ,5
  21.             arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
  22.             insertIndex--;
  23.         }
  24.         //当退出while循环时，说明插入的位置找到, insertIndex + 1
  25.         arr[insertIndex + 1] = insertVal;
  27.         System.out.println("第" + num + "轮插入");
  28.         System.out.println(Arrays.toString(arr));
  29.     }

输出结果和上面的一样,就不罗列出来了

3.最终版本

  2.     public static void main(String[] args) {
  3.         int[] arr = {5, 3, 4, 2, 1};
  5.         for (int i = 1; i < arr.length ; i++) {
  6.             int insertVal = arr[i];
  7.             int insertIndex = i - 1; //即arr[1]的前面这个数的下标
  8.             // 如果要插入的元素比当前元素小,就接着往前查找
  9.             while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
  10.              // 比要插入的元素大,就交换一下位置,  比如说 5比3大,就交换位置为 3 ,5
  11.                 arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
  12.                 insertIndex--;
  13.             }
  14.             arr[insertIndex + 1] = insertVal;
  16.             System.out.println("第" + i + "轮插入");
  17.             System.out.println(Arrays.toString(arr));
  19.         }
  20.     }

输出结果和上面的一样,就不罗列出来了