数据结构课程设计(排序综合)第四次实验

本周的实验主要做快速排序，自己随机生成10000个数据，用快速排序算法，输出排序完成所需时间，再用其他排序方法做比较，至少完成两个算法的效率比较

1 问题要求及任务描述

1.1 题目要求

利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。 要求：

1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。

2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。

3)如果采用4种或4种以上的方法者，可适当加分。 1.2 主要任务

分别实现直接插入、直接选择、冒泡、快速排序、堆排序的算法。从时间的角度来分析各种排序的性能。通过测试多组数据来掌握各种排序的方法及适用场合，并能在解决实际问题灵活运用。在编写代码的时候，有以下几个问题：

（1）建立一个主函数，在主函数中要有菜单界面，和输入功能键相应执行的功能。并且要求能循环使用系统。

（2）分别实现直接插入、直接选择、冒泡、快速排序、堆排序的算法。 （3）通过冒泡排序法来测试每组数据用那种排序算法最优。

2 解决问题的主要思路和方法

2.1 关键问题

核心问题: 排列组合 数据模型（逻辑结构）：30000个随机数 存储结构: 保存在不同的文件

核心算法: 直接插入、直接选择、冒泡、快速排序、堆排序的算法 输入数据: 初始化数组：rand()P000+1 输出数据：排序内容到文件，排序所用时间

2.2 拟采用解决问题的方法

把程序分为多个模块，有的是排序的算法如：void InsertSort(int a[],int p)，有的是计算排序所用时间的函数如：double TInsertSort(int a[],int p)，还有显示菜单的模块void menu()和显示排序结果模块void Disp(int a[])等等，各个模块之间可以互相调用，节省了资源。用case作为各个功能的入口。用QueryPerformanceFrequency（）和QueryPerformanceCounte（）函数计时，精度比用clock（）高，避免了很多时候因排序速度太快而出现运行时间为0的现象。用srand函数作为随机数发生器的初始化函数，用rand产生随机数。把计算得的排序时间存入数组并经冒泡排序得出最快的两种排序法。 下面是所用排序法的算法思想：

（1）直接插入排序的基本思想是基于插入，开始假定第一个记录有序，然后从第二个记录开始，依次插入到前面有序的子文件中。即将记录a[i](2<=i<=n)插入到有序子序列a[1..i-1]中，使记录的有序序列从a[1..i-1]变为a[1..i] ，最终使整个文件有序。共进行n-1趟插入。最坏时间复杂度是0(n)，平均时间复杂度是0(n)，空间复杂度是O(1)，是稳定排序。

