数据结构与算法（C语言版）---内排序算法比较
·
1、需求分析：
在教科书中,各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。
2、基本要求：
（1)对以下5种常用的内部排序算法进行比较起泡排序直接插入排序简单选择
排序、快速排序、希尔排序
(2)待排序表的表长不小于100;其中的数据要用伪随机数产生程序产生至少要用
5组不同的输入数据作比较;比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换计为3次移动)
(3)最后要对结果作出简单分析,包括对各组数据得出结果波动大小的解释
（1）数据对象
typedef struct SS
{
KeyType key; //关键字项
InfoType data; //其他数据项
} RecType; //排序的元素的类型（2）数据关系
typedef struct SSS
{
char name[30]; //排序名称
int com; //比较的次数
int mov; //移动的次数
}Analysis; //存储分析效率的4数据
//直接插入排序算法
void InsertSort(RecType R[], int n);
//折半插入排序法
void BinInsertSort(RecType R[], int n);
//希尔排序算法
void ShellSort(RecType R[], int n);
//冒泡排序算法
void BubbleSort(RecType R[], int n);
//
int partition(RecType R[], int s, int t); //一趟划分
//对R[s..t]的元素进行快速排序
void QuickSort(RecType R[], int s, int t);
//菜单
void menu();
//调用直接插入排序的实现函数，即菜单1
void FirstFun(RecType a[], int n);
//菜单2
void SecondFun(RecType a[], int n);
//菜单3
void ThirdFun(RecType a[], int n);
//菜单4
void FourthFun(RecType a[], int n);
//菜单5
void FifthFun(RecType a[], int n);
//菜单6
void SixthFun(RecType a[], int n);- 详细设计
//直接插入排序算法
void InsertSort(RecType R[], int n)
{
int i, j;
RecType tmp;
for (i = 1; i < n; i++) //for循环内一定比较了n-1次，if判断语句
{
if (R[i].key < R[i - 1].key) //一旦出现了逆序的关键字，就进行插入
{
tmp = R[i];
j = i - 1;
compare++;
do //往后移动一个位置，腾空间给tmp；
{
R[j + 1] = R[j];
move++; //移动加一
j--;
compare++; //比较次数加一
} while (j >= 0 && R[j].key > tmp.key);
R[j + 1] = tmp; //最后把tmp放在对应的位置
move+=2; //移动的temp
}
}
}
//折半插入排序法
void BinInsertSort(RecType R[], int n)
{
int i, j, low, high, mid;
RecType tmp;
for (i = 1; i < n; i++) //已经比较了n-1次
{
if (R[i].key < R[i - 1].key)
{
tmp = R[i];
low = 0;
high = i - 1;
compare++;
while (low <= high)
{
compare++; //while进入比较
mid = (low + high) / 2;
if (tmp.key < R[mid].key)
high = mid - 1;
else
low = mid + 1;
}
for (j = i - 1; j >= high + 1; j--)
{
R[j + 1] = R[j];
move++;//移动次数加一
}
R[high + 1] = tmp;
move += 2;//tmp交换
}
}
}
//希尔排序算法
void ShellSort(RecType R[], int n)
{
int i, j, d;
RecType tmp;
d = n / 2;
while (d > 0)
{
for (i = d; i < n; i++)
{
tmp = R[i];
j = i - d;
while (j >= 0 && tmp.key < R[j].key)
{
compare++;
move++;
R[j + d] = R[j];
j = j - d;
}
R[j + d] = tmp;
move += 2;//tmp进行两次操作
}
d = d / 2;
}
}
//冒泡排序算法
void BubbleSort(RecType R[], int n)
{
int i, j;
bool exchange;
RecType tmp;
for (i = 0; i < n - 1; i++)
{
exchange = false;
for (j = n - 1; j > i; j--)
if (R[j].key < R[j - 1].key)
{
compare ++;
move += 3;
tmp = R[j - 1];
R[j - 1] = R[j];
R[j] = tmp;
exchange = true;
}
if (!exchange)
return;
}
}
//快速排序算法
int partition(RecType R[], int s, int t) //一趟划分
{
int i = s, j = t;
RecType tmp = R[i]; //以R[i]为基准
while (i < j) //从两端交替向中间扫描,直至i=j为止
{
while (j > i && R[j].key >= tmp.key)
{
j--; //从右向左扫描,找一个小于tmp.key的R[j]
compare++;//进行比较
}
R[i] = R[j]; //找到这样的R[j],放入R[i]处
move++; //移动+1
while (i < j && R[i].key <= tmp.key)
{ i++; //从左向右扫描,找一个大于tmp.key的R[i]
compare++;//比较加一
}
R[j] = R[i]; //找到这样的R[i],放入R[j]处
move++; //移动加一
}
R[i] = tmp;
move+=2; //temp的交换
return i;
}
void QuickSort(RecType R[], int s, int t)
//对5种算法快速排序
{
int i;
if (s < t) //区间内至少存在两个元素的情况
{
i = partition(R, s, t);
QuickSort(R, s, i - 1); //对左区间递归排序
QuickSort(R, i + 1, t); //对右区间递归排序
}
}
void menu()
{
printf("***************************************************\n");
printf("\t\t1.直接插入排序法\n");
printf("\t\t2.折半插入排序法\n");
printf("\t\t3.希尔排序法\n");
printf("\t\t4.冒泡排序法\n");
printf("\t\t5.快速排序法\n");
printf("\t\t6.效率比较\n");
printf("\t\t7.退出\n");
printf("***************************************************\n");
}
//调用直接插入排序的实现函数，即菜单1
void FirstFun(RecType a[], int n)
{
int i;
for (i = 0; i < MAX; i++)
a[i].key = rand() % 100;
printf("伪随机数生成的10000个随机数：\n\n\n");
for (i = 0; i < MAX; i++)
printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n');
putchar(10);
InsertSort(a, MAX);
printf("\n\n\n利用直接插入排序后的数列如下：\n\n\n");
for (i = 0; i < MAX; i++)
printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n');
printf("\n\n直接插入排序法：\n一共比较了%d次，移动了%d次\n",compare,move);
Analy[0].com = compare;
Analy[0].mov = move;
strcpy(Analy[0].name, "直接插入排序");
}
//菜单2
void SecondFun(RecType a[], int n)
{
int i;
for (i = 0; i < MAX; i++)
a[i].key = rand() % 100;
printf("伪随机数生成的10000个随机数：\n\n\n");
for (i = 0; i < MAX; i++)
printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n');
putchar(10);
compare = 0;
move = 0;
BinInsertSort(a, MAX);
printf("\n\n\n利用折半插入排序后的数列如下：\n\n\n");
for (i = 0; i < MAX; i++)
printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n');
printf("\n\n折半插入排序：\n一共比较了%d次，移动了%d次\n",compare,move);
Analy[1].com = compare;
Analy[1].mov = move;
strcpy(Analy[1].name, "折半插入排序");
}
//菜单3
void ThirdFun(RecType a[], int n)
{
int i;
for (i = 0; i < MAX; i++)
a[i].key = rand() % 100;
printf("伪随机数生成的10000个随机数：\n\n\n");
for (i = 0; i < MAX; i++)
printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n');
putchar(10);
compare = 0;
move = 0;
ShellSort(a,MAX);
printf("\n\n\n利用希尔排序算法后的数列如下：\n\n\n");
for (i = 0; i < MAX; i++)
printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n');
printf("\n\n希尔排序算法：\n一共比较了%d次，移动了%d次\n",compare,move);
Analy[2].com = compare;
Analy[2].mov = move;
strcpy(Analy[2].name, "希尔排序算法");
}
//菜单4
void FourthFun(RecType a[], int n)
{
int i;
for (i = 0; i < MAX; i++)
a[i].key = rand() % 100;
printf("伪随机数生成的10000个随机数：\n\n\n");
for (i = 0; i < MAX; i++)
printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n');
putchar(10);
compare = 0;
move = 0;
BubbleSort(a,MAX);
printf("\n\n\n利用冒泡排序法后的数列如下：\n\n\n");
for (i = 0; i < MAX; i++)
printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n');
printf("\n\n冒泡排序算法：\n一共比较了%d次，移动了%d次\n",compare,move);
Analy[3].com = compare;
Analy[3].mov = move;
strcpy(Analy[3].name, "冒泡排序算法");
}
//菜单5
void FifthFun(RecType a[], int n)
{
int i;
for (i = 0; i < MAX; i++)
a[i].key = rand() % 100;
printf("伪随机数生成的10000个随机数：\n\n\n");
for (i = 0; i < MAX; i++)
printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n');
putchar(10);
compare = 0;
move = 0;
QuickSort(a,0,MAX);
printf("\n\n\n利用快速排序算法后的数列如下：\n\n\n");
for (i = 0; i < MAX; i++)
printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n');
printf("\n\n快速排序算法：\n一共比较了%d次，移动了%d次\n",compare,move);
Analy[4].com = compare;
Analy[4].mov = move;
strcpy(Analy[4].name, "快速排序算法");
}
//菜单6
void SixthFun(RecType a[], int n)
{
int i;
printf("各种排序算法的比较于移动次数的对比：\n\n");
//printf(" 名称\t\t\t\t比较次数\t\t\t移动次数\n");
printf(" 名称 比较次数 移动次数\n");
for(i = 0; i < 5; i++)
printf("%-17s%-18d%d\n",Analy[i].name,Analy[i].com,Analy[i].mov);
}- 用户手册
初始界面如上
输入1到7以外的数字没有效果要重新输入
运行完1到5后可运行6进行比较，可观察不同算法的比较次数和移动次数
- 测试结果
（1）
（2）
（3）
（4）
（5）
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
1
0- 0
已为社区贡献1条内容
所有评论(0)