内部排序算法比较实验报告（c语言版）
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
目:编制一个演示内部排序算法比较的程序
班级: 姓名: 学号: 完成日期:
一、需求
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
1(本演示程序对以下6种常用的内部排序算法进行实测比较:起泡排序，直接插入排序，简单选择排序，
快速排序，希尔排序，堆排序。
2(待排序表的元素的关键字为整数。比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字
交换记为3次移动)。
3(演示程序以以用户和计算机的对话方式执行，在计算机终端上显示提示信息，对随机数组进行排序，并
输出比较指标值。
4(最后对结果作出简单分析。
二、概要
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
1(可排序表的抽象数据类型定义:
ADT OrderableList{
数据对象:D={ai|ai?IntegerSet,i=1,2,„,n,n?0}
数据关系:R1={
|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 OrderableList
2(本程序包含两个模块:
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;
else
return 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(函数的调用关系图反映了演示程序的层次结构:
main
srand
BubbleSort InsertSort SelectSort QuickSort ShellSort HeapSort
InitLinkList RandomNum LT Display 四、调试分析
1(对正序、逆序和若干不同程度随机打乱的可排序表，进行各种排序
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
的比较测试，得到的测试数据具有较好的典型性和可比较性。通过设计和实现指定程序的随机乱序算法，对伪随机数序列的产生有了具体的认识和实践。
2(将排序算法中的关键字比较和交换分别由Less和Swap两个内部操作实现，较好的解决了排序算法的关键字比较次数和移动次数的统计问题。而赋值是直接统计的。
3(本实习作业采用循序渐进的策略，首先设计和实现可排序表的建立和随机操作，然后用插入排序验证各种内部辅助操作的正确性，进而逐个加入其他排序算法，最后完成对测试结果的显示。调试能力有了提高。 五、用户手册
1(本程序的运行环境为DOS操作系统，执行文件为:内部排序算法比较.exe。
2(进入程序后即显示文本方式的用户界面:
3(输入1回车，即得直接插入排序的排序结果及其关键字比较次数和移动次数及时间 输入2回车，即得希尔排序的排序结果及其关键字比较次数和移动次数及时间 输入3回车，即得快速排序的排序结果及其关键字比较次数和移动次数及时间 输入4回车，即得堆排序的排序结果及其关键字比较次数和移动次数及时间 输入5回车，即得冒泡排序的排序结果及其关键字比较次数和移动次数及时间 输入6回车，即得选择排序的排序结果及其关键字比较次数和移动次数及时间 输入7回车，即得以上所有排序的排序结果及其关键字比较次数和移动次数及时间 输入8回车，即退出该程序
六、测试结果
对结果的截屏如下:
对各种表长和测试组数进行了测试，程序运行正常。分析实测得到的数值，6种排序算法(快速排序采用“比中法”)的特点小结如下:
测试 插入排序 希尔排序 快速排序 堆排序 冒泡排序 选择排序
最多
第三多 稍多 越乱(逆)越少 少 第二多 比较次数 越乱(逆)越乱否差异很多 乱否差异小 乱否差异小 与乱否无关 多 小 越乱(逆)越
多
第二多 第二少 稍多 最多 约为快速排最少 移动次数 越乱(逆)越乱否差异较乱否差异很越乱(逆)越序的两倍 正和逆序少 多 小 小 多
七、附录
源程序文件名清单:
052376_李明_内部排序算法比较.cpp //主程序
#include
#include
#include
#include
#include
#include
#define MAXSIZE 5000
#define TRUE 1
#define FALSE 0
typedef int BOOL;
typedef struct{
int key;
} RedType;
typedef struct LinkList{
RedType r[MAXSIZE+1];
int Length;
} LinkList;
int RandArray[MAXSIZE+1];
void RandomNum(){
int i;
srand(2000);
for (i = 1; i <= MAXSIZE; i++)
RandArray[i] = (int)rand(); }
void InitLinkList(LinkList *L){
int i;
memset(L, 0, sizeof(LinkList));
RandomNum();
for (i = 1; i <= MAXSIZE; i++)
L->r[i].key = RandArray[i];
L->Length = i;
}
bool LT(int i, int j, int *CmpNum){
(*CmpNum)++;
if (i < j)
return TRUE;
else
return FALSE;
}
void Display(LinkList *L){
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));
}
}
}
void SelectSort(){
printf("1. 插入排序\n");
printf("2. 希尔排序\n");
printf("3. 快速排序\n");
printf("4. 堆排序\n");
printf("5. 冒泡排序\n");
printf("6. 选择排序\n");
printf("7. 以上所有排序方式\n");
printf("8. 退出程序\n\n");
printf("Please Select the Operate:"); }
void AllAbove(LinkList *L, int *CmpNum, int *ChgNum){
int TempTime, i,j;
int SpendTime;
int dlta[3] = {
7, 3, 1
};
int Indata[1] = {
1
};
for (i = 1; i <= MAXSIZE; i++)
L->r[i].key = RandArray[i]; //随机数列复位
printf("\n插入排序:\n");
TempTime = (int)GetTickCount();
ShellSort(L, Indata, 1, &CmpNum[0], &ChgNum[0]);
SpendTime = (int)GetTickCount() - TempTime;
printf("\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n", CmpNum[0],
ChgNum[0],SpendTime);
for (i = 1; i <= MAXSIZE; i++)
L->r[i].key = RandArray[i]; //随机数列复位
printf("\n希尔排序:\n");
TempTime = (int)GetTickCount();
ShellSort(L, dlta, 3, &CmpNum[1], &ChgNum[1]);
SpendTime = (int)GetTickCount() - TempTime;
printf("\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n", CmpNum[1],
ChgNum[1],SpendTime);
for (i = 1; i <= MAXSIZE; i++)
L->r[i].key = RandArray[i]; //随机数列复位
printf("\n快速排序:\n");
TempTime = (int)GetTickCount();
QuickSort(L, &CmpNum[2], &ChgNum[2]);
SpendTime = (int)GetTickCount() - TempTime;
printf("\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n", CmpNum[2],
ChgNum[2],SpendTime);
for (i = 1; i <= MAXSIZE; i++)
L->r[i].key = RandArray[i]; //随机数列复位
printf("\n堆排序:\n");
TempTime = (int)GetTickCount();
HeapSort(L, &CmpNum[3], &ChgNum[3]);
SpendTime = (int)GetTickCount() - TempTime;
printf("\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n", CmpNum[3],
ChgNum[3],SpendTime);
for (i = 1; i <= MAXSIZE; i++)
L->r[i].key = RandArray[i]; //随机数列复位
printf("\n冒泡排序:\n");
TempTime = (int)GetTickCount();
BubbleSort(L, &CmpNum[4], &ChgNum[4]);
SpendTime = (int)GetTickCount() - TempTime;
printf("\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n", CmpNum[4],
ChgNum[4],SpendTime);
for (i = 1; i <= MAXSIZE; i++)
L->r[i].key = RandArray[i]; //随机数列复位
printf("\n选择排序:\n");
TempTime = (int)GetTickCount();
SelSort(L, &CmpNum[5], &ChgNum[5]);
SpendTime = (int)GetTickCount() - TempTime;
printf("\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n", CmpNum[5],
ChgNum[5],SpendTime);
}
void main(){
int i,j;
int select = 0;
int dlta[3] = {7, 3, 1};
int Indata[1] = {1};
int CmpNum[8], ChgNum[8];
int SpendTime = 0;
int TempTime;
LinkList L;
InitLinkList(&L);
memset(CmpNum, 0, sizeof(CmpNum));
memset(ChgNum, 0, sizeof(ChgNum));
do{
SelectSort();
for (i = 0; i < MAXSIZE; i++)
L.r[i].key = RandArray[i]; //随机数列复位
scanf("%d", &select);
switch (select){
case 1:
printf("\n插入排序:\n");
TempTime = (int)GetTickCount();
ShellSort(&L, Indata, 1, &CmpNum[select], &ChgNum[select]);
SpendTime = (int)GetTickCount() - TempTime;
for(i=1;i<=MAXSIZE;i++){
printf("%5d ",L.r[i].key);
if(++j%10==0)printf("\n");
}
printf("\n\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n",
CmpNum[select],ChgNum[select], SpendTime);
break;
case 2:
printf("\n希尔排序:\n");
TempTime = (int)GetTickCount();
ShellSort(&L, dlta, 3, &CmpNum[select], &ChgNum[select]);
SpendTime = (int)GetTickCount() - TempTime;
for(i=1;i<=MAXSIZE;i++){
printf("%5d ",L.r[i].key);
if(++j%10==0)printf("\n");
}
printf("\n\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n",
CmpNum[select],ChgNum[select], SpendTime);
break;
case 3:
printf("\n快速排序:\n");
TempTime = (int)GetTickCount();
QuickSort(&L, &CmpNum[select], &ChgNum[select]);
SpendTime = (int)GetTickCount() - TempTime;
for(i=1;i<=MAXSIZE;i++){
printf("%5d ",L.r[i].key);
if(++j%10==0)printf("\n");
}
printf("\n\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n",
CmpNum[select],ChgNum[select], SpendTime);
break;
case 4:
printf("\n堆排序:\n");
TempTime = (int)GetTickCount();
HeapSort(&L, &CmpNum[select], &ChgNum[select]);
SpendTime = (int)GetTickCount() - TempTime;
for(i=1;i<=MAXSIZE;i++){
printf("%5d ",L.r[i].key);
if(++j%10==0)printf("\n");
}
printf("\n\nCompareNumber=%d\tChageNumber=%d\t\tTimeSpent=%dms\n",CmpNum[select],
ChgNum[select], SpendTime);
break;
case 5:
printf("\n冒泡排序:\n");
TempTime = (int)GetTickCount();
BubbleSort(&L, &CmpNum[select], &ChgNum[select]);
SpendTime = (int)GetTickCount() - TempTime;
for(i=1;i<=MAXSIZE;i++){
printf("%5d ",L.r[i].key);
if(++j%10==0)printf("\n");
}
printf("\n\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n",
CmpNum[select],ChgNum[select], SpendTime);
break;
case 6:
printf("\n选择排序:\n");
TempTime = (int)GetTickCount();
SelSort(&L, &CmpNum[select], &ChgNum[select]);
SpendTime = (int)GetTickCount() - TempTime;
for(i=1;i<=MAXSIZE;i++){
printf("%5d ",L.r[i].key);
if(++j%10==0)printf("\n");
}
printf("\n\nCompareNumber=%d\tChageNumber=%d\tTimeSpent=%dms\n",
CmpNum[select],ChgNum[select], SpendTime);
break;
case 7:
AllAbove(&L, CmpNum, ChgNum);
break;
}
}
while (select != 8 );
Display(&L);
}
浙公网安备 33021202002483