（2）直接选择排序的基本思想是基于选择，开始有序序列长度为零，第i(1<=i

(3)冒泡排序：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直到第N-1和第N个记录的关键字进行过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序，对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序。

(4)快速排序思想：从待排序列中任取一个元素 (例如取第一个) 作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。

(6)堆排序基本思想是：堆是n个元素的序列，先建堆，即先选得一个关键字最大或最小的记录，然后与序列中最后一个记录交换，之后将序列中前n-1记录重新调整为堆（调堆的过程称为“筛选”），再将堆顶记录和当前堆序列的最后一个记录交换，如此反复直至排序结束。优点是在时间性能与树形选择排序属同一量级的同时，堆排序只需要一个记录大小供交换用的辅助空间，调堆时子女只和双亲比较。避免了过多的辅助存储空间及和最大值的比较。

2

2

2

2

2.3 主要算法和处理流程图

开始 显示菜单 1 直接插入排序 2 直接选择排序 3 冒泡排序 输入序号 4 快速排序 5 堆 排序 6 时间效率比较 7 显示随机数 0 显示排序后的的数据和时间效率 显示各个排序法对同一组数据排序所用的时间和其中两种较快的方法 退出结束 3 程序实现

3.1 程序实现时应考虑的问题

void InsertSort(int a[],int p) void SelectSort(int a[],int p) void BubbleSort(int a[],int p) void heapsort(int a[],int n,int p) void Disp(int a[]) void quicksort(int a[],int n, int p) void creatheap(int a[],int i,int n) double TInsertSort(int a[],int p) double TBubbleSort(int a[],int p) double Tquicksort(int a[],int left, int right,int p) double TSelectSort(int a[],int p) void BubleSort(double a[]) 时间数组的冒泡排序 double Theapsort(int a[],int n,int p) 模块化能使节约资源，也方便了程序的调试和增加功能。 3.2 主要源代码及说明

#include #include #include #include #include #define N 30000

void Wrong() {

printf(\按键错误!\\n\getchar(); }

void Disp(int a[]) {

int i;

system(\

for(i=0;i

if((i-1)==9)

printf(\

printf(\ } }

void InsertSort(int a[],int p) //插入排序 {

int i,j,temp;

for(i=1;i

temp=a[i];

for(j=i;j>0&&a[j-1]>temp;j--) a[j]=a[j-1]; a[j]=temp; } }

void SelectSort(int a[],int p) //选择排序 {

int i,j,k;

for(i=0;i

k=i;

for(j=i+1;j if(k!=i) {

int temp; temp=a[k]; a[k]=a[i]; a[i]=temp; } } }

void BubbleSort(int a[],int p) /*冒泡排序算法*/ {

int i,j,temp;

for (i=0;i

for (j=N-1;j>i;j--) /*比较,找出本趟最小关键字的记录*/ if (a[j]

temp=a[j]; /*进行交换,将最小关键字记录前移*/ a[j]=a[j-1]; a[j-1]=temp; } } }

void creatheap(int a[],int i,int n) //{

int j; int t;

t=a[i];

j=2*(i+1)-1; while(j<=n) {

if((j a[i]=a[j]; i=j;

j=2*(i+1)-1; } else

j=n+1; }

a[i]=t; }

void heapsort(int a[],int n,int p) // {

int i; int t;

for(i=n/2-1;i>=0;i--) creatheap(a,i,n-1);

创建堆 堆排序

for(i=n-1;i>=1;i--) {

t=a[0]; a[0]=a[i]; a[i]=t;

creatheap(a,0,i-1);} }

void quicksort(int a[],int n,int p) {

int i,j,low,high,temp,top=-1;

struct node {

int low,high; }st[N]; top++;

st[top].low=0;st[top].high=n-1; while(top>-1)

{ low=st[top].low;high=st[top].high; top--;

i=low;j=high; if(low

{ temp=a[low]; while(i!=j)

{ while(itemp)j--; if(i

a[i]=temp;

top++;st[top].low=low;st[top].high=i-1; top++;st[top].low=i+1;st[top].high=high; } } }

double TInsertSort(int a[],int p)

{

int i; int b[N];

for(i=0;i

LARGE_INTEGER m_liPerfFreq={0};

QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart={0};

QueryPerformanceCounter(&m_liPerfStart); InsertSort(b,p);

LARGE_INTEGER liPerfNow={0};

QueryPerformanceCounter(&liPerfNow);

double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart; if(p!=6)

{Disp(b);getchar();}

printf(\用直接插入排序法用的时间为%f秒；\FILE *fp;

fp=fopen(\直接插入排序.txt\

for(i=0;i

fprintf(fp,\

fclose(fp); return(time); }

double TSelectSort(int a[],int p) {

int i; int b[N];

for(i=0;i

LARGE_INTEGER m_liPerfFreq={0};

QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart={0};

QueryPerformanceCounter(&m_liPerfStart); SelectSort(b,p); if(p!=6)

{Disp(b);getchar();}

LARGE_INTEGER liPerfNow={0};

QueryPerformanceCounter(&liPerfNow);

double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;

printf(\用直接选择排序法用的时间为%f秒；\

FILE *fp;

fp=fopen(\直接选择排序.txt\

for(i=0;i

fprintf(fp,\fclose(fp);return(time); }

double TBubbleSort(int a[],int p) {

int i; int b[N];

for(i=0;i

LARGE_INTEGER m_liPerfFreq={0};

QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart={0};

QueryPerformanceCounter(&m_liPerfStart); BubbleSort(b,p);

LARGE_INTEGER liPerfNow={0};

QueryPerformanceCounter(&liPerfNow);

double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart; if(p!=6)

{Disp(b);getchar();}

printf(\用冒泡排序法用的时间为%f秒；\

FILE *fp;

fp=fopen(\冒泡排序.txt\

for(i=0;i

fprintf(fp,\fclose(fp);return(time); }

double Theapsort(int a[],int n,int p) {

int i; int b[N];

for(i=0;i

LARGE_INTEGER m_liPerfFreq={0};

QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart={0};

QueryPerformanceCounter(&m_liPerfStart); heapsort(b,N,p);

LARGE_INTEGER liPerfNow={0};

QueryPerformanceCounter(&liPerfNow);

double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart; if(p!=6)

{Disp(b);getchar();}

printf(\用堆排序法用的时间为%f秒；\

FILE *fp;

fp=fopen(\堆排序.txt\

for(i=0;i

fprintf(fp,\fclose(fp);return(time); }

double Tquicksort(int a[],int n,int p) {

int i; int b[N];

for(i=0;i

LARGE_INTEGER m_liPerfFreq={0};

QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart={0};

QueryPerformanceCounter(&m_liPerfStart); quicksort(b,N,p);

LARGE_INTEGER liPerfNow={0};

QueryPerformanceCounter(&liPerfNow);

double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart; if(p!=6)

{Disp(b);getchar(); }

printf(\用快速排序法用的时间为%f秒；\

FILE *fp;fp=fopen(\快速排序.txt\ for(i=0;i

fprintf(fp,\

fclose(fp); return(time); }

本文来源：https://www.bwwdw.com/article/xgo6.html