常用排序算法之插入排序

目录
前言
一、基本原理
1.算法步调
2.动画演示
3.插入排序的实今世码
二、插入排序的时间复杂度
1. 时间复杂度
1.最优时间复杂度
2.最差时间复杂度
3.平均时间复杂度
2. 空间复杂度
三、插入排序的优缺点
1.优点
2.缺点
四、插入排序的改进与变种
五、插入排序的应用场景
六、总结

---

前言

        插入排序（Insertion Sort）是一种简单且直观的排序算法，常用于小规模数据的排序或作为其他复杂排序算法的一部门（如快速排序的小数组优化）。
        本文将详细先容插入排序的基本原理、实今世码、时间复杂度及其适用场景，资助你轻松把握这一算法。
一、基本原理

        插入排序的核心思想是将数组分为已排序部门和未排序部门。通过逐一从未排序部门取出元素，将其插入到已排序部门的符合位置，最终完成排序。
1.算法步调

        1. 从数组的第二个元素开始，视为当前需要插入的元素。
        2. 从已排序部门的最后一个元素开始比力，如果当前元素较小，则将已排序部门元素向右移动。
        3. 重复上述步调，直到找到插入位置，将当前元素插入。
        4. 对剩余的未排序部门重复以上步调，直至整个数组有序。
2.动画演示

        这里我写了一个程序用来演示直接插入算法的过程。
        假如我要进行排序的数据元素分别为5，3，, 8，6，2，7，4，1。
        初始的时间，我们已排序中的部门中的数据元素利用绿色表现，未排序的利用蓝色表现。

图1.初始状态

        初始状态下，我们把第一个数据元素看做一个已经排列好的部门。
        同时把第二个数据元素作为下次要插入的数据元素。
        

图2.插入排序的动画演示

        我们以上面的数组为例看一下具体的过程：
        5，3, 8，6，2，7，4，1
1.第一轮
        起首确定5是已经排列好的，我们将3进行插入操纵。将3插入到仅有一个数据元素为5的数组中，显然5比3大，我们将3插入到5的前面。至此第一轮插入竣事。此时的数组为{3,5,8,6,2,7,4,1}。
2.第二轮
        在上一轮中，已排序的区间为{3,5},如今我们将8拿出来和前面排列好的部门进行比力。因为5<8,依次已排序区间应该为{3,5,8}。第二轮竣事，此时排序依然是{3,5,8,6,2,7,4,1}。
2.第二轮
        在上一轮中，已排序的区间为{3,5},如今我们将8拿出来和前面排列好的部门进行比力。因为5<8,依次已排序区间应该为{3,5,8}。第二轮竣事，此时排序依然是{3,5,8,6,2,7,4,1}。
3.第三轮
        在上一轮中，已排序的区间为{3,5,8},如今我们将6拿出来和前面排列好的部门进行比力。因为8>6,我们在把6和前面的一个数据元素5比力，5<6，把6查到5反面,依次已排序区间应该为{3,5,6，8}。第二轮竣事，此时排序依是{3,5,6,8,2,7,4,1}。
4.第四轮
        在上一轮中，已排序的区间为{3,5,6,8},如今我们将2拿出来和前面排列好的部门进行比力。具体的比力过程和上一轮相同，这里不重复了，此时排序是{2,3,5,6,8,7,4,1}。
5.第五轮
        在上一轮中，已排序的区间为{2,3,5,6,8},如今我们将7拿出来和前面排列好的部门进行比力。具体的比力过程和上一轮相同，这里不重复了，此时排序是{2,3,5,6,7,8,4,1}。
3.第六轮
        在上一轮中，已排序的区间为{2,3,5,6,7,8},如今我们将4拿出来和前面排列好的部门进行比力。具体的比力过程和上一轮相同，这里不重复了，此时排序是{2,3,4,5,6,7,8,1}。
3.第三轮
        在上一轮中，已排序的区间为{2,3,4,5,6,7,8},如今我们将1拿出来和前面排列好的部门进行比力。具体的比力过程和上一轮相同，这里不重复了，此时排序是{1,2,3,4,5,6,7,8}
      

3.插入排序的实今世码

        以下是插入排序的 C语言实现：

1. #include <stdio.h>
2. // 插入排序函数
3. void insertionSort(int arr[], int n) {
4.     for (int i = 1; i < n; i++) {
5.         int key = arr[i]; // 当前要插入的元素
6.         int j = i - 1;
8.         // 将比 key 大的元素向右移动
9.         while (j >= 0 && arr[j] > key) {
10.             arr[j + 1] = arr[j];
11.             j--;
12.         }
14.         // 插入 key 到正确的位置
15.         arr[j + 1] = key;
17.         // 打印当前排序步骤
18.         printf("第 %d 步: ", i);
19.         for (int k = 0; k < n; k++) {
20.             printf("%d ", arr[k]);
21.         }
22.         printf("\n");
23.     }
24. }
25. int main(int argc, const char * argv[]) {
26.     int arr[] = {5, 3, 8, 6, 2, 7, 4, 1};
27.     int n = sizeof(arr) / sizeof(arr[0]);
29.     printf("原始数组: ");
30.     for (int i = 0; i < n; i++) {
31.         printf("%d ", arr[i]);
32.     }
33.     printf("\n");
35.     // 执行插入排序
36.     insertionSort(arr, n);
38.     // 打印排序后的数组
39.     printf("排序后数组: ");
40.     for (int i = 0; i < n; i++) {
41.         printf("%d ", arr[i]);
42.     }
43.     printf("\n");
44.    
45.    
46.     return 0;
47. }

复制代码

二、插入排序的时间复杂度

1. 时间复杂度

1.最优时间复杂度

        当数组已经有序时，每次插入只需比力一次，无需移动元素。
2.最差时间复杂度

        当数组为逆序时，每次插入都需要将全部已排序部门元素向右移动。
3.平均时间复杂度

        一样平常情况下，插入排序的性能体现介于最佳和最差之间。
2. 空间复杂度

        插入排序是原地排序算法，只需常数级别的额外空间，空间复杂度为O(1) 。
三、插入排序的优缺点

1.优点

1. 简单直观：算法易于明确和实现。
2. 适合小数据集：对于小规模数据排序性能较好。
3. 稳固性：插入排序是稳固排序算法，不会改变相同元素的相对位置。
4. 局部有序优化：当数据部门有序时，插入排序的性能非常靠近线性时间。
2.缺点

1. 服从低下：对于大规模数据，插入排序的性能较差，时间复杂度较高。
2. 多次元素移动：在数组为逆序的情况下，插入排序需要频繁移动元素，服从较低。
四、插入排序的改进与变种

1. 二分插入排序
• 改进点：在插入时，通过二分查找定位插入位置，从而淘汰比力次数。
• 时间复杂度：虽然查找位置优化为 ，但元素移动次数仍为 。
2. 希尔排序（Shell Sort）
• 基于插入排序的改进版，通过引入增量分组的思想，对远距离元素进行预排序，渐渐缩小分组间隔，最终变为插入排序。
• 时间复杂度：最优可达 。
五、插入排序的应用场景

1. 小规模数据排序：在数据量较小时，插入排序简单易用，且性能尚可。
2. 近乎有序数据：插入排序在处理已部门有序的数据时体现优异。
3. 作为复杂排序的辅助算法：如快速排序或希尔排序中，用插入排序优化小数组的排序服从。
六、总结

        插入排序是一种经典的排序算法，以其简单性和直观性被广泛应用于教学和小规模排序场景中。虽然它在大数据排序上的性能较差，但通过改进（如二分插入排序）或团结其他算法（如希尔排序），可以明显提升服从。



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