2025年数据结构与算法系列之插入排序

数据结构与算法系列之插入排序博客 小怡同学 个人简介 编程小萌新 如果博客对大家有用的话 请点赞关注再收藏 什么是插入排序 有一个已经有序的数据序列 要求在这个已经排好的数据序列中插入一个数

大家好,我是讯享网,很高兴认识大家。

在这里插入图片描述
讯享网

💗 💗 博客:小怡同学
💗 💗 个人简介:编程小萌新
💗 💗 如果博客对大家有用的话,请点赞关注再收藏 🌞

什么是插入排序

在这里插入图片描述

实现思想

当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排序码与
array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移。 例如:
有一个有序区间,选其中一个数插入其中,这个数依次比较如果匹配失败则,换到下一个数比较。

在这里插入图片描述

插入排序的时间复杂度

时间复杂度是O(n^2) 在最坏情况下逆序需要每个数轮流插入 根据等差数列 1+2+3+…+n-1
所以时间复杂度是O(n^2) 在最好情况下只需要轮一遍 所以时间复杂度为O(n^2)

在这里插入图片描述

插入排序的稳定性

稳定性意思是两个元素之间的相对位置没有改变 如 44 与 44 相等, 44在左 44在右,插入排序之后
44 仍在左 44 仍在右,这两个元素的相对位置没有改变。

在这里插入图片描述

代码实现

#include <stdio.h> void InsertSort(int* arr, int n) { 
    for (int i = 0; i < n - 1; i++) { 
    int end = i; int tmp = arr[end + 1]; while (end >= 0) { 
    if (tmp <= arr[end]) { 
    arr[end + 1] = arr[end]; end--; } else { 
    break; } } arr[end + 1] = tmp; } } int main() { 
    int arr[] = { 
    1,2,4,5,6,7,8,9,3 }; int n = (sizeof(arr) / sizeof(arr[0])); InsertSort(arr, n); for (int i = 0; i < n; i++) { 
    printf("%d ", arr[i]); } return 0; } 

讯享网

插入排序的优化——希尔排序

什么是希尔排序

希尔排序又称缩小增量排序,它通过比较相距一定间隔的元素来进行,各趟比较所用的距离随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止。
通俗大意是:把原本一组的数组间断性分为几个数组,在对已经分完的数组进行插入排序。

在这里插入图片描述

希尔排序的时间复杂度及稳定性

因为希尔排序的时间复杂度不好计算,因为gap的取值 方法很多,导致很难去计算。 时间复杂度;O(logNN)或者O(log3NN)
稳定性:不稳定

实现思想

先进行预排序,让数组接近有序,等到与排序之后 数组大多是有序的状态,大致上是有序数组,可进行插入排序。

讯享网void ShellSort(int* arr, int n) { 
    int gap = n; while (gap > 1) { 
    gap = gap / 3 + 1;//gap>1时是预排列 gap==1时相当有序排列 for (int i = 0; i < n - gap; i += gap)//把间隔为gap的元素进行插入排序 { 
    int end = i; int tmp = arr[end + gap]; while (end >= 0) { 
    if (tmp < arr[end]) { 
    arr[end + gap] = arr[end]; end -= gap; } else { 
    break; } } arr[end + gap] = tmp; } } } int main() { 
    int arr[] = { 
    1,2,4,5,6,7,8,9,3 }; int n = (sizeof(arr) / sizeof(arr[0])); InsertSort(arr, n); for (int i = 0; i < n; i++) { 
    printf("%d ", arr[i]); } return 0; } 

在这里插入图片描述

小讯
上一篇 2025-01-07 15:45
下一篇 2025-03-15 23:00

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/82418.html