数据结构课程设计--单独实现各种排序

《数据结构课程设计--单独实现各种排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、湖北民族学院信息工程学院2011级计算机专业班数据结构课程设计设计报告数据结构课程设计设计报告课程设计题目单独实现各种排序学生姓名学生学号学院名称信息工程学院指导教师2013年5月4日v湖北民族学院信息工程学院2011级计算机专业班数据结构课程设计设计报告v目录v目录1v需求分析3v概要设计4Ø直接插入排序的设计思路4Ø折半插入排序的设计思路4Ø希尔排序的设计思路5Ø冒泡排序设计思路5Ø快速排序设计思路5Ø直接选择排序的设计思路6Ø堆排序的设计思路6Ø归并排序的设计思路8Ø基数排序的设计思路9v详细设计11Ø直接插入排序11Ø折半

2、插入排序12Ø希尔排序13Ø冒泡排序15Ø快速排序16Ø直接选择排序17Ø堆排序18Ø归并排序20Ø基数排序22v调试分析25Ø直接插入排序25Ø折半插入排序26Ø希尔排序27Ø冒泡排序27Ø快速排序28Ø直接选择排序28Ø堆排序29Ø归并排序29Ø基数排序30v数据结构课程设计总结31Ø课程设计的收获31Ø遇到的问题及解决思路32Ø对数据结构课程的思考32v参考文献33第1页共32页湖北民族学院信息工程学院2011级计算机专业班数据结构课程设计设计报告v需求分析排序时计算机程序设计中一种重要的操作，它的功能将包含多个数据元素的任

3、意序列，重新排列成一个按关键字有序的序列。由于待排序的元素数量不同，使得排序过程中的时空开销也不同。没有一种排序算法可以适合任何一种场合，每种排序算法都有适合的特殊环境，只有在这种特殊环境中才能发挥这种排序算法的优势。排序在很多的场合都会用到，一个优秀的排序算法可以使程序的运行效率提高，节约时空资源。其中对整数或者是实数的排序用得最多，大多数情况下都是要求对一组无序的数据按照数据值的大小以增序或者以降序排列数据。例如对一组学生的成绩从高到低排序，以确定学生的名次。又如要求对员工的工资排序，以方便管理。在现实生活中要用到排序的地方不

4、胜枚举，虽然很多高级程序设计语言都封装了排序的算法，用来也方便，程序员也容易掌握和运用，但是这些封装好了的排序算法将会一成不变的按照设计者当初设计时设计的步骤工作，无法在实际情况中进行优化，也就不以利于提高程序的总体效率，所以根据实际的情况编写实际的排序算法才是可行的。本次课程设计单独实现直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序。第31页共32页湖北民族学院信息工程学院2011级计算机专业班数据结构课程设计设计报告v概要设计Ø直接插入排序的设计思路直接插入排序是一种最简单的

5、排序方法，他的基本操作是将一个数据元素直接插入到已排好序的一组数据中，从而得到一个新的元素数加一的有序表。由于数据存储结构采用的是数组，所以插入一个元素就涉及到查找待插入元素的位置，移动其他元素，而数组头一个结点设为哨兵结点。如图1所示：在序列1，3，5，8中插入4图1这样就有完成了一次插入，重复这种操作直到整个数组有序为止。Ø折半插入排序的设计思路折半插入排序是在直接插入排序的基础上减少了比较和移动的次数从而提高算法的效率，因为待插入数据前面的所有数据已经有序了。第31页共32页湖北民族学院信息工程学院2011级计算机专业班数据

6、结构课程设计设计报告先用两个指针low和high通过折半查找的方法确定待插入数据的位置，最后low所指向的位置即为待插入数据的位置，先将把待查入数据放到0号单元然后low以后的单元依次后移一位然后将0号单元的数据插入到low指向的单元中，重复这个操作直到整个数组有序。Ø希尔排序的设计思路希尔排序的设计思想是：先将整个待排序数列分割成若干子序列，对子序列分别进行直接插入排序，待整个序列基本有序时再对整个数列进行一次直接插入排序。Ø冒泡排序设计思路冒泡排序很简单，首先将第一个数据的关键字和第二个数据的关键字比较，若为逆序，则将两个数据

7、交换，然后比较第二个和第三个数据的关键字，以此类推，直到第n-1个数据和第n个数据进行比较。然后重复上述操作，第i次循环只进行到第n-i个为止，因为n-i以后的数据已经有序了。Ø快速排序设计思路快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分关键字均比另一部分关键字小，然后分别对这两部分继续排序直到整个有序。如图2所示：第31页共32页湖北民族学院信息工程学院2011级计算机专业班数据结构课程设计设计报告第一次找到3的位置3和6交换，1和4交换；第二次找到1的位置1和2交换，6

8、的位置不变；第三次找到4的位置4和5交换，至此整个序列有序。图2Ø直接选择排序的设计思路一趟直接选择排序的操作为：通过n-i次关键字间的比较，从n-i+1个数据中选出关键字最小的数据，并和第i个数据交换，重复n-1次就得到了一个有序的序列。Ø堆排序