单独实现各种排序.doc

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