当前位置：文档之家 › 内部排序算法比较实验报告(c语言版)

内部排序算法比较实验报告(c语言版)

  • 格式：doc
  • 大小：236.00 KB
  • 文档页数：19

题目：编制一个演示内部排序算法比较的程序班级：姓名：学号：完成日期：一、需求分析1．本演示程序对以下6种常用的内部排序算法进行实测比较：起泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序。

2．待排序表的元素的关键字为整数。

比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。

3．演示程序以以用户和计算机的对话方式执行，在计算机终端上显示提示信息，对随机数组进行排序，并输出比较指标值。

4．最后对结果作出简单分析。

二、概要设计1．可排序表的抽象数据类型定义：ADT OrderableList{数据对象：D={ai|ai∈IntegerSet,i=1,2,…,n,n≥0}数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}基本操作：InitList(n)操作结果：构造一个长度为n，元素值依次为1，2，…,n的有序表。

RandomizeList(d,isInverseOrder)操作结果：首先根据isInverseOrder为True或False,将表置为逆序或正序，然后将表进行d(0≤d≤8)级随机打乱。

d为0时表不打乱，d越大，打乱程度越高。

RecallList()操作结果：恢复最后一次用RandomizeList随机打乱得到的可排序表。

ListLength()操作结果：返回可排序表的长度。

ListEmpty()操作结果：若可排序表为空表，则返回Ture，否则返回False。

BubbleSort( &c, &s)操作结果：进行起泡排序，返回关键字比较次数c和移动次数s。

InsertSort( &c, &s)操作结果：进行插入排序，返回关键字比较次数c和移动次数s。

SelectSort ( &c, &s)操作结果：进行选择排序，返回关键字比较次数c和移动次数s。

QuickSort(&c, &s)操作结果：进行快速排序，返回关键字比较次数c和移动次数s。

ShellSort(long &c, long &s)操作结果：进行希尔排序，返回关键字比较次数c和移动次数s。

HeapSort (&c, &s)操作结果：进行堆排序，返回关键字比较次数c和移动次数s。

ListTraverse(visit())操作结果：依次对L中的每个元素调用函数visit()。

}ADT OrderableList2．本程序包含两个模块：1）主程序模块void main(){初始化；do{接受命令；处理命令；}while(“命令”！=“退出”)；}2）可排序表单元模块——实现可排序表的抽象数据类型；各模块之间的调用关系如下：主程序模块可排序表单元模块三、详细设计1．根据题目要求和可排序表的基本操作特点，可排序表采用整数顺序表存储结构。

