当前位置:首页 » 《随便一记》 » 正文

【C语言/数据结构】排序(直接插入排序|希尔排序)

25 人参与  2024年02月06日 14:41  分类 : 《随便一记》  评论

点击全文阅读


 ?个人主页:秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343
? 系列专栏:《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482

9efbcbc3d25747719da38c01b3fa9b4f.gif​​​​

目录

 插入排序

直接插入排序:

希尔排序

预排序

gap的取值

时间复杂度

​编辑 ​编辑

完整代码呈现

 


 

   前言

    ? hello! 各位铁子们大家好哇。

             今日更新了插入排序的内容
    ? 欢迎大家关注?点赞?收藏⭐️留言?

 

 81ede814cfe94cd2babe3f6300d32f63.png

 插入排序

直接插入排序:

下方是原理图:

 d96f573be6b19a36b1d8fb05d9fdd609.gif

 

//时间复杂度:O(N^2) 逆序//最好的情况:O(N)  顺序有序void InsertSort(int* a, int n){for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}}

分析:此过程为升序。end指向第一个要比较的元素的下标,tmp为待插入元素。当tmp小于前面的元素时,把前一位元素往后移,end--,使其指向前一位(更小的)元素。当tmp不再大于前一位元素,就直接用tmp替换。需注意:for循环的结束条件。

希尔排序

 希尔排序有2步:

预排序(接近有序)(分别对每个分组进行插入排序)直接插入排序

预排序

de7ec625ca5c46c7a7224a09ac3232e0.png

分析:我们假设每组的间隔是3,相同颜色相连的数字是同一组,红色原本是9,6,4,1,进行插入排序后就变成1,4,6,9。其他组别以此类推。这样的目的是使较大的数排后面,小的排前面,让他接近有序。最后再整体进行插入排序,这样可以提高效率。

 预排序代码实现如下:

int gap = 3;//一组一组排//for (int j = 0; j < gap; j++)//{//for (int i = j; i < n - gap; i += gap)//{//int end=i;//int tmp = a[end + gap];//while (end >= 0)//{//if (tmp < a[end])//{//a[end + gap] = a[end];//end -= gap;//}//else//{//break;//}//}//a[end + gap] = tmp;//}//}//多组并排for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}

分析:预排序有两种写法,第二种写法比第一种少了一层循环。

我们先分析第一种:预排序是在我们前面讲的直接插入排序中修改的。内层for循环中,因为是间隔着排序,所以每次加减时都是加减gap,内层循环结束后,就完成了第一组的排序,外层for循环控制第几组排序。

第二种:少了外层的for循环,i就要从0开始,然后每次加1,这样就是混合着多组进行排序,其他步骤不变。

gap的取值

gap越大,大的值更快调到后面,小的值可以更快调到前面,越不接近有序。gap越小,跳的越慢,但是越接近有序,如果gap==1,就是直接插入排序。
//多组并排int gap = n;//gap>1时是预排序,目的是让他接近有序//gap==1是直接插入排序,目的是让他有序while (gap>1){//gap=gap/2;gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}

分析:在实际中,gap取值看数量情况定。当gap>1,循环进行预排序,每次/2,最后一次肯定是1。但是每次/2,进行的预排序可能还是过多,就可以/3,不过要保证最后一次是1,因为当2除以3时==0,所以就要在后面加上1。具体除以几,主要保证最后一次是1即可。

时间复杂度

7659f81ca84f44da905dc538da4a0994.png 46ecc4e90c8f40c491a6049f80a9521c.png

分析:最后一轮累计的挪动次数大约为:n 。总的平均时间复杂度是O(N^1.3),因为计算过程十分复杂,只需了解。

完整代码呈现

//平均O(N^1.3)void ShellSort(int* a, int n){//int gap = 3;//一组一组排//for (int j = 0; j < gap; j++)//{//for (int i = j; i < n - gap; i += gap)//{//int end=i;//int tmp = a[end + gap];//while (end >= 0)//{//if (tmp < a[end])//{//a[end + gap] = a[end];//end -= gap;//}//else//{//break;//}//}//a[end + gap] = tmp;//}//}//多组并排int gap = n;//gap>1时是预排序,目的是让他接近有序//gap==1是直接插入排序,目的是让他有序while (gap>1){//gap=gap/2;gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}}

 

 


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/67610.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1