概念介绍

  有同学想了解插入排序,今天它来了!插入排序的核心思想是:把n个待排序的元素看成为一个有序表和一个无序表,默认开始时第一个元素为有序表中的唯一元素,剩余的n-1个元素为无序表中的元素,排序的过程是每次从无序表中取出第一个元素,通过和有序表中的元素进行对比,有序的插入到有序表中。概念有点长,如果不理解没关系,我们直接举例子进行说明。

  咱们要对[2,7,-5,30,9]这五个数使用选择排序进行排序,排序开始的时候,将序列分为有序表和无序表。

  有序表(默认为头元素):2

  无序表:7,-5,30,9。

  第一轮:我们的目的是将无序表中的第1个元素7,通过比较的方式,插入到有序表中。

      第一次,7>2,直接插入有序表的末尾,第一轮结束。

      第一轮结束后,有序表:2,7。

             无序表:-5,30,9。

  第二轮:同样的,我们的目的是将无序表中的第1个元素-5,通过比较的方式,插入到有序表中。

      第一次,-5<7,将7后移一位,记录下标,第一次后移后有序表元素序列为:2,X,7(X为插入元素的位置,如果大家不理解,可以理解为这轮比较的元素,也就是-5)。

      第二次,-5<2,将2后移一位,记录下标,第二次后移后有序表元素序列为:X,2,7,由于X已经到有序表中第一个元素的位置,将比较的元素-5插入到X中,第二轮结束。

      第二轮结束后,有序表:-5,2,7。

             无序表:30,9。

  第三轮:取无序表中第1个元素30,进行插入。

      第一次,7<30,直接插入有序表的末尾,第三轮插入结束。

      第三轮结束后,有序表:-5,2,7,30。

             无序表:9。

  第四轮:取无序表最后剩下的元素,进行插入。

      第一次,9<30,将30后移一位,第一次交换后有序表元素序列为:2,-5,7,X,30。

      第二次,7<9,不需要后移,将9插入到X所在位置。

      第四轮结束后:有序表:-5,2,7,9,30。

             无序表:无

  当无序表中没有元素时,排序结束。

代码实现

  代码的推导也是根据上述排序的过程来实现,大家可以用笔在纸上演示,再结合代码的注释,代码理解起来就很容易了。

 1 public static void insertSort(int[] arr) {
 2         // 定义:insertValue为插入的值
 3         int insertValue;
 4         // 定义:insertPreIndex为插入值的前一位下标
 5         int insertPreIndex;
 6         for (int i = 1; i < arr.length; i++) {
 7             insertValue = arr[i];
 8             insertPreIndex = i - 1;
 9             // 循环的目的是:找到插入的位置,insertValue < arr[insertPreIndex]为找到插入位置的条件
10             while (insertPreIndex >= 0 && insertValue < arr[insertPreIndex]) {
11                 // 对比之后,将较大的值往后移一位
12                 arr[insertPreIndex + 1] = arr[insertPreIndex];
13                 insertPreIndex--;
14             }
15             // 如果本来插入值就为最大值,是不需要交换的
16             if (insertPreIndex + 1 != i) {
17                 // 将插入的值放到合适的位置中
18                 arr[insertPreIndex + 1] = insertValue;
19             }
20         }
21     }

  至此,代码编写完成,Git地址:https://github.com/HollowCup/algorithms-and-data-structure,具体实现位于algorithm工程下的sort目录InsertSort,如果发现不足之处,请联系我进行更改,十分感谢!关注我,为你揭秘更多排序算法!

01-15 05:24