




已阅读5页,还剩13页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
排序算法 姓名:邓 海 波 学号:2013222053 年级:2013 级 专业: 生物信息学1、 算法介绍排序算法是为了解决输入的n个数的一个序列,.,经过我们的排序后输出已排好的序列,.,(满足.)。我们将通过不同的排序算法解决这个问题,比如选择排序、插入排序、冒泡排序、快速排序、堆排序、归并排序、希尔排序、基数排序等,并通过对其时间复杂度进行对比进而得出相应的结论。2、 基本算法1、 选择排序选择排序的基本思想是: 对待排序的n个数据进行n-1遍的处理,第1遍处理是将a2.n中最小者与a1交换位置,第2遍处理是将a3.n中最小者与a2交换位置,.,第i遍处理是将ai+1.n中最小者与ai交换位置。这样,经过i遍处理之后,前i个记录的位置就已经按从小到大的顺序排列好了。总共比较 n(n-1)/2 次,时间复杂度为(),其稳定性为不稳定(稳定性是指值相同的数字在排序前后其相对位置是否要发生改变,若要改变就是不稳定,否则就是稳定的。)算法代码: main() int flag,temp,i,j,a10=12,33,45,67,89,99,45,11,22,48; printf(源程序为:n); for(i=0;i10;i+) printf(%-3d,ai); for(i=0;i9;i+) flag=i; for(j=i+1;jaj) flag=j; if(i!=flag) temp=aflag; aflag=ai; ai=temp; printf(n排序后为:n); for(i=0;i10;i+) printf(%-3d,ai); 2、 冒泡排序冒泡排序基本思想是:对待排序的数字进行两两比较,如发现两个数字是反序的,则进行交换,直到无反序的记录为止(此处是按从大到小的顺序排列)。总共比较 n(n-1)/2 次,时间复杂度为(),是稳定的排序算法。算法代码:main() int i,j,l,a10=9,89,90,23,56,12,45,67,36,99; printf(源程序为:n); for(i=0;i10;i+) printf(%-3d,ai); printf(n); printf(排序后为:n); for(i=0;i10;i+) for(j=i+1;jaj) l=ai; ai=aj; aj=l; for(i=0;i10;i+) printf(%-3d,ai); 3、 插入排序有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法-插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为()。是稳定的排序方法。算法代码:void insert(int a,int leng) int i,j,key; for(i=1;i=0 & ajkey) aj+1=aj; j-; aj+1=key; main() int a=23,56,88,97,45,33,11,3,89,67,i,j; printf(源数组为:n); for(i=0;i10;i+) printf(%-3d,ai); insert(a,10); printf(n插入后序列为:n); for(j=0;j10;j+) printf(%-3d,aj); 4、 快速排序思想:每次找一个数位基准,把小于等于它的放到这个数的左边,把大于等于它的放到它的右边,每排完一趟,小于等于基准值的,在其左侧。大于等于基准值的在其右侧。平均时间复杂度:()是不稳定的排序算法。算法代码:void quiksort(int a,int low,int high) int i = low; int j = high; int temp = ai; if( low high) while(i = temp) & (i j) j-; ai = aj; while(ai = temp) & (i j) i+; aj= ai; ai = temp; quiksort(a,low,i-1); quiksort(a,j+1,high); else return; void main() int arry11 = 2,32,43,23,45,36,57,14,27,39,11,i; printf(源程序为:n); for(i=0;i11;i+) printf(%d ,arryi); printf(n); quiksort(arry,0,10); printf(排序后为:n); for(i=0;i11;i+) printf(%d ,arryi); printf(n);5、 堆排序堆的定义:n个元素的序列,.,,当&时我们称为最小化堆或小顶堆,当&时我们称为最大化堆或大顶堆(i=1,2,.,n)。由此,若序列,.,是堆,则堆顶元素(或完全二叉树的根)必为序列中n个元素的最小值(或最大值)。若在输出堆顶的最小值之后,使得剩余n-1个元素的序列重又建成一个堆,则得到n个元素的次小值。如此反复执行,便能得到一个有序序列,这个过程称之为堆排序。排序过程:堆排序是一种选择排序。建立的初始堆为初始的无序区。排序开始,首先输出堆顶元素(因为它是最值),将堆顶元素和最后一个元素交换,这样,第n个位置(即最后一个位置)作为有序区,前n-1个位置仍是无序区,对无序区进行调整,得到堆之后,再交换堆顶和最后一个元素,这样有序区长度变为2,不断进行此操作,将剩下的元素重新调整为堆,然后输出堆顶元素到有序区。每次交换都导致无序区-1,有序区+1。不断重复此过程直到有序区长度增长为n-1,排序完成。想得到升序,则建立大顶堆,若想得到降序,则建立小顶堆。堆排序在最坏的情况下,其时间复杂度:()是不稳定的排序算法。相对于快速排序来说,这是堆排序的最大优点。此外,堆排序仅需一个记录大小的供交换用的辅助存储空间。算法代码:/*堆排序 实现,算法复杂度O(nlgn)*/#include#include/*假设节点i的左右子树都是最大堆,操作使节点i的子树变成最大堆*/void maxHeap(int A,int len,int i) int l,r,large,temp; l=2*i; r=2*i+1; large=i; if(lAi) large=l; if(rAlarge) large=r; if(large!=i) temp=Alarge; Alarge=Ai; Ai=temp; maxHeap(A,len,large); /*建立大根堆*/void buildMaxHeap(int A,int len) int i; for(i=len/2-1;i=0;i-) maxHeap(A,len,i);/*堆排序*/void maxHeapSort(int A,int len) int i,temp; buildMaxHeap(A,len); printf(建立大跟堆:n); for(i=0;i1;i-) temp=A0; A0=Ai-1; Ai-1=temp; printf(%-3d,Ai-1); buildMaxHeap(A,i-1); printf(n);/*测试堆排序*/int main() int i; int A11=4,11,38,23,16,98,10,14,81,78,66; printf(源序列为:n); for(i=0;i11;i+) printf(%-3d,Ai); printf(n); maxHeapSort
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 单招服装考试题及答案
- 大学造型基础考试题及答案
- 中国烧碱氧化物项目创业投资方案
- 大学电磁理论考试题及答案
- 老师招聘协议书
- 船厂起重工考试题及答案
- 年会舞协议书
- 急救药品考试试题及答案
- 机械员考试试题及答案
- 回转窑考试试题及答案
- 筏板基础施工课件
- 法理学-第五编-法的价值
- 人教鄂教版五年级上册科学期中测试题(1-3单元)(含答案)
- 心灵树洞中小学生心理健康主题班会PPT教学课件
- 木质纤维素的生物分解及其转化技术
- 海康威视磁盘阵列使用说明精.选
- GB/T 7387-1999船用参比电极技术条件
- GB/T 39473-2020北斗卫星导航系统公开服务性能规范
- GB 16808-2008可燃气体报警控制器
- 公司有限空间作业安全专项排查表
- 强度调制机理光纤传感器基本原理课件
评论
0/150
提交评论