//可排序表的元素类型#define MAXSIZE 10000 //用作示例的顺序表的最大长度typedef int BOOL;typedef struct{int key; //关键字项} RedType;//记录类型typedef struct LinkList{RedType r[MAXSIZE];int Length; //顺序表长度} LinkList;int RandArray[MAXSIZE];//内部操作void RandomNum(){int i;srand(20000);for (i = 0; i < MAXSIZE; i++)RandArray[i] = (int)rand(); //构建随机序列}void InitLinkList(LinkList *L){ //建立表int i;memset(L, 0, sizeof(LinkList));RandomNum();for (i = 0; i < MAXSIZE; i++)L->r[i].key = RandArray[i]; //赋值L->Length = i;}bool LT(int i, int j, int *CmpNum){ //比较i与j大小，返回0或1(*CmpNum)++;if (i < j)return TRUE;elsereturn FALSE;}void Display(LinkList *L){ //存储表到SortRes.txt文件中FILE *f;int i;if ((f = fopen("SortRes.txt", "w")) == NULL){printf("can't open file\n");exit(0);}for (i = 0; i < L->Length; i++)fprintf(f, "%d\n", L->r[i].key);fclose(f);}//部分操作的伪码算法//希尔排序void ShellInsert(LinkList *L, int dk, int *CmpNum, int *ChgNum){int i, j;RedType Temp;for (i = dk; i < L->Length; i++){if (LT(L->r[i].key, L->r[i - dk].key, CmpNum)){memcpy(&Temp, &L->r[i], sizeof(RedType));for (j = i - dk; j >= 0 && LT(Temp.key, L->r[j].key, CmpNum); j -= dk){ (*ChgNum)++;memcpy(&L->r[j + dk], &L->r[j], sizeof(RedType));}memcpy(&L->r[j + dk], &Temp, sizeof(RedType));}}}void ShellSort(LinkList *L, int dlta[], int t, int *CmpNum, int *ChgNum){int k;for (k = 0; k < t; k++)ShellInsert(L, dlta[k], CmpNum, ChgNum);}//快速排序int Partition(LinkList *L, int low, int high, int *CmpNum, int *ChgNum){ RedType Temp;int PivotKey;memcpy(&Temp, &L->r[low], sizeof(RedType));PivotKey = L->r[low].key;while (low < high){while (low < high && L->r[high].key >= PivotKey){high--;(*CmpNum)++;}(*ChgNum)++;memcpy(&L->r[low], &L->r[high], sizeof(RedType));while (low < high && L->r[low].key <= PivotKey){low++;(*CmpNum)++;}(*ChgNum)++;memcpy(&L->r[high], &L->r[low], sizeof(RedType));}memcpy(&L->r[low], &Temp, sizeof(RedType));return low;}void QSort(LinkList *L, int low, int high, int *CmpNum, int *ChgNum){int PivotLoc = 0;if (low < high){PivotLoc = Partition(L, low, high, CmpNum, ChgNum);QSort(L, low, PivotLoc - 1, CmpNum, ChgNum);QSort(L, PivotLoc + 1, high, CmpNum, ChgNum);}}void QuickSort(LinkList *L, int *CmpNum, int *ChgNum){QSort(L, 0, L->Length - 1, CmpNum, ChgNum);}//堆排序void HeapAdjust(LinkList *L, int s, int m, int *CmpNum, int *ChgNum){RedType Temp;int j = 0;s++;memcpy(&Temp, &L->r[s - 1], sizeof(RedType));for (j = 2 * s; j <= m; j *= 2){if (j < m && LT(L->r[j - 1].key, L->r[j].key, CmpNum)) ++j;if (!LT(Temp.key, L->r[j - 1].key, CmpNum))break;(*ChgNum)++;memcpy(&L->r[s - 1], &L->r[j - 1], sizeof(RedType)); s = j;}memcpy(&L->r[s - 1], &Temp, sizeof(RedType));}void HeapSort(LinkList *L, int *CmpNum, int *ChgNum){int i = 0;RedType Temp;for (i = L->Length / 2-1; i >= 0; i--)HeapAdjust(L, i, L->Length, CmpNum, ChgNum);for (i = L->Length; i > 1; i--){memcpy(&Temp, &L->r[0], sizeof(RedType));(*ChgNum)++;memcpy(&L->r[0], &L->r[i - 1], sizeof(RedType));memcpy(&L->r[i - 1], &Temp, sizeof(RedType));HeapAdjust(L, 0, i - 1, CmpNum, ChgNum);}}//冒泡排序void BubbleSort(LinkList *L, int *CmpNum, int *ChgNum){int i, j;RedType temp;for (i = 1; i <= MAXSIZE; i++){for (j = 1; j <= MAXSIZE - i; j++){if (!LT(L->r[j].key, L->r[j + 1].key, CmpNum)){(*ChgNum)++;memcpy(&temp, &L->r[j], sizeof(RedType));memcpy(&L->r[j], &L->r[j + 1], sizeof(RedType)); memcpy(&L->r[j + 1], &temp, sizeof(RedType));}}}}//选择排序int SelectMinKey(LinkList *L, int k, int *CmpNum){int Min = k;for (; k < L->Length; k++){if (!LT(L->r[Min].key, L->r[k].key, CmpNum))Min = k;}return Min;}void SelSort(LinkList *L, int *CmpNum, int *ChgNum){int i, j;RedType temp;for (i = 0; i < L->Length; i++){j = SelectMinKey(L, i, CmpNum);if (i != j){(*ChgNum)++;memcpy(&temp, &L->r[i], sizeof(RedType));memcpy(&L->r[i], &L->r[j], sizeof(RedType));memcpy(&L->r[j], &temp, sizeof(RedType));}}}3．函数的调用关系图反映了演示程序的层次结构：mainInitLinkList RandomNum LT Display四、调试分析1．对正序、逆序和若干不同程度随机打乱的可排序表，进行各种排序方法的比较测试，得到的测试数据具有较好的典型性和可比较性。

