数据结构关于排序的课程设计.docx

《数据结构关于排序的课程设计.docx》由会员分享，可在线阅读，更多相关《数据结构关于排序的课程设计.docx（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构关于排序的课程设计 课程设计说明书 题目：排序算法的运用与分析 姓名： 学号：_ 班级：_ _ _ X X X X大学 数理学院X X X专业 2022 年7 月8 日 目录： 一题目 (5) 二算法设计的思想 (5) 三算法的流程图 (7) 四算法设计分析 (8) 五源代码 (10) 六运行结果与分析 (19) 七总结 (22) 八参考文献 (22) 课程设计报告的内容 一、题目：排序算法比较： 1、设计目的： 1掌握各种排序的基本思想。 2掌握各种排序方法的算法实现。 3掌握各种排序方法的优劣分析及花费的时间的计算。 4掌握各种排序方法所适应的不同场合。 2、设计内容和要求 利用随

2、机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间 二、算法设计的思想： 1、冒泡排序：BubbleSort() 基本思想: 设待排序的文件为r1.n 第1趟(遍)：从r1开始,依次比较两个相邻记录的关键字：ri.key和ri+1.key,ri。若 keyri+1.key，则交换记录ri和ri+1的位置；否则,不交换。(i=1,2,.n-1) 第1趟之后,n个关键字中最大的记录移到了rn的位置上。 第2趟：从r1开始,依次比较两个相邻记录的关键字：ri.key和ri+1.key,若 ri.keyri+

3、1.key，则交换记录ri和ri+1的位置；否则,不交换。(i=1,2,.n-2) 第2趟之后,前n-1个关键字中最大的记录移到了rn-1的位置上，作完n-1趟,或者不需 再交换记录时为止。 2、选择排序：SelSort() 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数 列的最后，直到全部待排序的数据元素排完。 选择排序不像冒泡排序算法那样先并不急于调换位置，第一轮（k=1）先从arrayk开始 逐个检查，看哪个数最小就记下该数所在的位置于minlIndex中，等一轮扫描完毕，如果找 到比arrayk-1更小的元素，则把arrayminlIndex和ak-1对调

4、，这时arrayk到最后一个元 素中最小的元素就换到了arrayk-1的位置。如此反复进行第二轮、第三轮直到循环至最 后一元素。 3、直接插入排序：InsSort() 在已经排好序的序列中查找待插入的元素的插入位置，并将待插入元素插入到有序列表 中的过程。 将数组分成两部分，初始化时，前部分数组为只有第一个元素，用来存储已排序元素， 我们这里叫arr1 ；后部分数组的元素为除第一个元素的所有元素，为待排序或待插入元素， 我们这里叫arr2 。 排序时使用二层循环：第一层对arr2 进行循环，每次取后部分数组（待排序数组）里 的第一个元素（我们称为待排序元素或称待插入元素）e1 ，然后在第二层循

5、环中对arr1 （已排好序的数组）从第一个元素往后进行循环，查到第一个大于待插入元素（如果是升序 排列）或第一个小于待插入元素（如果是降序排列）e2 ，然后对arr1 从e2 元素开始往 后的所有元素向后移，最后把e1 插入到原来e2 所在的位置。这样反复地对arr2 进行循 环，直到arr2 中所有的待插入的元素都插入到arr1 中。 4、快序排序：QuickSort() 基本思想：首先在r1.n中，确定一个ri，经过比较和移动，将ri放到中间某个位 置上，使得ri左边所有记录的关键字小于等于ri.key，ri右边所有记录的关键字大于等 于ri.key。以ri为界,将文件划分为左、右两个子文

6、件。 用同样的方法分别对这两个子文件进行划分, 得到4个更小的子文件。继续进行下去, 使得每个子文件只有一个记录为止,便得到原文件的有序文件。 例. 给定文件(20,05,37,08,63,12,59,15,44,08)，选用第1个元素20进行划分: 5、归并排序：MegeSort() 假定文件(r1,r2,.,rn)中记录是随机排列的,进行2-路归并排序，首先把它划分为长度 均为1的n个有序子文件，然后对它们逐步进行2路归并排序。其步骤如下： 第1趟：从r1.n中的第1个和第2个有序子文件开始,调用算法merge,每次归并两个相 邻子文件,归并结果放到y1.n中。在y中形成 n/2 个长度为

7、2的有序子文件。若n为 奇数,则y中最后一个子文件的长度为1。 第2趟：把y1.n看作输入文件,将 n/2 个有序子文件两两归并,归并结果回送到 r1.n中,在r中形成 n/2 /2 个长度为4的有序子文件。若y中有奇数个子文件，则r 中最后一个子文件的长度为2。 共计经过 log2n 趟归并,最后得到n个记录的有序文件。 6、堆排序：HeapSort() 堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小 于)其左右孩子(若存在)结点的关键字。 1、N（N1）个节点的的完全二叉树从层次从左自右编号，最后一个分枝节点（非叶子节点） 的编号为 N/2 取整。2、且对于编

