排序算法比较实验报告

时间：2024.4.14

1课程设计名称

排序算法的比较

概述

排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。内部排序算法主要分为5 大类，有十二个算法。插入排序类、交换排序类、选择排序类、归并排序类和基数排序类。算法主要包括：插入排序、折半插入排序、选择排序、冒泡排序、希尔排序、快速排序、堆排序、归并排序、基数排序等。

2使用工具软件

Microsoft Visual C++ 6.0

3 课程设计内容简介

3.1课程设计内容

掌握各种排序算法（直接插入排序、冒泡排序、快速排序、简单选择排序）的思路核比较他们之间的优劣。

3.2 基本要求

1.任意性：系统首先生成1000个随机整数，然后分别用不同的排序方法对其进行升序排序，给出每种方法的比较次数或所用时间

2.友好性：界面要友好，输入有提示，尽量展示人性化

3.可读性：源程序代码清晰、有层次

4.健壮性：用户输入非法数据时，系统要及时给出警告信息

3.3 课程设计思想

程序设计的总体思路：首先构建main()函数，根据题目的要求，再分别构建四个排序函数：冒泡排序函数（long Bubblesort(long R[], long n)）、选择排序函数（long selectsort(long R[],long n)）、直接插入排序函数（long insertsort(long R[], long n)）和快速排序函数（void QuickSort(long R[],long n)）。为了使程序具有可读性和层次感，建立一个导航函数（void DaoHang()）和操作函数（void operate(long a[], long n)），其中，void DaoHang()用来告知用户程序的操作流程，void operate(long a[], long n)用来接收用户不同的选择，从而调用其它函数。

3.4 程序分析

3.4.1 存储结构

顺序存储结构（如图1）

示意图

图1

3.4.2 关键算法分析

关键算法1

实现四种算法的基本排序功能

1．冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。

实现过程（如图2）。

对于数组（21 25 49 16 08）。

初态：

第一趟：

第二趟：

第三趟：

第四趟：

图2

2．选择排序：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。

实现过程（如图3）。

对于数组（21 25 49 16 08）。

初态：

第一趟：

第二趟：

第三趟：

图3

3．直接插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。

实现过程（如图4）。

对于数组（21 25 49 16 08）。

初态：

第一趟：

第二趟：

第三趟：

第四趟：

第五趟：

图4

4．快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成。

实现过程（如图5）

对于数组（21 25 49 16 08）。

初态：

R[0]=21

low

第一趟：

R[0]=21

low

R[0]=21

low

R[0]=21

low=high

图5

关键算法二

获取当前系统时间，精确到毫秒，分别在代码运行前后调用记录前后时间，再相减即可得到代码运行时间。

//以冒泡排序为例

start=(double)clock();//开始

Bubblesort(R, n);

end=(double)clock();//结束

Time = (double)(end-start)/CLK_TCK;//相减，精确到毫秒

关键算法三：

实现手动与计算机随机双重输入。手动输入检查程序的正确性，计算机随即输入，可以比较各排序算法的性能。

void Rand()//随机数函数

void HandInput()//手动输入函数

关键算法四

纠错功能。在用户输入非法数据时，给予警告，并要求用户重新输入，不必重启程序。

3.4.3时间复杂度与空间复杂度：

理论分析可以得出各种排序算法的时间复杂度和空间复杂度，如下表所示（图6）：

图6

3.4.4 选择排序算法的依据

影响排序的因素有很多，平均时间复杂度低的算法并不一定就是最优的。相反，有时平均时间复杂度高的算法可能更适合某些特殊情况。同时，选择算法还得考虑它的可读性，以利于软件的维护。一般而言，需要考虑的因素有以下4 点：

u 待排序的记录数目n 的大小。

u 记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小。

u 关键字的结构及其分布情况。

u 对排序稳定性的要求。

3.5 程序流程图

流程图: 可选过程: main()

图7

3.6 运行环境

Microsoft Visual C++ 6.0/WIN32 Console Application

3.7运行结果

3.7.1当手动输入五个数据时，运行结果（如图8）

