Java数据结构与算法之插入排序详解

什么是插入排序？

插入排序是一种简单且常用的排序算法，其基本思想是将未排序的元素一个一个地插入到已经排序好的有序序列中。

插入排序的步骤

1. 首先确定一个将要被排序的数组；
2. 从第二个元素开始，将其与排序好的子数组从后往前依次进行比较；
3. 如果发现当前元素比排序好的子数组中的某个元素小，则将该元素插入到该元素的后面；
4. 重复步骤2-3，直到所有元素都插入到有序序列中。

插入排序的示例

示例1

假设我们要将一个未排序的数字序列按照从小到大的顺序进行排序：

4, 1, 9, 3, 7, 6

首先，我们将第一个数字4看作一个有序子数组，然后从第二个数字1开始，依次将其插入到有序子数组中。第一次插入操作后，数组变成了：

1, 4, 9, 3, 7, 6

此时，有序子数组中有两个元素1和4。接下来，我们将第三个数字9插入到有序子数组中。由于9比4大，所以9不用做任何操作，数组保持不变：

1, 4, 9, 3, 7, 6

接下来，我们将第四个数字3插入到有序子数组中。由于3比9小，所以我们需要将9向后移动一个位置，并将3插入到原来9的位置：

1, 4, 3, 9, 7, 6

继续上述操作，最后的有序数组为：

1, 3, 4, 7, 9, 6
1, 3, 4, 6, 7, 9  //最终的有序数组

示例2

假设我们要将一个未排序的字符串数组按照从A到Z的顺序进行排序：

"C", "A", "D", "F", "H", "B", "G", "E"

首先，我们将第一个字符串C看作一个有序子数组，然后从第二个字符串A开始，依次将其插入到有序子数组中。第一次插入操作后，数组变成了：

A, C, D, F, H, B, G, E

此时，有序子数组中有两个元素A和C。接下来，我们将第三个字符串D插入到有序子数组中。由于D比C大，所以D不用做任何操作，数组保持不变：

A, C, D, F, H, B, G, E

接下来，我们将第四个字符串F插入到有序子数组中。由于F比D大，所以F不用做任何操作，数组保持不变：

A, C, D, F, H, B, G, E

接下来，我们将第五个字符串H插入到有序子数组中。由于H比F大，B和G同理，所以需要将这三个字符串向后移动一个位置，并将H插入到原来G的位置：

A, C, D, F, B, G, H, E

接下来，我们将第六个字符串B插入到有序子数组中。由于B比D小，所以我们需要将D, F, H, G, E 向后移动一个位置，并将B插入到原来D的位置：

A, B, C, D, F, H, G, E

继续上述操作，最后的有序数组为：

A, B, C, D, E, F, G, H  //最终的有序数组