数据结构内部排序实验报告

一、实验目的
1、掌握排序的有关概念和特点。
2、熟练掌握直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序等算法的基本思想。。
3、关键字序列有序与无序,对于不同的排序方法有不同的影响,通过该实验进一步加深理解。
二、实验内容
设有关键字序列k={ 12 , 45 , 21 , 12 , 30 , 2 , 68 , 33 },试用各种排序算法进行排序。
三、实验环境
TC或VC++
四、实验步骤
1、从键盘输入上述8个整数,存放在数组quick[8]中,并输出值。
2、输出各种排序算法每一趟排序的结果,观察关键字次序的变化。
(1)直接插入排序算法如下:
void InsertionSort ( SqList &L ) {
// 对顺序表 L 作直接插入排序。
for ( i=2; i<=L.length; ++i )
if (L.r[i].key < L.r[i-1].key) {
L.r[0] = L.r[i]; // 复制为监视哨
for ( j=i-1; L.r[0].key < L.r[j].key; -- j )
L.r[j+1] = L.r[j]; // 记录后移
L.r[j+1] = L.r[0]; // 插入到正确位置
}
} // InsertSort
(2)希尔排序算法如下:
void ShellInsert ( SqList &L, int dk ) {
for ( i=dk+1; i<=n; ++i )
if ( L.r[i].key< L.r[i-dk].key) {
L.r[0] = L.r[i]; // 暂存在R[0]
for (j=i-dk; j>0&&(L.r[0].key j-=dk)
L.r[j+dk] = L.r[j]; // 记录后移,查找插入位置
L.r[j+dk] = L.r[0]; // 插入
} // if
} // ShellInsert
void ShellSort (SqList &L, int dlta[], int t)
{ // 增量为dlta[]的希尔排序
for (k=0; k ShellInsert(L, dlta[k]);
//一趟增量为dlta[k]的插入排序
} // ShellSort
(3)冒泡排序算法如下:
void BubbleSort(Elem R[ ], int n) {
i = n;
while (i >1) {
lastExchangeIndex = 1;
for (j = 1; j < i; j++)
if (R[j+1].key < R[j].key) {
Swap(R[j], R[j+1]);
lastExchangeIndex = j; //记下进行交换的记录位置
} //if
i = lastExchangeIndex;
} // while
} // BubbleSort
(4)快速排序算法如下:
int Partition (RedType R[], int low, int high) {
R[0] = R[low]; pivotkey = R[low].key; // 枢轴

while (low while(low=pivotkey)
-- high; // 从右向左搜索
R[low] = R[high];
while (low ++ low; // 从左向右搜索
R[high] = R[low];
}
R[low] = R[0]; return low;
}// Partition
void QSort (RedType & R[], int s, int t ) {
// 对记录序列R[s..t]进行快速排序
if (s pivotloc = Partition(R, s, t); // 对 R[s..t] 进行一次划分
QSort(R, s, pivotloc-1);
QSort(R, pivotloc+1, t);
}
} // QSort
(5)简单选择排序的算法描述如下:
void SelectSort (Elem R[], int n ) {
// 对记录序列R[1..n]作简单选择排序。
for (i=1; i j = SelectMinKey(R, i); // 在 R[i..n] 中选择关键字最小的记录
if (i!=j) R[i]←→R[j]; // 与第 i 个记录交换
}
} // SelectSort
(6)堆排序算法描述如下:
void HeapSort ( HeapType &H ) {
// 对顺序表 H 进行堆排序
for ( i=H.length/2; i>0; --i )
HeapAdjust ( H.r, i, H.length ); // 建大顶堆
for ( i=H.length; i>1; --i ) {
H.r[1]←→H.r[i];

HeapAdjust(H.r, 1, i-1); // 对 H.r[1] 进行筛选
}
} // HeapSort
void HeapAdjust (RcdType &R[], int s, int m)
{

rc = R[s]; // 暂存 R[s]
for ( j=2*s; j<=m; j*=2 ) { // j 初值指向左孩子
if ( j if ( rc.key >= R[j].key ) break;
R[s] = R[j]; s = j;

}
R[s] = rc;

} // HeapAdjust
(7)归并排序算法描述如下:
void Msort ( RcdType SR[],

RcdType &TR1[], int s, int t ) {
// 将SR[s..t] 归并排序为 TR1[s..t]
if (s= =t) TR1[s]=SR[s];
else
{
m = (s+t)/2;
Msort (SR, TR2, s, m); // 递归地将SR[s..m]归并为有序的TR2[s..m]
Msort (SR, TR2, m+1, t);
Merge (TR2, TR1, s, m, t);
}
} // Msort
3、如果上述8个整数按照升序输入,即k1={ 2 , 12 , 12 , 21 , 30 , 33 , 45 , 68 },输出各种排序算法每一趟排序的结果,观察关键字次序的变化。
4、如果上述8个整数按照降序输入,即k2={ 68 , 45 , 33 , 30 , 21 , 12 , 12 , 2},输出各种排序算法每一趟排序的结果,观察关键字次序的变化。
5、随机产生3万个数,对其进行排序,观察其结果,并测试各排序算法的执行时间,比较执行效率。
五、问题讨论
1、直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序中哪些是稳定的排序方法,哪些是不稳定的?
2、直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序中哪些排序方法比较次数与初始序列有关,那些无关?
3、在初始序列基本有序的前提条件下,哪种排序方法效率最高?
六、实验报告内容
1、实验目的
2、实验内容和具体要求
3、完成情况和实验记录,实验记录为实验过程中遇到的问题及解决方法
4、程序清单
5、所输入的数据及相应的运行结果
6、问题回答
7、实验心得

1个回答

网上有类似代码,对所有排序的算法写一遍然后每次运行都是有时间统计的,你去下载来改改应该就可以完成这个报告了。 = =我的数据机构期末作业就这么弄弄,糊弄过去了。。。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
数据结构求解:如何列出所有的拓扑排序
-
51单片机汇编程序,将内部存储器E0H开始的32个单元数据倒序排序
-
数据结构快速排序问题
-
数据结构基数排序c++语言
-
数据结构直接插入排序
-
混合数组怎么仅仅对某种类型的数据排序,排序结果还是要保持别的类型的数据的顺序?
-
结构体排序,按照内部某成员变量排序
-
一道面试题(关于千万量级数据结构排序)
-
SQLite中对数据进行排序
-
java jtable数据排序问题
-
在初始数据表已经有序时,在排序过程中仍要改变数据表内容的排序算法是?
-
C++数据结构排序问题输出和时间问题求助
-
java数据结构排序输出问题
-
数据结构问题,请问如何用冒泡发实现单向链表的倒排序?C++语言
-
堆栈能不能进行排序后再Peek,C++数据结构的思考题?关于堆栈的排序,谢谢
-
页面显示的数据的排序问题
-
数据结构中的排序和查找
-
c++数据结构快速排序用栈实现
-
程序员真是太太太太太有趣了!!!
网络上虽然已经有了很多关于程序员的话题,但大部分人对这个群体还是很陌生。我们在谈论程序员的时候,究竟该聊些什么呢?各位程序员大佬们,请让我听到你们的声音!不管你是前端开发...
史上最详细的IDEA优雅整合Maven+SSM框架(详细思路+附带源码)
网上很多整合SSM博客文章并不能让初探ssm的同学思路完全的清晰,可以试着关掉整合教程,摇两下头骨,哈一大口气,就在万事具备的时候,开整,这个时候你可能思路全无 ~中招了咩~ ,还有一些同学依旧在使用eclipse或者Myeclipse开发,我想对这些朋友说IDEA 的编译速度很快,人生苦短,来不及解释了,直接上手idea吧。这篇文章每一步搭建过程都测试过了,应该不会有什么差错。本文章还有个比较优秀的特点,就是idea的使用,基本上关于idea的操作都算是比较详细的,所以不用太担心不会撸idea!最后,本文
2019年9月全国程序员工资统计
2019年9月2日,统计了某招聘网站上的所有程序员招聘信息。并汇总如下。
吃人的那些 Java 名词:对象、引用、堆、栈
作为一个有着 8 年 Java 编程经验的 IT 老兵,说起来很惭愧,我被 Java 当中的四五个名词一直困扰着:**对象、引用、堆、栈、堆栈**(栈可同堆栈,因此是四个名词,也是五个名词)。每次我看到这几个名词,都隐隐约约觉得自己在被一只无形的大口慢慢地吞噬,只剩下满地的衣服碎屑(为什么不是骨头,因为骨头也好吃)。
我花了一夜用数据结构给女朋友写个H5走迷宫游戏
起因 又到深夜了,我按照以往在csdn和公众号写着数据结构!这占用了我大量的时间!我的超越妹妹严重缺乏陪伴而 怨气满满! 而女朋友时常埋怨,认为数据结构这么抽象难懂的东西没啥作用,常会问道:天天写这玩意,有啥作用。而我答道:能干事情多了,比如写个迷宫小游戏啥的! 当我码完字准备睡觉时:写不好别睡觉! 分析 如果用数据结构与算法造出东西来呢? ...
接班马云的为何是张勇?
上海人、职业经理人、CFO 背景,集齐马云三大不喜欢的张勇怎么就成了阿里接班人? 作者|王琳 本文经授权转载自燃财经(ID:rancaijing) 9月10日,张勇转正了,他由阿里巴巴董事局候任主席正式成为阿里巴巴董事局主席,这也意味着阿里巴巴将正式开启“逍遥子时代”。 从2015年接任CEO开始,张勇已经将阿里巴巴股价拉升了超过200%。但和马云强大的个人光环比,张勇显得尤其...
让程序员崩溃的瞬间(非程序员勿入)
今天给大家带来点快乐,程序员才能看懂。 来源:https://zhuanlan.zhihu.com/p/47066521 1. 公司实习生找 Bug 2.在调试时,将断点设置在错误的位置 3.当我有一个很棒的调试想法时 4.偶然间看到自己多年前写的代码 5.当我第一次启动我的单元测试时 ...
用Python分析2000款避孕套,得出这些有趣的结论
到现在为止,我们的淘宝教程已经写到了第四篇,前三篇分别是: 第一篇:Python模拟登录淘宝,详细讲解如何使用requests库登录淘宝pc端。 第二篇:淘宝自动登录2.0,新增Cookies序列化,教大家如何将cookies保存起来。 第三篇:Python爬取淘宝商品避孕套,教大家如何爬取淘宝pc端商品信息。 今天,我们来看看淘宝系列的第四篇 我们在上一篇的时候已经将淘宝数据爬取下来了,...
Spring Cloud(11)——基于RocketMQ的Stream实现
基于RocketMQ的Stream实现 Spring Cloud Stream是一个消息收发的框架,它提供了一套标准,应用程序只需要按照它的标准进行消息的收发,而不用关注具体的实现机制。具体的实现可以基于不同的消息中间件进行不同的实现,比如Kafka的实现、RabbitMQ的实现、RocketMQ的实现等。官方已经提供了Kafka和RabbitMQ的实现,RocketMQ的实现由Alibaba负责...
Java 13 新特性全面解读
作者 l Hollis 本文经授权转载自Hollis(ID:hollischuang) 2017年8月,JCP执行委员会提出将Java的发布频率改为每六个月一次,新的发布周期严格遵循时间点,将在每年的3月份和9月份发布。 目前该版本包含的特性已经全部固定,主要包含以下五个: JEP 350,Dynamic CDS Archives JEP 351,ZGC: Uncomm...
分享靠写代码赚钱的一些门路
作者 mezod,译者 josephchang10如今,通过自己的代码去赚钱变得越来越简单,不过对很多人来说依然还是很难,因为他们不知道有哪些门路。今天给大家分享一个精彩...
技术人员要拿百万年薪,必须要经历这9个段位
很多人都问,技术人员如何成长,每个阶段又是怎样的,如何才能走出当前的迷茫,实现自我的突破。所以我结合我自己10多年的从业经验,总结了技术人员成长的9个段位,希望对大家的职...
面试官:兄弟,说说基本类型和包装类型的区别吧
Java 的每个基本类型都对应了一个包装类型,比如说 int 的包装类型为 Integer,double 的包装类型为 Double。基本类型和包装类型的区别主要有以下 4 点。
多线程编程是后台开发人员的基本功
这里先给大家分享一个小故事:在我刚开始参加工作的那年,公司安排我开发一款即时通讯软件(IM,类似于 QQ 聊天软件),在这之前我心里也知道如果多线程操作一个整型值是要加锁...
进程和线程的区别(超详细)
进程和线程 进程 一个在内存中运行的应用程序。每个进程都有自己独立的一块内存空间,一个进程可以有多个线程,比如在Windows系统中,一个运行的xx.exe就是一个进程。 线程 进程中的一个执行任务(控制单元),负责当前进程中程序的执行。一个进程至少有一个线程,一个进程可以运行多个线程,多个线程可共享数据。 与进程不同的是同类的多个线程共享进程的堆和方法区资源,但每个线程有自己的程序计数器、虚拟...
动画:用动画给面试官解释 TCP 三次握手过程
作者 | 小鹿 来源 | 公众号:小鹿动画学编程 写在前边 TCP 三次握手过程对于面试是必考的一个,所以不但要掌握 TCP 整个握手的过程,其中有些小细节也更受到面试官的青睐。 对于这部分掌握以及 TCP 的四次挥手,小鹿将会以动画的形式呈现给每个人,这样将复杂的知识简单化,理解起来也容易了很多,尤其对于一个初学者来说。 学习导图 一、TCP 是什么? TCP(Transmissio...
为什么程序员在学习编程的时候什么都记不住?
在程序员的职业生涯中,记住所有你接触过的代码是一件不可能的事情!那么我们该如何解决这一问题?作者 |Dylan Mestyanek译者 | 弯月,责编 | 屠敏出品 |...
500行代码,教你用python写个微信飞机大战
这几天在重温微信小游戏的飞机大战,玩着玩着就在思考人生了,这飞机大战怎么就可以做的那么好,操作简单,简单上手。 帮助蹲厕族、YP族、饭圈女孩在无聊之余可以有一样东西让他们振作起来!让他们的左手 / 右手有节奏有韵律的朝着同一个方向来回移动起来! 这是史诗级的发明,是浓墨重彩的一笔,是…… 在一阵抽搐后,我结束了游戏,瞬时觉得一切都索然无味,正在我进入贤者模式时,突然想到,如果我可以让更多人已不同的方式体会到这种美轮美奂的感觉岂不美哉? 所以我打开电脑,创建了一个 `plan_game.py`……
唐僧团队要裁员,你会裁谁?
提问: 西游记取经团为了节约成本,唐太宗需要在这个团队里裁掉一名队员,该裁掉哪一位呢,为什么? 为了完成西天取经任务,组成取经团队,成员有唐僧、孙悟空、猪八戒、沙和尚、白龙马。 高层领导: 观音 项目经理: 唐僧 技术核心: 孙悟空 普通团员: 猪八戒、沙和尚 司机: 白龙马 这是个很有意思的项目团队 项目经理:唐僧 得道高僧。 唐僧作为项目经理,有很坚韧的品性和极高的原则性,不达目的不罢...
2019诺贝尔经济学奖得主:贫穷的本质是什么?
2019年诺贝尔经济学奖,颁给了来自麻省理工学院的 阿巴希·巴纳吉(Abhijit Vinayak Banerjee)、艾丝特·杜芙若(Esther Duflo)夫妇和哈...
linux:最常见的linux命令(centOS 7.6)
最常见,最频繁使用的20个基础命令如下: 皮一下,这都是干货偶,大佬轻喷 一、linux关机命令: 1.shutdown命令安全地将系统关机(推荐)参数说明: [-r] 重启计算器。 [-h] 关机后关闭电源〔halt〕。 [-c] cancel current process取消目前正在执行的关机程序。 [-time] 设定关机〔shutdown〕前的时间。 shutdown -h now ...
只因写了一段爬虫,公司200多人被抓!
“一个程序员写了个爬虫程序,整个公司200多人被端了。” “不可能吧!” 刚从朋友听到这个消息的时候,我有点不太相信,做为一名程序员来讲,谁还没有写过几段爬虫呢?只因写爬虫程序就被端有点夸张了吧。 朋友说,消息很确认并且已经进入审判阶段了。 01.对消息进一步确认 朋友认识几个律师朋友,和他们有一些业务来往,得知他们想尝试把业务扩展到程序员这个群体。那段时间我刚好离职也有时间,在朋友...
相关热词 c# 中文ascii c#电话客服 c#开发管理系统实例 c#三个条件判断 c# mvc过滤器 c# 鼠标缩放图像 c# 空间后方交会 c#串口测试应用程序 c# 匹配 正则表达式 c#防止窗体重绘