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

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

1 问题要求及任务描述

1.1 题目要求

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

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

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

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

1.2 主要任务

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

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

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

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

2.1 关键问题

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

核心算法: 直接插入、直接选择、冒泡、快速排序、堆排序的算法 输入数据: 初始化数组：rand()%50000+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<n)趟简单选择排序是，从无序序列a[i..n]的n-i+1记录中选出关键字最小的记录，和第i个记录交换，使有序序列逐步扩大，最后整个文件有序。共进行n-1趟选择。最坏时间复杂度是0(n)，平均时间复杂度是0(n)，空间复杂度是O(1)，是不稳定排序。

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

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

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

2

2

2

2

2.3 主要算法和处理流程图

3 程序实现

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

模块化能使节约资源，也方便了程序的调试和增加功能。

3.2 主要源代码及说明

#include <stdio.h> #include <conio.h> #include <stdlib.h> #include <windows.h> #include <time.h> #define N 30000

void Wrong() {

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

void Disp(int a[]) {

int i;

system("cls");

for(i=0;i<N;i++) {

if((i-1)%10==9)

printf("\n");

printf("%-7d",a[i]); } }

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

int i,j,temp;

for(i=1;i<N;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<N-1;i++) {

k=i;

for(j=i+1;j<N;j++) if(a[j]<a[k]) k=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<N-1;i++) {

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

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<n)&&(a[j]<a[j+1])) j++; if(t<a[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<high)

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

{ while(i<j&& …… 此处隐藏：7645字，全部文档内容请下载后查看。喜欢就下载吧 ……