CSP-J 算法基础之插入排序

举报
人才程序员 发表于 2024/09/14 18:14:02 2024/09/14
【摘要】 @TOC 前言插入排序(Insertion Sort)是一种简单且高效的排序算法,特别适用于数据规模较小的情况。它的工作原理类似于将扑克牌整理成顺序,通过逐步将每张牌插入到已排序部分的适当位置。插入排序在处理小规模数据时具有较好的性能,并且易于实现。由于其时间复杂度为 O(n²),在大规模数据集上效率较低。然而,插入排序在数据接近有序时表现尤为出色,是一种直观且易于理解的排序算法。 插入排序...

@TOC


前言

插入排序(Insertion Sort)是一种简单且高效的排序算法,特别适用于数据规模较小的情况。它的工作原理类似于将扑克牌整理成顺序,通过逐步将每张牌插入到已排序部分的适当位置。插入排序在处理小规模数据时具有较好的性能,并且易于实现。由于其时间复杂度为 O(n²),在大规模数据集上效率较低。然而,插入排序在数据接近有序时表现尤为出色,是一种直观且易于理解的排序算法。


插入排序

插入排序(Insertion Sort)是一种简单且直观的排序算法。它的工作原理类似于整理扑克牌:我们将数组看作分为两个部分,已排序的部分和未排序的部分,逐一将未排序的元素插入到已排序的部分中合适的位置,直到整个数组有序。

插入排序的过程

假设我们有一个数组 [7, 4, 5, 2, 9],使用插入排序对它进行升序排序。

  1. 初始数组
    [7, 4, 5, 2, 9]

    • 第一个元素 7 默认作为已排序的部分。
  2. 第1轮
    取第二个元素 4,将它插入到已排序部分 [7] 中:

    • 比较 74,由于 4 < 7,将 7 向右移:
      [7, 7, 5, 2, 9]
    • 4 插入到空出来的位置:
      [4, 7, 5, 2, 9]

    第1轮结果[4, 7] 是已排序部分。

  3. 第2轮
    取第三个元素 5,将它插入到已排序部分 [4, 7] 中:

    • 比较 75,由于 5 < 7,将 7 向右移:
      [4, 7, 7, 2, 9]
    • 比较 54,由于 5 > 4,不移动,直接插入到 7 的前面:
      [4, 5, 7, 2, 9]

    第2轮结果[4, 5, 7] 是已排序部分。

  4. 第3轮
    取第四个元素 2,将它插入到已排序部分 [4, 5, 7] 中:

    • 比较 72,由于 2 < 7,将 7 向右移:
      [4, 5, 7, 7, 9]
    • 比较 52,由于 2 < 5,将 5 向右移:
      [4, 5, 5, 7, 9]
    • 比较 42,由于 2 < 4,将 4 向右移:
      [4, 4, 5, 7, 9]
    • 2 插入到空出来的位置:
      [2, 4, 5, 7, 9]

    第3轮结果[2, 4, 5, 7] 是已排序部分。

  5. 第4轮
    取第五个元素 9,将它插入到已排序部分 [2, 4, 5, 7] 中:

    • 比较 97,由于 9 > 7,不移动,直接插入到末尾:
      [2, 4, 5, 7, 9]

    第4轮结果:数组已经完全排序。

最终结果

经过插入排序,数组从 [7, 4, 5, 2, 9] 排序为 [2, 4, 5, 7, 9]

插入排序总结

插入排序通过逐步将元素插入到已排序部分来实现有序排列。每一轮通过比较,找到适当的位置插入当前元素,并通过元素的移动来为它腾出空间。这个过程类似于玩扑克牌时,整理手中的牌。

实现插入排序代码

// 插入排序函数(带调试信息)
void insertionSort(int arr[], int n) {
    int i, key, j;
    // 从第二个元素开始,依次插入到已排序的部分
    for (i = 1; i < n; i++) {
        key = arr[i];  // 当前要插入的元素
        j = i - 1;
        
        printf("\n第 %d 轮:插入元素 %d\n", i, key);  // 输出当前要插入的元素
        printf("排序前的数组: ");
        for (int k = 0; k < n; k++) {
            printf("%d ", arr[k]);
        }
        printf("\n");

        // 将已排序部分比 key 大的元素向右移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];//向右移动就是两个交换位置 
            printf("将 %d 向右移动到位置 %d\n", arr[j], j + 1);
            j = j - 1;
        }

        // 将 key 插入到正确的位置
        arr[j + 1] = key;
        printf("将插入元素 %d 放在位置 %d\n", key, j + 1);
        
        printf("排序后的数组: ");
        for (int k = 0; k < n; k++) {
            printf("%d ", arr[k]);
        }
        printf("\n");
    }
}

总结

插入排序通过逐步将每个元素插入到已排序部分的适当位置来实现排序。它的核心思想是利用已排序部分的有序性,每次插入一个新元素,并将它插入到合适的位置。尽管插入排序的时间复杂度为 O(n²),这使得它在处理大型数据集时效率不高,但它在处理小规模数据或数据几乎有序的情况下表现良好。插入排序的简单性和直观性使其成为学习排序算法的良好入门选择,并为进一步学习其他复杂排序算法奠定了基础。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。