题目：编制一个演示内部排序算法比较的程序
班级：姓名：学号：完成日期：
一、需求分析
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 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){  //存储表到文件中
FILE *f;
int i;
if ((f = fopen("", "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));
sort命令排序}
}
}
}
//选择排序
int SelectMinKey(LinkList *L, int k, int *CmpNum){
int Min = k;
for (; k < L->Length; k++){

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。