【保姆级图解】插入排序 算法详解：直接插入排序、希尔排序
总体引入在盘算机科学的算法领域中，排序是一项基础且重要的操纵。它旨在将一组无序的数据元素重新分列为有序序列，以满足特定的次序要求，如升序或降序。常见的排序算法可分为差异类别，像插入排序，包罗直接插入排序和希尔排序；选择排序，有直接选择排序和堆排序；交换排序，涵盖冒泡排序和快速排序；还有归并排序 。这些算法各有特点，实用于差异的应用场景，接下来让我们深入相识它们。
https://i-blog.csdnimg.cn/direct/8432cda3311d4b78882b5e9638ee9b8f.png
插入排序引入
想象你整理扑克牌时，会从一堆牌里一张一张拿出来，按次序插到已经整理好的牌堆符合位置 。编程里的插入排序差不多也是这个原理。它把数据分成已排序和未排序两部分，从 未排序部分取元素，在已排序部分找到符合位置插入，不断重复，直到全部元素都排好序，就像把乱序的扑克牌整理成有序的一样。
https://i-blog.csdnimg.cn/direct/18921e504b5246319ee4cb8aba93f38a.png
一、直接插入排序（Insertion Sort）
算法头脑：
将数组分为“已排序”和“未排序”两部分，逐个将未排序部分的元素插入到已排序部分的精确位置。
https://i-blog.csdnimg.cn/direct/83ced2c9f1204880ad78817e8aa5a12e.gif
代码解析：
void InsertSort(int* arr, int n) {
for (int i = 0; i < n - 1; i++) {// 从第一个元素开始遍历到倒数第二个元素
int end = i; // 已排序部分的末尾索引
int tmp = arr; // 待插入元素（未排序部分的第一个元素）
while (end >= 0) { // 向前寻找插入位置
if (arr > tmp) { // 若当前元素大于待插入元素，则后移
arr = arr;
end--;
} else { // 找到合适位置，退出循环
break;
}
}
arr = tmp; // 插入元素到正确位置
}
} 步骤说明：
[*] 外层循环：遍历每个待插入元素（从第二个元素开始）。
[*] 内层循环：从后向前比较，若当前元素比待插入元素大，则将其后移。
[*] 插入操纵：找到第一个比待插入元素小的位置，将元素插入其后。
复杂度分析：
[*] 时间复杂度：
[*] 最好环境（已有序）：O(n)，只需比较无需移动。
[*] 最坏环境（逆序）：O(n²)，每次插入需移动全部已排序元素。
[*] 空间复杂度：O(1)，原地排序。
实用场景：
数据量小或基本有序时效率高，稳定且简单。
二、希尔排序（Shell Sort）
算法头脑：
希尔排序是对直接插入排序的一种改进算法，它通过将待排序的数组按照一定的隔断（称为增量）举行分组，对每组分别举行直接插入排序，逐步缩小增量，当 gap > 1 时都是预排序，⽬的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，如许就会很快。如许整体⽽⾔，可以达到优化的结果。
https://i-blog.csdnimg.cn/direct/d8aef826adf0457ab80fbd330639f38c.png
https://i-blog.csdnimg.cn/direct/c86a548eea70454db107d51d9b9baae4.png
代码解析：
void ShellSort(int* arr, int n) {
int gap = n; // 初始间隔设为数组长度
while (gap > 1) { // 循环直到间隔为1（最后一次完整插入排序）
gap = gap / 3 + 1; // 动态调整间隔（常见增量方式）
for (int i = 0; i < n - gap; i++) {// 对所有间隔分组进行插入排序
int end = i; // 当前组的已排序末尾
int tmp = arr; // 待插入元素
while (end >= 0) { // 组内插入排序
if (arr > tmp) {
arr = arr;
end -= gap; // 跨间隔移动
} else {
break;
}
}
arr = tmp; // 插入元素
}
}
} 步骤说明：
[*] 动态调整隔断：初始隔断较大，逐步缩小(gap = gap/3 + 1)大概(gap = gap/2)。
[*] 分组插入排序：对每个隔断形成的子序列举行插入排序。
[*] 最终排序：当隔断为1时，退化为尺度插入排序，此时数组已基本有序。
复杂度分析：
[*] 时间复杂度：约 O(n^1.3)，依赖增量序列的选择。
[*] 空间复杂度：O(1)，原地排序。
实用场景：
中等规模数据，对稳定性无要求，优于直接插入排序。
测试案例
void test01() {
int arr[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
int size = sizeof(arr) / sizeof(arr);
// InsertSort(arr, size);
ShellSort(arr, size);
for (int i = 0; i < size; i++) {
printf("%d ", arr);// 输出：0 1 2 3 4 5 6 7 8 9
}
} 运行结果：
无论调用哪个排序函数，最终输出均为有序数组 0 1 2 3 4 5 6 7 8 9。
总结
[*] 直接插入排序：简单稳定，得当小数据或部分有序场景。
[*] 希尔排序：插入排序的高效改进，得当中等规模数据。
理解基础排序算法的实现有助于掌握更复杂的排序技术，现实应用中可根据数据特征选择符合的算法。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]