8、号 i（1N，则没有右孩子，否则其右孩子为2i+1。 3、这里使用完全二叉树只是为了好描述算法，它只是一种逻辑结构，真真在实现时我们还 是使用数组来存储这棵二叉树的，因为完全二叉树完全可以使用数组来存储。 堆排序其实最主要的两个过程：第一步，创建初始堆；第二步，交换根节点与最后一个非叶 子节 从最后一个非叶子节点为开始向前循环每个会支节点，比较每个分支节点与他左右子节点，如果其中某个子节点比父节点大，则与父节点交换，交换后原父节点可能还小于原子节点的子节点，所以还需 对原父节点进行调整，使用原父节点继续下沉，直到没有子节点或比左右子节点都大为止，调用过程可通过递归完成。当某个非叶子节点调整完毕

9、后，再处理下一个非叶子节点，直到根节点也调整完成，这里初始堆就创建好了，这里我们创建的是大顶堆，即大的元素向树的根浮，这样排序最后得到的结果为升序，因为最大的 将树中的最后一个元素与堆顶元素进行交换，并从树中去掉最后叶子节点。交换后再按创建初始堆的算法调整根节点，如此下去直到树中只有一个节点为止。 三、算法的流程图 四、算法设计分析： 1、冒泡排序：bubbleSort() 冒泡排序算法分析： (1)最好情况, 待排序的文件已是有序文件: 只需要进行1趟排序,共计比较关键字的次数为n1,不交换记录。 (2)最坏情况, 要经过n-1趟排序， 所需总的比较关键字的次数为 :(n-1)+(n-2)+

10、.+1n(n-1)/2 交换记录的次数最多为:(n-1)+(n-2)+.+1n(n-1)/2 移动记录次数最多为:3n(n-1)/2。 (3)只需要少量中间变量作为辅助空间。 算法是稳定的。 2、选择排序：selSort() 选择排序算法分析： (1)比较次数，在任何情况下,均为 (2)交换记录的次数 在最好情况下,原n个记录递增有序：不移动记录。 在最坏情况下共交换记录n-1对,移动记录数3(n-1)次。 故,时间复杂度为O(n2)。 (3)只需少量中间变量作为辅助空间。 (4)算法是不稳定的。 3、直接插入排序：insSort() 直接插入排序算法分析： 故,时间复杂度为O(n2)。 (4

11、)只需少量中间变量作为辅助空间。 (5)算法是稳定的。 4、快序排序：QuickSort () 快速排序算法分析： (1)就平均速度而言， 快速排序是已知内部排序方法中最好的一种排序方法,其时间复杂度为O(nlog(n)。 (2)在最坏情况下， 快速排序所需的比较次数和冒泡排序的比较次数相同,其时间复杂度为O(n2)。 (3)快速排序需要一个栈作辅助空间，用来实现递归处理左、右子文件。在最坏情况下,递归深度为n，所需栈的空间大小为O(n)。 (4)快速排序是不稳定的。 5、归并排序：MegerSort() 归并排序算法分析： (1)对n个记录的文件进行归并排序,共需log2n趟, (2)每趟所

12、需比较关键字的次数不超过n, 共比较O(nlog2n)次。 (3)每趟移动n个记录, 共移动记录O(nlog2n)个 (4)归并排序需要一个大小为n的辅助空间y1.n。 (5)归并排序是稳定的。 6、堆排序：HeapSort() 堆排序算法分析： (1)堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。 (2)堆排序的最坏时间复杂度为O(nlgn)。 (3)堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 (4)堆排序是就地排序，辅助空间为O(1)。 (5)它是不稳定的排序方法 五、源代

13、码： #include #include #include #include #include /外部变量定义 int count1=0,bj1=0,yd1=0; int count2=0,bj2=0,yd2=0; int count3=0,bj3=0,yd3=0; int count4=0,bj4=0,yd4=0; int count5=0,bj5=0,yd5=0; int count6=0,bj6=0,yd6=0; clock_t start1,finish1; clock_t start2,finish2; clock_t start3,finish3; clock_t start4,f

14、inish4; clock_t start5,finish5; clock_t start6,finish6; int b6=finish1-start1,finish2-start2,finish3-start3,finish4-start4,finish5-start5,finish6-start6; template class an public: void selectsort(T A,int n);/简单选择排序 void insertsort(T A,int n);/直接插入排序 void shellsort(T A,int n); /希尔排序 void bubblesort(T

15、 A,int n);/冒泡排序 void quicksort(T A,int n);/快速排序 void mergesort(T A,int n);/两路合并排序 private: void merge(T A,int i1,int j1,int i2,int j2); void qsort(T A,int left,int right); ; template void an:selectsort(T A,int n) /简单选择排序 int small; start3=clock(); for(int i=0;i0 & temp bj1+; Aj=Aj-1; j-; yd1+; Aj=temp;