合集下载

内部排序实验报告

内部排序实验报告

数据结构实验报告内部排序班级：13 软工一班学号：13131113 姓名：吕蒙学号：13131116 姓名：钱剑滨学号：13131142 姓名：孔亚亚学号：13131144 姓名：邱佃雨13软工转本1 钱剑滨实验报告内部排序实验报告信息工程系 13软工转本1 日期 2016年06月07日一、实验内容编写程序实现各种内部排序（包括：冒泡排序、插入排序、选择排序、希尔排序、快速排序、堆排序、归并排序、基数排序），并运用这些排序对一组随机生成的数组进行排序。

二、时间复杂度1．冒泡排序（O(n^2））若文件的初始状态是正序的，一趟扫描即可完成排序。

所需的关键字比较次数和记录移动次数均达到最小值：，。

所以，冒泡排序最好的时间复杂度为。

若初始文件是反序的，需要进行趟排序。

每趟排序要进行次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。

在这种情况下，比较和移动次数均达到最大值：冒泡排序的最坏时间复杂度为。

综上，因此冒泡排序总的平均时间复杂度为。

2．插入排序（O(n^2））如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。

最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。

最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。

插入排序的赋值操作是比较操作的次数加上(n-1）次。

平均来说插入排序算法的时间复杂度为O(n^2）。

因而，插入排序不适合对于数据量比较大的排序应用。

但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。

3．选择排序（O(n^2））选择排序的交换操作介于0 和(n - 1）次之间。

选择排序的比较操作为n (n - 1）/ 2 次之间。

选择排序的赋值操作介于0 和3 (n - 1）次之间。

比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2。

实验九 内部排序

实验九 内部排序

实验九内部排序一、实验目的1、深入了解各种排序方法的基本思想、排序过程.2、熟练掌握各种排序方法的实现和特点，掌握各种排序方法的时间复杂度的分析方法。

3、掌握各种排序方法所适应的不同场合，能加以灵活运用。

二、实验内容和要求2、典型内部排序算法的比较。

（1）针对“12.11。

4参考源程序”，随机产生整数样本，进行8种排序,并比较各种排序算法的执行时间，如执行时间均为0，可考虑增大样本，如加大至5000。

（2）修改“12。

11.4参考源程序”，输出8种排序算法的每一趟结果.三、实验过程及结果(1）源代码:＃include "stdio。

h”＃include "conio。

h”#include ”stdlib。

h"＃include ”time.h”#define OK 1＃define ERROR 0＃define OVERFLOW -1＃define MAXSIZE 5000 //设待排序记录数不超过5000个typedef int Status；typedef int KeyType; //定义关键字为整型typedef int InfoType；//定义其它数据项类型为整型typedef struct {KeyType key；//关键字项InfoType otherinfo；//其他数据项}RedType;typedef struct { //定义顺序表的结构RedType *r; //存储空间基址，人r[0］闲置或用作哨兵或用作缓冲区int length; //顺序表长度｝SqList;Status InitSqList(SqList ＊L)； //构造一个空的顺序表LStatus CreateSqList（SqList ＊L）；//输入数据元素个数，随机产生整数样本Status CopySqList（SqList L_BAK，SqList ＊L）；//Status OutputSqList（SqList L）；//输出排序之后的数据int LT（KeyType e1，KeyType e2）; //判断数据元素e1是否小余e2void Swap(RedType *e1，RedType *e2); //数据元素e1和e2互换Status InsertSort（SqList ＊L); //直接排入排序Status BInsertSort（SqList ＊L）; //折半插入排序Status ShellInsert（SqList *L,int dk）； //一趟希尔排序Status ShellSort（SqList *L，int dlta［],int t); //希尔排序Status BubbleSort(SqList *L）；//冒泡排序int Partition(SqList *L,int low，int high); //一趟快速排序void QSort(SqList *L，int low,int high)；//对L中子序列L。

内部排序算法比较

内部排序算法比较

内部排序算法比较内部排序算法比较一、需求和规格说明1. 对常用的6种内部排序算法进行比较：冒泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序。

2. 待排序表的表长不小于500；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）3. 最后要对结果作出简单分析，包括对各组数据得到结果波动大小的解释。

2．设计1. 存储结构采用顺序表的存储结构typedef struct{int *elem;int length;}SqList;定义6个内容相同的顺序表：SqList L1,L2,L3,L4,L5,L6;2. main函数的过程：六个链表初始化InitList_Sq(SqList &L)for(i=0;i<5;i++)void CreateRand(SqList &L)产生伪随机数，并且将值赋在L.elem[MAXSIZE]里销毁链表结束Copy_List(L,L1,L2,L3,L4,L5,L6)六个顺序表中的内容完全一样SelectSort(L1);//简单选择排序InsertSort(L2);//直接插入排序Bubble_Sort(L3);//起泡排序Quick_Sort(L4);//快速排序Shell_Sort(L5);//希尔排序Heap_Sort(L6);//堆排序在各个排序函数中，会输出各种排序生成的关键词比较次数和移动次数1）.链表初识化InitList_Sq(SqList &L)。

为L.elem分配地址空间，且令L.length=02）.void CreateRand(SqList &L)产生伪随机数，并且将值赋在L.elem[MAXSIZE]里函数代码如下：void CreateRand(SqList &L){L.length=0;for(int i=1;i<maxsize+1;i++)< p="">{L.elem[i]=rand()%INFINE;L.length++;}}3）.Copy_List(L,L1,L2,L3,L4,L5,L6)；将顺序表L中的信息复制给L1,L2,L3,L4,L5,L6；4）.依次进行各种排序，在各个排序函数中，输出各自的关键字比较次数和移动次数。

内部排序实验报告

内部排序实验报告

//所在位置，此时在它之前（后）的记录均不大（小）于它。算法 10.6(b)
KeyType pivotkey; L.r[0]=L.r[low]; pivotkey=L.r[low].key;
//用子表的第一个记录作枢轴记录 //枢轴记录关键字
while(low< high) {
//从表的两端交替地向中间扫描
h.r[i+1]=d[i]; h.length=N; printf("\n 堆排序前:\n"); print_H(h); HeapSort(h); printf("堆排序后:\n"); print_H(h); goto s123;
case 4: for(i=0;i<N;i++) LL.r[i+1]=d[i]; LL.length=N; printf("归并排序前:\n"); print(LL); MergeSort(LL); printf("归并排序后:\n"); print(LL); goto s123;
RedType d[N]={{20,6},{52,1},{65,3},{88,9},{47,8},{22,4},{39,5},{74,7}}; int i; SqList LL; int dt[T]={5,3,1}; // 增量序列数组 int choice;
s123: cout<<"请选择要使用的排序算法：\n0..............退出\n"; cout<<"1..............插入排序\n2..............交换排序\n"; cout<<"3..............选择排序\n4..............归并排序\n"; cin>>choice; switch(choice) { case 0: break;