【保姆级图解】插入排序 算法详解：直接插入排序、希尔排序 ...

 总体引入

在盘算机科学的算法领域中，排序是一项基础且重要的操纵。它旨在将一组无序的数据元素重新分列为有序序列，以满足特定的次序要求，如升序或降序。常见的排序算法可分为差异类别，像插入排序，包罗直接插入排序和希尔排序；选择排序，有直接选择排序和堆排序；交换排序，涵盖冒泡排序和快速排序；还有归并排序 。这些算法各有特点，实用于差异的应用场景，接下来让我们深入相识它们。
 

插入排序引入

想象你整理扑克牌时，会从一堆牌里一张一张拿出来，按次序插到已经整理好的牌堆符合位置 。编程里的插入排序差不多也是这个原理。它把数据分成已排序和未排序两部分，从 未排序部分取元素，在已排序部分找到符合位置插入，不断重复，直到全部元素都排好序，就像把乱序的扑克牌整理成有序的一样。

一、直接插入排序（Insertion Sort）

算法头脑：
将数组分为“已排序”和“未排序”两部分，逐个将未排序部分的元素插入到已排序部分的精确位置。

代码解析：

1. void InsertSort(int* arr, int n) {
2.     for (int i = 0; i < n - 1; i++) {  // 从第一个元素开始遍历到倒数第二个元素
3.         int end = i;                   // 已排序部分的末尾索引
4.         int tmp = arr[end + 1];        // 待插入元素（未排序部分的第一个元素）
5.         while (end >= 0) {             // 向前寻找插入位置
6.             if (arr[end] > tmp) {      // 若当前元素大于待插入元素，则后移
7.                 arr[end + 1] = arr[end];
8.                 end--;
9.             } else {                   // 找到合适位置，退出循环
10.                 break;
11.             }
12.         }
13.         arr[end + 1] = tmp;            // 插入元素到正确位置
14.     }
15. }

复制代码

步骤说明：

• 外层循环：遍历每个待插入元素（从第二个元素开始）。
  
• 内层循环：从后向前比较，若当前元素比待插入元素大，则将其后移。
  
• 插入操纵：找到第一个比待插入元素小的位置，将元素插入其后。
  

复杂度分析：

• 时间复杂度：
  
  
  
  • 最好环境（已有序）：O(n)，只需比较无需移动。
    
  • 最坏环境（逆序）：O(n²)，每次插入需移动全部已排序元素。
    
  
  
• 空间复杂度：O(1)，原地排序。
  

实用场景：
数据量小或基本有序时效率高，稳定且简单。

---

二、希尔排序（Shell Sort）

算法头脑：
希尔排序是对直接插入排序的一种改进算法，它通过将待排序的数组按照一定的隔断（称为增量）举行分组，对每组分别举行直接插入排序，逐步缩小增量，当 gap > 1 时都是预排序，⽬的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，如许就会很快。如许整体⽽⾔，可以达到优化的结果。

代码解析：

1. void ShellSort(int* arr, int n) {
2.     int gap = n;                       // 初始间隔设为数组长度
3.     while (gap > 1) {                  // 循环直到间隔为1（最后一次完整插入排序）
4.         gap = gap / 3 + 1;            // 动态调整间隔（常见增量方式）
5.         for (int i = 0; i < n - gap; i++) {  // 对所有间隔分组进行插入排序
6.             int end = i;               // 当前组的已排序末尾
7.             int tmp = arr[end + gap]; // 待插入元素
8.             while (end >= 0) {        // 组内插入排序
9.                 if (arr[end] > tmp) {  
10.                     arr[end + gap] = arr[end];
11.                     end -= gap;        // 跨间隔移动
12.                 } else {
13.                     break;
14.                 }
15.             }
16.             arr[end + gap] = tmp;      // 插入元素
17.         }
18.     }
19. }

复制代码

步骤说明：

• 动态调整隔断：初始隔断较大，逐步缩小(gap = gap/3 + 1)大概(gap = gap/2)。
  
• 分组插入排序：对每个隔断形成的子序列举行插入排序。
  
• 最终排序：当隔断为1时，退化为尺度插入排序，此时数组已基本有序。
  

复杂度分析：

• 时间复杂度：约 O(n^1.3)，依赖增量序列的选择。
  
• 空间复杂度：O(1)，原地排序。
  

实用场景：
中等规模数据，对稳定性无要求，优于直接插入排序。

---

测试案例

1. void test01() {
2.     int arr[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
3.     int size = sizeof(arr) / sizeof(arr[0]);
4.     // InsertSort(arr, size);
5.      ShellSort(arr, size);
6.     for (int i = 0; i < size; i++) {
7.         printf("%d ", arr[i]);  // 输出：0 1 2 3 4 5 6 7 8 9
8.     }
9. }

复制代码

运行结果：
无论调用哪个排序函数，最终输出均为有序数组 0 1 2 3 4 5 6 7 8 9。

---

总结

• 直接插入排序：简单稳定，得当小数据或部分有序场景。
  
• 希尔排序：插入排序的高效改进，得当中等规模数据。
  

理解基础排序算法的实现有助于掌握更复杂的排序技术，现实应用中可根据数据特征选择符合的算法。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。