数据结构课程设计报告(各种排序实现及对比)

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

1、课程设计报告课程名称数据结构课题名称1.成绩排序2.通讯录管理专业计算机科学与技术班级计算机1281学号04姓名刘恒指导教师刘铁武　　　　2014年6月22日35设计题目成绩各种排序一、算法设计的思想3.1简单选择排序     <1> 基本思想每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列的第i个关键字。3.5快速排序  <1> 基本思想      快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r]，如果规模足够小则直接进行排序，否则分三步处理：     分解(Di

2、vide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。     递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。  合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。   35一、算法的流程图4.1主函数的算法流程图开始输入数据个数lengthcrea

3、te(),visit()输入select7select6543210select_sort(L);Zhijie(L);ShellSort(L,dlta,4);Maopao(L);QuickSort(L);print(num);select_sort(L);QuickSort(L);Maopao(L);ShellSort()Zhijie(L)Exit(0)输入y/nny结束354.6快速排序的算法流程图（1）开始Low

4、77L.r[low]=L.r[high]Low=pivotkey77真L.r[0]=L.r[low]Pivotkey=L.r[low].key假L.r[high]=L.r[low]结束L,low,high假354.7快速排序的算法流程图（2）开始真Low

5、c=partioion(L,low,high),low=low,high=pivotloc-1;QSort(L,low,pivotloc-1)结束算法设计分析5.5快速排序35快速排序是通过比较关键码、交换记录，以某个记录为界(该记录称为支点)，将待排序列分成两部分。其中，一部分所有记录的关键码大于等于支点记录的关键码，另一部分所有记录的关键码小于支点记录的关键码。我们将待排序列按关键码以支点记录分成两部分的过程，称为一次划分。对各部分不断划分，直到整个序列按关键码有序。【效率分析】空间效率：快速排序是递归的，每层递归

6、调用时的指针和参数均要用栈来存放，递归调用层次数与上述二叉树的深度一致。因而，存储开销在理想情况下为O(log2n)，即树的高度；在最坏情况下，即二叉树是一个单链，为O(n)。时间效率：在n个记录的待排序列中，一次划分需要约n次关键码比较，时效为O(n)，若设T(n)为对n个记录的待排序列进行快速排序所需时间。理想情况下：每次划分，正好将分成两个等长的子序列，则T(n)≤cn+2T(n/2)c是一个常数≤cn+2(cn/2+2T(n/4))=2cn+4T(n/4)≤2cn+4(cn/4+T(n/8))=3cn+8T(n

7、/8)······≤cnlog2n+nT(1)=O(nlog2n)最坏情况下：即每次划分，只得到一个子序列，时效为O(n2)。快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取支点记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。排序方法最好时间平均时间最坏时间稳定性插入排序直接插入排序O(n)O(n2)O(n2)稳定希尔排序O(n1.5)

8、不稳定交换排序冒泡排序O(n)O(n2)O(n2)稳定快速排序O(nlogn)O(nlogn)O(n2)不稳定选择排序直接选择排序O(n2)O(n2)O(n2)不稳定内部排序各种算法的性能比较(表)35一、源代码#include"stdlib.h"#include"stdio.h"#include"time.h"#defineMA