排序算法实验报告
19页1、数据结构实验报告八种排序算法实验报告一、 实验内容编写关于八种排序算法的C语言程序,要求包含直接插入排序、希尔排序、简单选择排序、堆排序、冒泡排序、快速排序、归并排序和基数排序。二、 实验步骤 各种内部排序算法的比较:1. 八种排序算法的复杂度分析(时间与空间)。2. 八种排序算法的C语言编程实现。3. 八种排序算法的比较,包括比较次数、移动次数。三、 稳定性,时间复杂度和空间复杂度分析比较时间复杂度函数的情况:时间复杂度函数O(n)的增长情况所以对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。时间复杂度来说:(1)平方阶(O(n2)排序 各类简单排序:直接插入、直接选择和冒泡排序; (2)线性对数阶(O(nlog2n)排序 快速排序、堆排序和归并排序; (3)O(n1+)排序,是介于0和1之间的常数。 希尔排序(4)线性阶(O(n)排序 基数排序,此外还有桶、箱排序。说明:当原表有序或基本有序时,直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数,时间复杂度可降至O(n);而快速排序则相反,当原表基本有序时,将蜕化为冒泡排序,时间复杂度提高为O(n2
2、);原表是否有序,对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。稳定性:排序算法的稳定性:若待排序的序列中,存在多个具有相同关键字的记录,经过排序, 这些记录的相对次序保持不变,则称该算法是稳定的;若经排序后,记录的相对 次序发生了改变,则称该算法是不稳定的。稳定性的好处:排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定,可以避免多余的比较;稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序四、 设计细节排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。我们这里说说八大排序就是内部排序。1. 插入排序-直接插入排序(Straight lnsertion Sort)基本思想: 将一个记录插入到已排序好的有序表中,从而得到一个新,记录数增1的有
3、序表。即:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插入,直至整个序列有序为止。要点:设立哨兵,作为临时存储和判断数组边界之用。直接插入排序示例:如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。时效分析:时间复杂度:O(n2)2. 插入排序希尔排序(Shells Sort)希尔排序是1959 年由D.L.Shell 提出来的,相对直接排序有较大的改进。希尔排序又叫缩小增量排序基本思想:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。操作方法:1. 选择一个增量序列t1,t2,tk,其中titj,tk=1;2. 按增量序列个数k,对序列进行k 趟排序;3. 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。希尔排序的示例:算法的实现:我
4、们简单处理增量序列:增量序列d = n/2 ,n/4, n/8 .1n为要排序数的个数即:先将要排序的一组记录按某个增量d(n/2,n为要排序数的个数)分成若干组子序列,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。继续不断缩小增量直至为1,最后使用直接插入排序完成排序。时效分析:希尔排序时效分析很难,关键码的比较次数与记录移动次数依赖于增量因子序列d的选取,特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法,有取奇数的,也有取质数的,但需要注意:增量因子中除1 外没有公因子,且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。3. 选择排序简单选择排序(Simple Selection Sort)基本思想:在要排序的一组数中,选出最小(或者最大)的一个数与第1个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换,依次类推,直到第n-1个元素(倒数第二个数)和第n个元素(最后一个数)比较
《排序算法实验报告》由会员大米分享,可在线阅读,更多相关《排序算法实验报告》请在金锄头文库上搜索。
根据DS1302和51单片机的电子时钟设计
消防逃生知识
中小企业贷款借款申请书
钢筋焊接方案
《动物的花衣裳》教案
幼儿园小班体育活动实施方案(三篇).doc
电缆的持续容许电流查询表
《汽车维修教程》题库参考答案.doc
《浙江专版》2011年高考语文 第6章古代诗歌鉴赏总复习 新人教版
2023会计助理的工作计划范本(四篇).doc
2023年新进教师述职报告.doc
精选2020年大学《中国近现代史纲要》期末试题库考核题库完整版500题(含参考答案)
幼儿园保健医师2022工作计划
2014-2015学年第一学期六年级语文期末卷
化工原理答案必下
大型五星级酒店装修协议书格式版(三篇).doc
2023年《夏洛特烦恼》观后感范文3篇(夏洛特的烦恼观后感)
大学生课外活动总结(二篇).doc
口腔科年度工作计划参考样本(四篇).doc
食品安全工作情况总结范文(二篇).doc
2023-02-01 33页
2022-08-15 4页
2023-05-03 6页
2022-12-03 3页
2023-12-05 21页
2023-10-25 6页
2023-06-25 6页
2023-03-26 4页
2022-12-28 9页
2022-11-01 1页