图8

3.7.2当选择随机数时，运行结果(如图9)

图9

3.8 得意之处

得意之处1

将时间精确到毫秒，使得实验结果更容易观察比较。

代码如下（冒泡排序为例）：

start=(double)clock();

degree = Bubblesort(R, n);

end=(double)clock();

Time = (double)(end-start)/;

其中CLK_TCK值为1000，即将时间精确到毫秒（图10）。

图10

得意之处2

将排序过程的每一趟输出，并且将已排好序的用中括号括起来，这样以来，可以直接看出排序过程是否正确以及深入了解排序过程的每一步。

如：对于冒泡排序（图11）

图11

得意之处3

冒泡排序算法中，运用做标记的方法，使得排序得到正确结果后，便停止做不必要的循环。

代码如下

while(i>1)

{

long lastExchangeIndex=1;//表示已经有序

for(long j=1;j<i;j++)

if(R[j+1]<R[j])

{

long t=R[j];

R[j]=R[j+1];

R[j+1]=t;

BT++;

lastExchangeIndex=j;//记下进行的位置

}

i=lastExchangeIndex;//本趟进行过交换的最后一个记录的位置

}

4 课程设计中目前存在问题

1．交换次数统计不够精确。

2．无论时间还是移动次数，应该有一个对比结果，不能只是罗列出来。

3．对于快速排序，存在两个问题。其一，不能两边同时进行排序，使得排序趟数增加；其二，没能格式化输出，使得输出不清晰，不美观。

5 自我感受

1．在初期构思代码的时候，首先构造了各种算法的基本实现代码，已经能够实现四种排序的基本功能，并且测试无误。后来考虑能否优化本程序，首先考虑到测试算法的需求，需要大量随机数，因为增添了随机函数发生函数，满足各种测试条件的需求。之后考虑如何能简化代码以实现多达四种排序算法的简单调用和性能指标统计、算法时间的精确而简易的统计、算法移动次数和比较次数的精确统计。调用精确的系统函数实现时间的统计。此外还添加了一系列优化，使得程序的结构变得更加合理，版面风格也变得好看，可读性增强。

2．程序的优化是一个艰辛的过程，如果只是实现一般的功能，将变得容易很多，当加上优化，不论是效率还是结构优化，都需要精心设计。这次做优化的过程中，遇到不少阻力。因而以后要多花力气学习C++编程语言，必须要加强这方面的训练，这样才能在将编程思想和数据结构转换为代码的时候能得心应手。

3．这次课设通过在网上查阅大量资料、程序以及一些学术论文，很好的对内排序算法进行了研究，特别对数据结构这门课所学到的内容付诸于实践，加深了理解。另外，还学到了一写别的方面的知识。

这次课设做还有许多没有考虑周到的地方，希望老师指出。

6参考文献

[1] 严蔚敏吴伟民，数据结构（C语言版），北京:清华大学出版社,2007。

[2] 汪祖柱沈晓潞，基于C语言实现的若干排序算法和分析，安徽电气工程职业学院学报，第九卷第一期。

[3] 王莉，常用内部排序算法的比较与选择，软件导刊，20##年1月号。

[4] 赵延惠，排序方法及效率浅析，思茅师范高等专科学校学报，第18卷

附录：程序

#include <iostream>

#include<stdio.h>

#include <stdlib.h>

#include <time.h>

#include <iomanip>

#define MAX 100000000

using namespace std;

void print(long R[],long n)

{

for(int i=1;i<=n;i++)

cout<<setw(4)<<R[i];

}

//------------------------------------------------------------------------------

//冒泡排序

//------------------------------------------------------------------------------

long Bubblesort(long R[], long n)

