如何进行C语言数据结构与算法中的排序总结
导读:本文共4759字符,通常情况下阅读需要16分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要: 一、前言学习目标:排序和查找密不可分,将待处理的数据按关键值大小有序排列后,查找更加快速准确理解各种排序算法的定义和特点,并能将代码灵活运用掌握各种排序方法时间复杂度与空间复杂度理解排序稳定和不稳定的概念 重点和难点: 希尔、快速、堆、归并排序这几种快速排序二、基本概念1.排序定义:将一个无序的数据元素任意序列,重新排列成有序的过程代码:typede... ...
目录
(为您整理了一些要点),点击可以直达。一、前言
学习目标:
排序和查找密不可分,将待处理的数据按关键值大小有序排列后,查找更加快速准确
理解各种排序算法的定义和特点,并能将代码灵活运用
掌握各种排序方法时间复杂度与空间复杂度
理解排序稳定和不稳定的概念
重点和难点: 希尔、快速、堆、归并排序这几种快速排序
二、基本概念
1.排序
定义:将一个无序的数据元素任意序列,重新排列成有序的过程
代码:
typedefstruct{intkey;//假设关键字为int型OtherTypeother_data;}RecordType;
2.排序方法的稳定性
0123456789541011228107612解读:如上个表格这样的一个无序数组,想要将它按照从小到大排序。上图下标2和6对应的数字都是10,排序后假如红色的10任然在黑色的10前面,那这种排序方法就是稳定的,否则排序方法不稳定。
3.内部和外部排序
内部排序:整个排序过程在内存中
外部排序:需要排序的数过大,需要借助外部设备
三、插入类排序
插入类:在一个有序序列插入一个新的记录,使之仍然有序
1.直接插入排序
动态演示:
算法讲解:
上面的动态图可以很好的表达直接插入的过程,只是动态图有点长
首先将0作为监视哨,用一个指针从前往后找后面的数字比前面数字小的,找到了放到0
指针开始向前移动,如果指向的值比监视哨里的值大,数字向后移
如果指向的值比监视哨里的值小,那把监视哨里的值存入这个元素之后
以此类推
代码:
voidInsSort(RecordTyper[],intlength)/*对记录数组r做直接插入排序,length为数组中待排序记录的数目*/{ inti,j; for(i=2;i<=length;i++) { r[0]=r[i];/*将待插入记录存放到监视哨r[0]中*/ j=i-1; while(r[0].key<r[j].key)/*寻找插入位置*/ { r[j+1]=r[j]; j=j-1; } r[j+1]=r[0]; /*将待插入记录插入到已排序的序列中*/ }}/*InsSort*/
特点:
稳定排序
时间复杂度O(n*n), 空间复杂度O(1)
2.折半插入排序
算法讲解:
动态图没找到,只能用上面这张图片了
折半插入和折半查找思想差不多,对于一个有序的数组,将一个数字插入之后任然有序
k=要插入的值 low=1, high=length , mid=(low+high)+1 mid对应的值比k大, high=low-1,否则 low=mid+1,
当low >high ,low后面就是k插入的位置
代码:
voidBinSort(RecordTyper[],intlength)/*对记录数组r进行折半插入排序,length为数组的长度*/{ inti,j;RecordTypex; intlow,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;/*插入记录*/ }}/*BinSort*/
特点:
稳定排序
时间复杂度O(n*n), 空间复杂度O(1)
3.希尔排序
动态演示:
算法讲解:
对于希尔排序来说取增量 d (d一般为奇数,并且逐次递减)
上图第一次排序d等于5,将第一个作为起始点,下标+5取下一个值,一直到最后,将去到的值从小到达排序,然后将第二个作为起始点,3 4 5依次作为起始点排序
第二次是d等于3
第三次是d等于1
代码:
voidShellInsert(RecordTyper[],intlength,intdelta)/*对记录数组r做一趟希尔插入排序,length为数组的长度,delta为增量*/{ inti,j; for(i=1+delta;i<=length;i++)/*1+delta为第一个子序列的第二个元素的下标*/ if(r[i].key<r[i-delta].key) { r[0]=r[i];/*备份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]; }}/*ShellInsert*/
特点:
不稳定排序方法
增量序列的d取值无除1之外的公因子,最后一个增量值必须为1
时间复杂度O(nlogn) 空间复杂度O(1)
四、交换类排序
1.冒泡排序
动态演示:
算法讲解:
设立两个指针,i,j
每一次排序都会把最大的一个数放到后面,依次类推,假设执行2次以后,那么最后2个数就不需要比较了
执行n-1次排序,结果完成
代码:
voidBubbleSort(RecordTyper[],intlength)/*对记录数组r做冒泡排序,length为数组的长度*/{ intn,i,j;ntchange;RecordTypex;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; } }}/*BubbleSort
特点:
稳定排序
时间复杂度O(n*n), 空间复杂度O(1)
2.快速排序
动态演示:
算法讲解:
快速排序讲起来稍微有点复杂,其实就是划分区域
建立两个指针low high 分别指向第一个和第二个元素,把第一个元素的值赋给x变量
high向前移动,假如high指向的值小于x,则high指向的值与x互换
low向后移动,假如low指向的值大于x,则low指向的值与x互换
重复3 4两步,知道high==low,第一次结束
将low指向第二个元素,把第二个元素的值赋给x变量
重复操作,知道元素有序
代码:
1.递归算法:
voidQKSort(RecordTyper[],intlow,inthigh)/*对记录数组r[low..high]用快速排序算法进行排序*/{ intpos; if(low<high) { pos=QKPass(r,low,high);/*调用一趟快速排序,将枢轴元素为界划分两个子表*/ QKSort(r,low,pos-1);/*对左部子表快速排序*/ QKSort(r,pos+1,high);/*对右部子表快速排序*/ }}
2.非递归算法:
intQKPass(RecordTyper[],intleft,intright)/*对记录数组r中的r[left]至r[right]部分进行一趟排序,并得到基准的位置,使得排序后的结果满足其之后(前)的记录的关键字均不小于(大于)于基准记录*/{ RecordTypex; intlow,high; x=r[left];/*选择基准记录*/ low=left; high=right; while(low<high) { while(low<high&&r[high].key>=x.key)/*high从右到左找小于x.key的记录*/ high--; if(low<high){r[low]=r[high];low++;}/*找到小于x.key的记录,则进行交换*/ while(low<high&&r[low].key<x.key)/*low从左到右找大于x.key的记录*/ low++; if(low<high){r[high]=r[low];high--;}/*找到大于x.key的记录,则交换*/ } r[low]=x;/*将基准记录保存到low=high的位置*/ returnlow;/*返回基准记录的位置*/}/*QKPass*/
特点:
不稳定排序,但内部排序中公认效率最好的一种
时间复杂度O(nlogn) 空间复杂度O(logn)
五、总结比较
</div> <div class="zixun-tj-product adv-bottom"></div> </div> </div> <div class="prve-next-news">
如何进行C语言数据结构与算法中的排序总结的详细内容,希望对您有所帮助,信息来源于网络。