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

内容发布更新时间 : 2024/12/23 6:40:56星期一 下面是文章的全部内容请认真阅读。

快速排序

堆排序

归并排序

退出系统

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;