{

long y=1;

long i,BT=0;

i=n;

while(i>1)

{

long lastExchangeIndex=1;//表示已经有序

for(long j=1;j<i;j++)

if(R[j+1]<R[j])

{

long t=R[j];

R[j]=R[j+1];

R[j+1]=t;

BT++;

lastExchangeIndex=j;//记下进行的位置

}

i=lastExchangeIndex;//本趟进行过交换的最后一个记录的位置

cout<<"第"<<y<<"趟:";

y++;

for(long x=1;x<=i;x++)

cout<<setw(4)<<R[x];

cout<<setw(3)<<"["<<R[i+1];

for(x=i+2;x<=n;x++)

cout<<setw(4)<<R[x];

cout<<"]";

cout<<endl;

}

return BT;

}

//------------------------------------------------------------------------------

//选择排序

//------------------------------------------------------------------------------

//static long ST=0;

long SelectMinKey(long R[],long i,long n)//在 R[i..R.length] 中选择关键字最小的记录

{

long temp=i;//记录最小的元素值的位置

for(int j=i;j<=n;j++)

{

if(R[temp]>R[j])

{

temp=j;

//ST++;

}

return temp;

}

long selectsort(long R[],long n)

{

long j,i,t;

long y=1;

int ST=0;

for( i=1;i<n;i++)

{

j = SelectMinKey(R,i,n);// 在 L.r[i..L.length] 中选择关键字最小的记录

if (i!=j) // 与第 i 个记录交换

{

t=R[i];

R[i]=R[j];

R[j]=t;

ST++;

}

cout<<"第"<<y<<"趟:"<<' ';

y++;

for(long x=1;x<=i;x++)

cout<<setw(4)<<R[x];

cout<<setw(3)<<"["<<R[i+1];

for(x=i+2;x<=n;x++)

cout<<setw(4)<<R[x];

cout<<"]";

//print(R,n);

cout<<endl;

}

return ST;

}

//------------------------------------------------------------------------------

//直接插入排序

//------------------------------------------------------------------------------

long insertsort(long R[], long n)

{

long y=1;

long IT=0,j;

for(long i=2;i<=n;++i)

{

if(R[i]<R[i-1])

{

R[0]=R[i];//复制为哨兵

IT=IT+1;

for( j=i-1;R[0]<R[j];--j)

{

R[j+1]=R[j];//记录后移

IT=IT+1;

}

R[j+1]=R[0];//插入到正确位置

IT=IT+1;

}

cout<<"第"<<y<<"趟:"<<' ';

y++;

cout<<setw(4)<<"["<<R[1];

for(long x=2;x<=i;x++)

cout<<setw(4)<<R[x];

cout<<"]";

for(x=i+1;x<=n;x++)

cout<<setw(4)<<R[x];

cout<<endl;

}

return IT;

}

//------------------------------------------------------------------------------

// 快速排序

//------------------------------------------------------------------------------

static long QT=0;

int Partition (long R[], long low, long high,long n)

{

R[0] =R[low];

long pivotkey = R[low]; // 枢轴

QT=QT+2;

while (low<high)

{

while(low<high&& R[high]>=pivotkey)// 从右向左搜索

-- high;

R[low] = R[high];

QT=QT+1;

while (low<high && R[low]<=pivotkey)// 从左向右搜索

++ low;

R[high] = R[low];

}

QT=QT+1;

R[low] =R[0];

QT=QT+1;

return low;

}// Partition

void quicksort (long R[], int low, int high,long n,long y)// 对记录序列L.r[low..high]进行快速排序

{

if (low < high) // 长度大于1

{

long pivotloc = Partition(R,low,high,n);// 对 L.r[low..high] 进行一次划分

QT=QT+1;

cout<<"第"<<y<<"趟:";

y++;

print(R,pivotloc-1);

cout<<setw(2)<<"["<<R[pivotloc];

cout<<"]";

for(long x=pivotloc+1;x<=n;x++)

cout<<setw(5)<<R[x];

cout<<endl;

quicksort(R, low, pivotloc-1,n,y); // 对低子序列递归排序

quicksort(R, pivotloc+1, high,n,y); // 对高子序列递归排序

}

} // QSort

void QuickSort(long R[],long n)

{

long y=1;

quicksort(R,1,n,n,y);

}

//------------------------------------------------------------------------------

//操作选择函数

//------------------------------------------------------------------------------

void operate(long a[], long n)

{

void main();

long * R = new long [n];

time_t start, end;//定义两个变量

double Time;//排序时间

long degree;//排序次数

char ch;

cout << "请选择排序算法：\t";

cin >> ch;

switch(ch){

case '1':

{

cout<<'\n';

cout<<"\t==您选择的是冒泡排序=="<<'\n';

for(int i = 1; i <=n; i ++)//将随机数付给R[i]

{

R[i] = a[i];

}

start=(double)clock();

degree = Bubblesort(R, n);

end=(double)clock();

Time = (double)(end-start)/CLK_TCK;

//print(R,n);

cout << '\n';

cout << "冒泡排序所用时间：\t" << Time << '\n';

cout << "冒泡排序交换次数：\t" << degree << '\n';

cout<<'\n';

operate(a, n);

break;

}

case '2':

{

cout<<'\n';

cout<<"\t==您选择的是选择排序=="<<'\n';

for(int i = 1; i <= n; i ++)

{

R[i] = a[i];

}

start=(double)clock();

degree = selectsort(R, n);

end=(double)clock();

Time = (double)(end-start)/CLK_TCK;

//print(R,n);

cout<<'\n';

cout << "选择排序所用时间：\t" << Time << '\n';

cout << "选择排序交换次数：\t" << degree << '\n';

cout << '\n';

operate(a, n);

break;

}

case '3':

{

cout<<'\n';

cout<<"\t==您选择的是直接插入排序=="<<'\n';

for(int i=1; i<=n; i ++)

{

R[i] = a[i];

}

start=(double)clock();

degree = insertsort(R, n);

end=(double)clock();

Time = (double)(end-start)/CLK_TCK;

//print(R,n);

cout<<'\n';

cout << "直接插入排序所用时间： " << Time<< '\n';

cout << "直接插入排序交换次数： " << degree << '\n';

cout << '\n';

operate(a, n);

break;

}

case '4':

{

cout<<'\n';

cout<<"\t==您选择的是快速排序=="<<'\n';

for(int i=1; i<=n; i ++)

{

R[i] = a[i];

}

start=(double)clock();

QuickSort(R, n);

end=(double)clock();

Time = (double)(end-start)/CLK_TCK;

cout<<'\n';

cout << "快速排序所用时间：\t" << Time << '\n';

cout << "快速排序交换次数：\t" << QT << '\n';

cout << '\n';

operate(a, n);

break;

}

case 'a':

{

main();

break;

}

default:

{

cout << "输入错误，请选择正确的操作！" << '\n';

operate(a, n);

break;

}

case '0':

{

cout<<"您已选择退出程序，谢谢使用"<<'\n';

break;

}

//------------------------------------------------------------------------------

//导航菜单函数

//------------------------------------------------------------------------------

void DaoHang()

{

cout<<"\n** 排序算法比较 **"<<endl;

cout<<"*****************************************************"<<endl;

cout<<"== 1 --- 冒泡排序 =="<<endl;

cout<<"== 2 --- 选择排序 =="<<endl;

cout<<"== 3 --- 直接插入排序 =="<<endl;

cout<<"== 4 --- 快速排序 =="<<endl;

cout<<"== 0 --- 退出程序 =="<<endl;

cout<<"== a --- 改变随机数的个数 =="<<endl;

cout<<"*****************************************************"<<endl;

}

//--------------------------------------------------------------------------------

//随机输入函数

//--------------------------------------------------------------------------------

void Rand()

{

cout << "\n请输入要产生的随机数的个数（0<=n<=100000000）："<<endl;

long int n;

cin >> n;

cout << endl;

long *a = new long [n];

srand((unsigned long)time(NULL));//产生一个以当前时间开始的随机种子

for (long i=1; i<=n; i++)

{

a[i] = rand() % n;//n为最大值,其随机域为0~n-1

}

DaoHang();

print(a,n);

operate(a, n);

}

//--------------------------------------------------------------------------------

//手动输入函数

//--------------------------------------------------------------------------------

void HandInput()

{

cout<<"请输入数据个数："<<endl;

int n;

cout<<"n=";

cin>>n;

cout << endl;

long *a = new long [n];

for (long i=1; i<=n; i++)

{

cin>>a[i] ;

}

DaoHang();

operate(a, n);

}

//------------------------------------------------------------------------------

//主函数

//------------------------------------------------------------------------------

void main()

{

loop:

cout<<"手动输入请按 1 ，随机输入请按 2 "<<endl;

int x;

cin>>x;

switch(x)

{

case 2:{

Rand();

break;

}

case 1:{

HandInput();

break;

}

default:

cout<<"输入错误,请重新输入!"<<endl;

goto loop;

}

更多相关推荐：

排序算法实验报告: 实验课程算法分析与设计实验名称几种排序算法的平均性能比较验证型实验实验目标1几种排序算法在平均情况下哪一个更快2加深对时间复杂度概念的理解实验任务1实现几种排序算法selectionsortinsertions...
数据结构排序算法实验报告: 《数据结构》课程设计报告
数据结构排序实验报告: 数据结构课程设计报告实验五排序一需求分析本演示程序用C60编写完成各种排序的实现对输入的一组数字实现不同的排序方法对其由小到大顺序输出1分别对直接插入排序希尔排序冒泡排序快速排序选择排序堆排序算法进行编写2对存...
查找排序实验报告: 实验十查找排序计算机学院12级2班1211020xx李龙实验目的1掌握折半查找算法的思想2实现折半查找的算法3掌握常见的排序算法插入排序交换排序选择排序等的思想特点及其适用条件4能够分析各种算法的效率5熟练的掌...
算法设计与分析实验报告--排序: 计算机算法设计与分析实验报告学号20xx211773姓名吕功建班级0411103实验一快速排序一实验目的1以排序分类问题为例掌握分治法的基本设计策略2熟练掌握一般插入排序算法的实现3熟练掌握快速排序算法的实现4...
排序算法比较系统实验报告: 排序算法比较系统一项目计划书1项目的选题意义随着计算机科学技术的快速发展排序成为了计算机程序设计中的一种重要操作它在计算机图形计算机辅助设计机器人模式识别及统计学等领域具有广泛应用在实际应用当中比如数据统计等方...
实验报告-各种排序方法及其实现: 计算机学院实验报告专用纸实验室网络实验室机号网38实验日期20xx年6月25日1计算机学院实验报告附页2计算机学院实验报告附页3计算机学院实验报告附页4计算机学院实验报告附页5计算机学院实验报告附页6计算机学院...

实验报告一快速排序并行实现_谢有军: 一实验目的通过实现某种排序算法的并行化熟悉openMP的编程原理和基本编写技巧和步骤并能了解并行算法较串行算法的优越性二实验内容设计一个排序算法并将其改成并行算法观察串行与并行的性能差别三实验步骤四341快速排...
算法分析与设计实验报告: 算法分析与设计实验报告，内容附图。
排序算法比较实验报告: 信息学部算法分析上机报告学号姓名指导老师时间090107021101秦明一上机实验题目实验1比较归并排序和快速排序的区别实验2利用贪心算法对背包问题进行求解二算法设计思路归并排序申请空间使其大小为两个已经排序序...
内部排序算法的实现的实验报告: 班级学号姓名实验组别试验日期室温报告日期成绩报告内容目的和要求原理步骤数据计算小结等实验名称内部排序算法的实现实验目的掌握直接插入排序希尔排序快速排序的实现实验环境硬软件要求Windows20xxVisualC...
软件基础实验报告之排序算法: 软件基础上机题之排序算法1软件基础上机题之排序算法2软件基础上机题之排序算法includequotstdafxhquotincludequotstdiohquotincludequotstdlibhquotin...

排序算法实验报告（36篇）

热门关注

算法分析与设计实验报告-合并排序、快速排序

算法设计实验报告

终稿- -算法设计与分析实验报告格式 3

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

微机原理实验报告冒泡法对数据排序

shiweijie《算法分析与设计》实验指导与报告书

算法实验报告

内部排序实验报告