欢迎来到论文网! 加入收藏 | 设为论文网 | 网站地图 | Tags标签 | RSS
论文网 论文网8200余万篇毕业论文、各种论文格式和论文范文以及9千多种期刊杂志的论文征稿及论文投稿信息,是论文写作、论文投稿和论文发表的论文参考网站,也是科研人员论文检测和发表论文的理想平台,lunwenf@yeah.net。
您当前的位置:论文网 > 科技论文 > 计算机论文

数据结构中内部排序算法的分析

时间:2015-12-02  作者:吴红芝郭麦城吴浩

摘要:排序是计算机程序设计中的一种重要操作,它的功能是将一个数据元素的任意系列,重新排列成一个按关键字有序的序列。然而,在现实的过程中,由于受到排序算法本身的程序设计思想、时间复杂度及稳定性等因素的影响,使初学者在理解上存在很大的问题,本文将具体针对这些问题,提供一些行之有效的解决方法。
论文关键词:排序,算法,稳定性,时间复杂度
  排序依据所涉及的存储器不同,分为两大类:一类是内部排序,指的是待排序记录存放在计算机存储器中进行的排序过程;另一类则是外部排序,指的是待排序记录数量很大,以至内存不能容纳全部记录,在排序过程中尚需对外存进行访问的排序过程。本文将主要讨论内部排序中的直接插入排序、冒泡排序和简单选择排序三种排序,并简要的分析一下快速排序的稳定性。
  与其它算法相比,排序也是数据结构中的一种算法,只不过它所实现的功能比较具体,即实现无序系列的排序。同样,它也涉及到一种算法的设计思想、参数的引用及时间复杂度等相关因素;与其它算法有所不同,排序算法涉及到了稳定性与不稳定性的概念,即关键字相同,排序后它们的顺序不变的排序方法称为稳定排序,顺序有可能发生改变的排序方法称为不稳定排序。例如,数据结构中内部排序算法的分析,序列中有两个2,标记为。用一种排序方法进行排序,排序后,若始终在的前面,则称稳定的排序,若有可能在的后面,则称不稳定的排序。
  排序按排序过程中依据的不同原则对内部排序进行分类,大致可分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。其实现过程主要进行比较和移位两种操作,即比较关键字的大小,将记录从一个位置移动到另一个位置,最后得到一个有序序列。学习排序的过程,其关键在于理解排序的思想,分析各种排序的特点,从分类到实现,利用流程来实现过程。
  1 几种排序算法的实现过程
  内部排序按其算法设计思想的不同,可分为直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序和基数排序,其中插入的排序有直接插入排序、折半插入排序和希尔排序三种,交换的排序有冒泡排序和快速排序,选择的排序有简单选择排序和堆排序。
  从排序的稳定性来看,稳定的排序有:直接插入排序、折半插入排序、冒泡排序和归并排序,不稳定的排序有:希尔排序、快速排序、简单选择排序和堆排序;从排序算法的时间复杂度来看,直接插入排序、折半插入排序、冒泡排序、简单选择排序的时间复杂度为,希尔排序的时间复杂度为,快速排序、堆排序和归并排序的时间复杂度为稳定性
  本文将从排序算法的设计思想、流程图、程序设计、稳定性和时间复杂度等五个方面具体分析,主要介绍直接插入排序、冒泡排序、快速排序、简单选择排序和堆排序。此外,在程序的设计过程中,将引用一个数组啊a[n]来保存排序序列,排序序列中的所有元素均为整型元素,且均按把序列排成升序的过程来实现。
  1.1 直接插入排序
  1.1.1 程序设计思想
  直接插入排序可把序列分成已排序列和未排序列两个部分,最开始时,第一个元素为已排序列,后面的所有元素均为未排序列,在排序的过程中,是把前面的序列看成一个已经排好的序列,把后面的元素逐个插入到前面已排好的序列中。例如序列:25,17,8,49,23,15,20。
  一次排序,25是一个已排好的序列,17,8,49,23,15,20是未排序列,选择未排序列中第一个数17插入到前面的已排序列中,形成序列:17,25,8,49,23,15,20。此时17,25是已排序列,8,49,23,15,20是未排序列。
  二次排序,选择未排序列中第一个数8插入到前面的已排序列,形成已排序列8,17,25,未排序列49,23,15,20,此时整个序列为8,17,25,49,23,15,20。依次类推,直至整个序列有序。
  1.1.2 程序流程图
  图1 直接插入排序流程图
  1.1.3 程序设计
  InsertSort( int a[n] ) //a[i-1]是已排序列的最后一个元素,a[i]是未
  { int i ,j ,b ; //排序列的第一个元素,实质是把a[i]插入到
  for( i=1; j

查看相关论文专题
-------------------------------------------------------------------------
加入收藏  打印本文
上一篇论文:数据库管理系统的组成与发展
下一篇论文:试论移动数字化办公的实现
科技论文分类
科技小论文 数学建模论文
数学论文 节能减排论文
数学小论文 低碳生活论文
物理论文 建筑工程论文
网站设计论文 农业论文
图书情报 环境保护论文
计算机论文 化学论文
机电一体化论文 生物论文
网络安全论文 机械论文
水利论文 地质论文
交通论文
相关计算机论文
最新计算机论文
读者推荐的计算机论文