数据结构课程设计报告---几种排序算法的演示(附源代码) 下载本文

快速排序

堆排序

归并排序

退出系统

3) 上机过程中出现的问题及其解决方案

1 快速排序时出现多一次排序的情况 解决方法:在进行循环体时,多运行了一次,将运行次序减1即可。

2 堆排序时也出现与上一条相同的情况 解决方法:由于缺少一个判断语句导致输出只能是偶数倍趟数,因此加一条if(len<=currentsize-1)判断语句就可以使程序正常输出结果

3 快速排序趟数开始为1 ,2 ,1, 2出现 解决方法:再定义一个全局变量,不过当其用完时,没有将它重新置为0,这样最后输出的趟数就正确了。

4 运行程序时,若输入字符,则必须输入完全后,才判断其为不正确的选择 解决方法:加一个if判断语句即可

4) 程序中可以改进的地方说明

本程序不能判断字符数大于1的字符串,这方面需要改进 可以在程序中加入性能分析,例如空间复杂度,时间复杂度等

5) 程序中可以扩充的功能及其设计实现假想

扩充功能:可以加入希尔排序等未加入的排序方法,可以加入性能分析

实现假想:加入其他排序方法后,输出为正确排序的过程,加入性能分析时,输出排序过程的同时,可以输出时间复杂度与空间复杂度

6) 收获及体会

在进行为期一个星期的课程设计中,最终完成了算法。这期间,遇到的各种麻烦也都相继解决。从这次实践中,我意识到自己还有很多不足之处。

首先先说一下基本的。对于各种排序算法的过程还是不够熟悉,进行编程时还需要翻书查找,对于这一点,只能说对数据结构的学习还不够扎实,虽然说这门课程以后就没有了,但是我想这门课对以后的学习会有很大帮助,所以有空时还应该继续熟悉这门课程。

其次,就是对于错误的处理,不能得心应手,不能正确处理一些简单的错误。对于逻辑上的错误,不能够立即找到出错点,往往需要向同学请教才能找出错误,并且改正。我觉得这是自己独自思考能力不高的问题,遇事需要自己仔细想想,若还不能改正,再请教别人也不迟。

从总体上说,整个代码的实现还是存在不足的,例如本程序不能判断字符数大于1的字符串,没有相应排序的性能分析(如空间复杂度,时间复杂度),等等。从这点看,说明自己的程序还是不够完善,不能做到十全十美,希望以后能有所修正。

总而言之,从这次的实践中我学到了很多东西,希望以后能够多加运应

7) 源代码:

#include \#include using namespace std; const int maxsize=100;

int num=0;//定义全局变量,为每一趟的输出做准备 int x=0;

templateclass sortlist {

private:

int currentsize;//数据表中数据元素的个数 public:

type *arr;//存储数据元素的向量(排序表)

sortlist():currentsize(0){arr=new type[maxsize];}//构造函数 sortlist(int n){arr=new type[maxsize];currentsize=n;} void insert(int i,type x){arr[i]=x;} ~sortlist(){delete []arr;}//析构函数

void swap(type &x,type &y)//数据元素x和y交换位置 {type temp=x;x=y;y=temp;} void bubblesort();//冒泡排序

void quicksort(int low,int high);//快速排序 void insertionsort();//直接插入排序 void binaryinsertsort();//折半插入排序 void selectsort();//简单选择排序 void heapsort();//堆排序

void mergesort(sortlist &table);//归并排序 void filterdown(const int start);//建立最大堆

void mergepass(sortlist&sourcetable,sortlist&mergedtable,const int len);//一趟归并

void merge(sortlist&sourcetable,sortlist&mergedtable,const int left,const int mid,const int right);//两路归并算法 };

template //直接插入排序 void sortlist::insertionsort()

{

type temp; int j;

for(int i=1;i<=currentsize-1;i++) {

temp=arr[i];j=i-1;

while(j>=0&&temp

cout<<\第\<<++num<<\趟排序结果为:\; for(int t=0;t

num=0; }

template //折半插入排序 void sortlist::binaryinsertsort() {

type temp;

int left,right;

for(int i=1;i

left=0;right=i-1;temp=arr[i]; while(left<=right)//找插入位置 {

int mid=(left+right)/2;

if(temp

for(int k=i-1;k>=left;k--)//向后移动 arr[k+1]=arr[k]; arr[left]=temp;

cout<<\第\<<++num<<\趟排序结果为:\; for(int t=0;t

num=0; }

template //冒泡排序 void sortlist:: bubblesort() {

int i=1;