1、 数据结构课程设计设计报告 课程设计题目 单独实现各种排序 2013 年 5 月 4 日 第 1 页 共 32 页 目录目录 目录 1 需求分析 2 概要设计 3 直接插入排序的设计思路 . 3 折半插入排序的设计思路 . 3 希尔排序的设计思路 . 4 冒泡排序设计思路 . 4 快速排序设计思路 . 4 直接选择排序的设计思路 . 5 堆排序的设计思路 . 5 归并排序的设计思路 . 7 基数排序的设计思路 . 8 详细设计 10 直接插入排序 . 10 折半插入排序 . 11 希尔排序 . 12 冒泡排序 . 13 快速排序 . 14 直接选择排序 . 15 堆排序 . 17 归并排序 .
2、 19 基数排序 . 21 调试分析 24 直接插入排序 . 24 折半插入排序 . 24 希尔排序 . 25 冒泡排序 . 25 快速排序 . 26 直接选择排序 . 26 堆排序 . 27 归并排序 . 28 基数排序 . 29 数据结构课程设计总结 29 课程设计的收获 . 29 遇到的问题及解决思路 . 30 对数据结构课程的思考 . 30 参考文献 31 第 2 页 共 32 页 需求分析需求分析 排序时计算机程序设计中一种重要的操作， 它的功能将包含多个 数据元素的任意序列，重新排列成一个按关键字有序的序列。 由于待排序的元素数量不同，使得排序过程中的时空开销也不 同。没有一种排序
3、算法可以适合任何一种场合，每种排序算法都有适 合的特殊环境，只有在这种特殊环境中才能发挥这种排序算法的优 势。 排序在很多的场合都会用到， 一个优秀的排序算法可以使程序的 运行效率提高，节约时空资源。 其中对整数或者是实数的排序用得最多， 大多数情况下都是要求 对一组无序的数据按照数据值的大小以增序或者以降序排列数据。 例如对一组学生的成绩从高到低排序， 以确定学生的名次。 又如 要求对员工的工资排序，以方便管理。在现实生活中要用到排序的地 方不胜枚举，虽然很多高级程序设计语言都封装了排序的算法， 用来 也方便， 程序员也容易掌握和运用， 但是这些封装好了的排序算法将 会一成不变的按照设计者当
4、初设计时设计的步骤工作， 无法在实际情 况中进行优化， 也就不以利于提高程序的总体效率，所以根据实际的 情况编写实际的排序算法才是可行的。 本次课程设计单独实现直接插入排序、折半插入排序、希尔排序、 冒泡排序、快速排序、 直接选择排序、堆排序、 归并排序、基数排序。 第 3 页 共 32 页 概要设计概要设计 直接插入排序的设计思路直接插入排序的设计思路 直接插入排序是一种最简单的排序方法，他的基本操作是将一个 数据元素直接插入到已排好序的一组数据中， 从而得到一个新的元素 数加一的有序表。 由于数据存储结构采用的是数组， 所以插入一个元素就涉及到查 找待插入元素的位置， 移动其他元素，而数组
5、头一个结点设为哨兵结 点。 如图 1 所示：在序列 1，3，5，8 中插入 4 图 1 这样就有完成了一次插入， 重复这种操作直到整个数组有序为止。 折半插入排序的设计思路折半插入排序的设计思路 折半插入排序是在直接插入排序的基础上减少了比较和移动的 次数从而提高算法的效率， 因为待插入数据前面的所有数据已经有序 了。 第 4 页 共 32 页 先用两个指针 low和 high通过折半查找的方法确定待插入数据的 位置，最后 low 所指向的位置即为待插入数据的位置，先将把待查入 数据放到 0号单元然后 low以后的单元依次后移一位然后将 0号单元 的数据插入到 low 指向的单元中，重复这个操
6、作直到整个数组有序。 希尔排序的设计思路希尔排序的设计思路 希尔排序的设计思想是：先将整个待排序数列分割成若干子序 列，对子序列分别进行直接插入排序，待整个序列基本有序时再对整 个数列进行一次直接插入排序。 冒泡排序设计思路冒泡排序设计思路 冒泡排序很简单， 首先将第一个数据的关键字和第二个数据的关键字 比较，若为逆序，则将两个数据交换，然后比较第二个和第三个数据 的关键字，以此类推，直到第 n-1 个数据和第 n 个数据进行比较。然 后重复上述操作，第 i次循环只进行到第 n-i个为止， 因为 n-i以后的 数据已经有序了。 快速排序设计思路快速排序设计思路 快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排 序将待排序记录分割成独立的两部分， 其中一部分关键字均比另一部 分关键字小，然后分别对这两部分继续排序直到
