1、 课课 程程 设设 计计 说说 明明 书书 课程名称： 数据结构和算法 设计题目： 多种排序 院 系： 计算机科学与信息工程学院 学生姓名： 学 号： 专业班级： 计科嵌入式（12-1） 指导教师： 年 月 日 1 课课 程程 设设 计计 任任 务务 书书 设计题目 表达式计算程序设计 学生姓名 所在院系 计科 专业、年级、班 12 计科 （嵌入式） 设计要求：设计要求： 1) 采用如下七种方法实现上述问题求解：插入排序、希尔排序、起泡排序、快速排 序、选择排序、堆排序、归并排序。 2) 统计每一种排序方法的性能 （以上机运行程序所花费的时间为准进行对比） ， 找出 其中两种较快的方法。并将数
2、据序列和不同的查找算法的性能结果记录入 txt 文 件。 学生应完成的工作：学生应完成的工作： 1. 利用随机函数产生 N 个随机整数（10000 以上） 。 2. 对这些数字进行排序。 3. 采用插入、希尔、起泡、快速、选择、归并、堆排序方法解决问题。 4. 对不同的排序算法进行性能比较并记录。 参考文献阅读：参考文献阅读： 1. 数据结构(C 语言版) 严蔚敏 清华大学出版社 2. C 语言程序设计 丁峻岭 中国铁道出版社 3. C 程序设计 谭浩强 清华大学出版社 工作计划：工作计划： 任务下达日期： 年 月 日 任务完成日期： 年 月 日 指导教师（签名） ： 学生（签名） ： 2 多
3、种排序多种排序 摘摘 要：要： 排序是算法中最基础的问题之一，经典的排序算法是前人不断总结得到的，基于 比较的方法是比较直观的方式，主要存在插入法排序、堆排序、希尔排序、归并排序、 快速排序，每一种排序算法都有自己的优缺点，比如插入法排序适用于那些长度短的排 序，要是长的话，有些爱莫能助啦，堆排序主要是依据了二叉堆的特性，但是创建堆的 过程也是一个复杂的问题，希尔排序的过程是一个不断精确的过程，但是目前也只是一 个经验方式。归并排序是一个递归的问题，采用分治的思想实现，但是这种算法需要额 外的存储空间，快速排序虽然是实践中比较常用的算法，但是对于有序的数组采用快速 排序就是灾难。比较型算法的时
4、间复杂度最优也只能到达 O(NlogN)。 关键词：关键词： 归并排序 快排排序 选择排序 冒泡排序 插入排序 堆排序 希尔排序 内部排序 3 目目 录录 1. 设计背景 3 1.1 问题描述 4 1.2 问题分析. 4 2.设计方案 4 2.1 算法设计. 4 2.2 功能模块分析 . 6 3.主要算法流程图 . 15 4. 结果与结论 16 4.1 正确结果 16 4.2 错误信息 18 5. 算法复杂度以及稳定性分析 . 18 6. 收获与致谢 19 7. 参考文献 19 8. 附件 20 1. 设计背景 4 1.11.1 问题描述问题描述 利用随机函数产生 N 个随机整数（10000
5、以上） ，对这些数进行多种方法进行排 序。包括：插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序。 1.21.2 问题分析问题分析 经典的排序算法是前人不断总结得到的，基于比较的方法是比较直观的方式，主要 存在插入法排序、堆排序、希尔排序、归并排序、快速排序，每一种排序算法都有自己 的优缺点。 2.设计方案 2.2.1 1 算法设计算法设计 （1）选择排序 在待排序的一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素交 换；然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换，循环到只剩 下最后一个数据元素为止。 （2）冒泡排序 相邻的两个元素进行比较，将小
6、的调到前面，大的调到后面。 （3）插入排序 待排序的记录放在数组 R0n-1中排序过程中某一时刻，R 被划分成两个子区间 5 R0,i-1 (有序和)Rin-1(无序)。直接插入的基本操作是将当前无序区的一个记录 Ri插入到有序区 R0i-1中适当的位置 （4） 快速排序 在待排序的数组的 n 个元素中取一个元素(一般取第一个)， 将其移动到这样的位置： 在其之前的元素的值都小于它，在其之后的元素都大于它，这样是一趟快速排序；然后 对数组的两个部分进行同样的操作，直到每部分只有一个记录为止；总之，每趟使表的 第一个元素放在适当位置，将表两分，再对两子表进行同样的递归划分，直至划分的子 表长度为 1。 （5）堆排序 堆排序中 heap 算法的时间复杂度与堆所对应的完全二叉树的树高度 log2n 相关。 而 heapsort 中对 heap
