🍎道阻且长，行则将至。🍓
🌻算法，不如说它是一种思考方式🍀
算法专栏： 👉🏻123
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中 从后向前扫描，找到相应位置并插入。插入排序包括直接插入排序和希尔排序
- 步骤：
- 将第一个元素标记为已排序
- 对于每一个未排序的元素 X：
2.1： “提取” 元素 X
2.2：i = 最后排序过元素的索引 到 0 的遍历：{
*如果当前元素 j > X：
*将排序过的元素向右移一格
*跳出循环并在此插入 X
}
- 图示：
一、ChatGPT教我插入排序
为了更好的学习排序算法和了解ChatGPT，就让ChatGPT来教我学习插入排序算法吧：
1.解释插入排序和希尔排序
插入排序是一种简单的排序算法，它通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。
具体操作是每次将一个待排序的元素插入到已经有序的元素集合中，并保持有序集合的有序性。对于一个长度为n的数组，我们可以先定义一个有序的集合只有第一个元素，然后一次将后面的元素插入到这个集合中，直到所有元素都被插入完成。希尔排序是插入排序的一种改进版。它通过将一系列间隔较大的待排序元素进行插入排序，使得原来序列中的大部分元素已经基本有序，然后逐渐缩小间隔进行插入排序，最终达到整个序列有序。
具体操作是选择一个增量序列，将数据按增量序列划分成若干子序列，对每个子序列进行插入排序，然后逐步缩小增量，重复以上步骤，直到增量为1。与插入排序相比，希尔排序的关键在于选择合适的增量序列。常用的增量序列有希尔增量、Hibbard增量、Sedgewick增量等。
2.可以更详细一点吗
当数据量不大时，插入排序是一种高效的排序方法，时间复杂度为O(n²)，若数据已经有序，则时间复杂度将会变成O(n)。插入排序主要分为直接插入排序和折半插入排序两种。直接插入排序的基本思想是，将待排序序列分成有序区和无序区。每次从无序区中取出元素，向有序区中插入，直到无序区为空。具体操作为从第二个元素开始，依次将其与前面的有序区进行比较并插入到正确位置上。折半插入排序是在直接插入排序的基础上，利用二分查找确定插入位置，进一步优化了算法。具体操作是在有序区中找到中间位置后进行比较，如果被排序元素小于中间位置的值，则在左侧有序区递归查找；如果被排序元素大于中间位置的值，则在右侧有序区递归查找。
而希尔排序是对插入排序的一种改进方法，通过将数据分组，对每个分组进行插入排序，使得每次插入可以同时将多个数据进行移动，提高了插入排序的效率。具体而言，希尔排序先将待排序的序列分成若干大小相同的子序列，对每个子序列进行插入排序，然后逐步缩小子序列的长度，直到子序列长度为1，即完成排序。希尔排序的时间复杂度约为O(n^(1.3))，相对于直接插入排序能更快地将数据变成有序状态。
3.再解释一下希尔排序步骤
希尔排序的具体实现步骤如下：
- 首先选择一个步长序列，一般是折半的方式，即首先将元素分成较少的几组，距离为gap（步长）；
- 对于每个子序列，按照插入排序的方法进行排序，即把数据插入到已排序序列中的正确位置；
- 缩小步长，重复上述操作，直到步长为1。
下面用一个例子来说明希尔排序的具体过程。
假设有一个无序序列：{10，8，6，20，4，3，22，1，0}，选择步长序列为{4，2，1}，按照上述步骤进行排序。
步长为4时（将序列分成4组）：
第一次分组：{10，4}，{8，3}，{6，22}，{20，1}，{4，0}
对每组进行插入排序：
{4，10}，{3，8}，{6，22}，{1，20}，{0，4}
对整个序列进行一次插入排序：
{0，3，4，6，1，8，10，20，4}，序列变为：{0，3，4，4，6，8，10，20，22}
步长为2时（将序列分成2组）：
第一次分组：{0，4，6，10，22}，{3，4，8，20}
对每组进行插入排序：
{0，4，6，10，22}，{3，4，8，20}
对整个序列进行一次插入排序：
{0，3，4，4，6，8，10，20，22}
步长为1时（将序列分成1组）：
对整个序列进行插入排序：
{0，3，4，4，6，8，10，20，22}
最终得到有序序列。
4.你可以进一步优化插入排序算法吗
可以通过以下两种方法进一步优化插入排序算法：
二分查找：在插入排序时，可以利用二分查找法快速定位插入位置，避免从头开始逐个比较的方法。具体而言，插入时在有序序列中查找待插入元素的插入位置，从而减少比较次数。
希尔增量：在进行插入排序时，我们可以先将待排序元素分成若干个子序列，对每个子序列进行插入排序，然后再逐步缩小子序列的长度，直到子序列长度为1。希尔排序中的增量序列可以影响排序的效率，而希尔增量序列已知是性能较优的增量序列之一。希尔增量序列的计算方法是：H(n+1) = 2 * H(n) + 1，其中H(1) = 1，n为增量序列的索引。
通过以上两种优化方法，插入排序的时间复杂度可以进一步降低，算法效率更高。
end.
二、算法实现
直接插入排序：
public class c0_insert {
public static void main(String[] args) {
int[] arr={10,8,6,20,4,3,22,1,0};
arr=insertionSort(arr);
for (int i : arr) {
System.out.print(" "+i);
}
}
public static int[] insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int preIndex = i - 1;
int current = arr[i];
while (preIndex >= 0 && current < arr[preIndex]) {
arr[preIndex + 1] = arr[preIndex];
preIndex -= 1;
}
arr[preIndex + 1] = current;
}
return arr;
}
}
希尔排序：
public class c1_insert {
public static void main(String[] args) {
int[] arr={10,8,6,20,4,3,22,1,0};
arr=shellSort(arr);
for (int i : arr) {
System.out.print(" "+i);
}
}
public static int[] shellSort(int[] arr) {
int n = arr.length;
int gap = n / 2;
while (gap > 0) {
for (int i = gap; i < n; i++) {
int current = arr[i];
int preIndex = i - gap;
// Insertion sort
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + gap] = arr[preIndex];
preIndex -= gap;
}
arr[preIndex + gap] = current;
}
gap /= 2;
}
return arr;
}
}插入排序的时间复杂度为O(n^2^)，空间复杂度为O(1)。
希尔排序的时间复杂度与所选的增量序列有关，平均时间复杂度为O(nlogn)到O(n^2^)之间，常数因子较小，性能较好。空间复杂度为O(1)。
远树带行客，孤城当落晖 — 王维
☕物有本末，事有终始，知所先后。🍭
