文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

如何进行C语言数据结构与算法中的排序总结

2023-06-22 03:32

关注

这篇文章将为大家详细讲解有关如何进行C语言数据结构与算法中的排序总结,文章内容质量较高,因此小编分享给大家做个参考,希望大家阅读完这篇文章后对相关知识有一定的了解。

一、前言

学习目标:

排序和查找密不可分,将待处理的数据按关键值大小有序排列后,查找更加快速准确

理解各种排序算法的定义和特点,并能将代码灵活运用

掌握各种排序方法时间复杂度与空间复杂度

理解排序稳定和不稳定的概念                

重点和难点: 希尔、快速、堆、归并排序这几种快速排序

二、基本概念

1.排序

定义:将一个无序的数据元素任意序列,重新排列成有序的过程

代码:

typedef struct{         int key;   //假设关键字为int型       OtherType  other_data;} RecordType;

2.排序方法的稳定性

0123456789
541011228107612

解读:如上个表格这样的一个无序数组,想要将它按照从小到大排序。上图下标2和6对应的数字都是10,排序后假如红色的10任然在黑色的10前面,那这种排序方法就是稳定的,否则排序方法不稳定。

3.内部和外部排序

三、插入类排序

插入类:在一个有序序列插入一个新的记录,使之仍然有序

1.直接插入排序

动态演示:

如何进行C语言数据结构与算法中的排序总结

算法讲解: 

  1. 上面的动态图可以很好的表达直接插入的过程,只是动态图有点长

  2. 首先将0作为监视哨,用一个指针从前往后找后面的数字比前面数字小的,找到了放到0

  3. 指针开始向前移动,如果指向的值比监视哨里的值大,数字向后移

  4. 如果指向的值比监视哨里的值小,那把监视哨里的值存入这个元素之后

  5. 以此类推

代码:

void InsSort(RecordType  r[],  int length){ int i,j;for (i=2;  i<=length;  i++) {r[0]=r[i];      j=i-1;         while (r[0].key< r[j].key )     {r[j+1]= r[j]; j=j-1;}r[j+1]=r[0];}} 

特点: 

稳定排序

时间复杂度O(n*n), 空间复杂度O(1)

2.折半插入排序

如何进行C语言数据结构与算法中的排序总结

算法讲解:

  1. 动态图没找到,只能用上面这张图片了

  2. 折半插入和折半查找思想差不多,对于一个有序的数组,将一个数字插入之后任然有序

  3. k=要插入的值  low=1, high=length , mid=(low+high)+1   mid对应的值比k大, high=low-1,否则 low=mid+1,

  4. 当low >high ,low后面就是k插入的位置

代码:

void BinSort (RecordType  r[],  int length){int i,j;    RecordType x;    int low,high,mid;for (i=2; i<=length ; ++i ) {x= r[i];  low=1;  high=i-1;while (low<=high )                   {mid=(low+high) / 2;if ( x.key< r[mid].key) high=mid-1;else low=mid+1;}for ( j=i-1 ; j>= low; --j )   r[j+1]= r[j];     r[low]=x;    }}

特点: 

稳定排序

时间复杂度O(n*n), 空间复杂度O(1)

3.希尔排序

动态演示:

如何进行C语言数据结构与算法中的排序总结

算法讲解: 

  1. 对于希尔排序来说取增量 d (d一般为奇数,并且逐次递减)

  2. 上图第一次排序d等于5,将第一个作为起始点,下标+5取下一个值,一直到最后,将去到的值从小到达排序,然后将第二个作为起始点,3 4 5依次作为起始点排序

  3. 第二次是d等于3

  4. 第三次是d等于1

代码:

void  ShellInsert(RecordType r[], int length,  int  delta){int i,j;for(i=1+delta;i<= length; i++)     if(r[i].key < r[i-delta].key){r[0]= r[i];          for(j=i-delta; j>0 &&r[0].key < r[j].key; j-=delta)r[j+delta]= r[j];r[j+delta]= r[0];}}

特点:

不稳定排序方法

增量序列的d取值无除1之外的公因子,最后一个增量值必须为1

时间复杂度O(nlogn)  空间复杂度O(1)

四、交换类排序

1.冒泡排序

动态演示:

如何进行C语言数据结构与算法中的排序总结

算法讲解: 

  1. 设立两个指针,i,j

  2. 每一次排序都会把最大的一个数放到后面,依次类推,假设执行2次以后,那么最后2个数就不需要比较了

  3. 执行n-1次排序,结果完成

代码:

void  BubbleSort(RecordType r[], int length ){int n,i,j; nt change; RecordType x; n=length;  change=TRUE;for ( i=1 ; i<= n-1 && change ;++i ) {change=FALSE;for ( j=1 ; j<= n-i ; ++j) if (r[j].key > r[j+1].key )  {x= r[j];r[j]= r[j+1];r[j+1]= x;change=TRUE;} }} {int pos;if(low<high){pos=QKPass(r, low, high);  QKSort(r, low, pos-1);     QKSort(r, pos+1, high); }}

非递归算法:

int QKPass(RecordType r[],int left,int right){ RecordType x;int low,high;x= r[left];              low=left;  high=right;while ( low<high ){while (low< high && r[high].key>=x.key )   high--;if ( low <high ) {r[low]= r[high];  low++;}  while (low<high && r[low].key<x.key  )   low++; if (  low<high  ){ r[high]= r[low]; high--; } }r[low]=x;                     return low;                     } 

特点:

不稳定排序,但内部排序中公认效率最好的一种

时间复杂度O(nlogn)  空间复杂度O(logn)

五、总结比较

如何进行C语言数据结构与算法中的排序总结

关于如何进行C语言数据结构与算法中的排序总结就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