数据结构实验完结撒花之内部排序比较
- 实验目的：
比较冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序；
- 实验要求：
待排序长度不小于100，数据可有随机函数产生，用五组不同输入数据做比较，比较的指标为关键字参加比较的次数和关键字移动的次数；
对结果做简单的分析，包括各组数据得出结果的解释；
设计程序用顺序存储。
- 实验内容
对各种内部排序算法的时间复杂度有一个比较直观的感受，包括关键字比较次数和关键字移动次数。
将排序算法进行合编在一起，可考虑用顺序执行各种排序算法来执行，最后输出所有结果。
代码 1
#include<stdio.h>
#include<string.h>
#include<time.h>
#include<stdlib.h>
#include<math.h>
#define MAXSIZE 100
typedef int KeyType; //定义关键字的整数类型
typedef struct{
KeyType key; //关键字项
}RedType;
typedef struct{
RedType r[MAXSIZE+1]; //0号单元闲置或用作哨兵单元
int length; //顺序表长度
int info; //记录关键字移动次数
int cmp; //关键字的比较次数
}Sqlist;
/**********************************************************************/
void BubbleSort(Sqlist *L) //冒泡排序
{
int i,j;
int N=L->length;
for(i=0;i<L->length;i++)
{
L->r[0]=L->r[1];
for(j=1;j<N-i;j++)
{
if(L->r[0].key>=L->r[j+1].key)
{
L->r[j]=L->r[j+1];
L->info++;
}
else
{
L->r[j]=L->r[0];
L->r[0]=L->r[j+1];
L->info+=2;
}
L->cmp++;
L->r[j+1]=L->r[0];
}
}
printf("以下数据的排列顺序为BubbleSort排序后的排列顺序：\n");
for(i=1;i<=MAXSIZE;i++)
{
printf("%d\t",L->r[i]);//输出排序后数组和相关数据
if(i%10==0)printf("\n");
}
printf("\n关键字移动次数为：%d\n",L->info);
printf("关键字比较次数为：%d\n",L->cmp);
}
/**********************************************************************/
void insertSort(Sqlist *L) //直接插入排序
{
int i,j;
for(i=2;i<=L->length;i++)
{
L->cmp++;
if((L->r[i].key < L->r[i-1].key))
{
L->r[0] = L->r[i]; //复制哨兵
L->r[i] = L->r[i-1];
L->info+=2;
for(j=i-2;(L->r[0].key < L->r[j].key);j--)
{
L->r[j+1] = L->r[j]; //记录后移
L->info++;
L->cmp++;
}
L->r[j+1] = L->r[0]; //插入到正确位置
L->info++;
}
}
printf("以下数据的排列顺序为insertSort排序后的排列顺序：\n");
for(i=1;i<=L->length;i++)
{
printf("%d\t",L->r[i]);//输出排序后数组和相关数据
if(i%10==0)printf("\n");
}
printf("\n关键字移动次数为：%d\n",L->info);
printf("关键字比较次数为：%d\n",L->cmp);
}
/**********************************************************************/
void SelectSort(Sqlist *L) // 简单选择排序
{
int i,j,k;
for (i=1; i<=L->length; ++i) // 选择第i小的记录，并交换到位
{
L->r[0]=L->r[i];j=i;
for(k=i+1;k<=L->length;k++) // 在L.r[i..L.length]中选key最小者
{
L->cmp++;
if(L->r[0].key>L->r[k].key)
{
L->r[0]=L->r[k];
j=k;
L->info++;
}
}
if (i!=j)
{ // L.r[i]←→L.r[j]; 与第i个记录交换
RedType temp;
temp=L->r[i];
L->r[i]=L->r[j];
L->r[j]=temp;
L->info+=3;
}
}
printf("以下数据的排列顺序为SelectSort排序后的排列顺序：\n");
for(i=1;i<=L->length;i++)
{
printf("%d\t",L->r[i]);//输出排序后数组和相关数据
if(i%10==0)printf("\n");
}
printf("\n关键字移动次数为：%d\n",L->info);
printf("关键字比较次数为：%d\n",L->cmp);
}
/**********************************************************************/
int serchSort(Sqlist *L,int low,int high) //查找排序单次排序
{
int pivotkey;
L->r[0] = L->r[low];
pivotkey=L->r[low].key; //枢轴纪录关键字
while(low<high)
{
while(low<high && L->r[high].key>=pivotkey)
{
high--;
L->cmp++;
}
L->r[low] = L->r[high]; //将比枢轴纪录小的纪录移到底端
L->info++;
while(low<high && L->r[low].key<=pivotkey)
{
low++;
L->cmp++;
}
L->r[high] = L->r[low]; //将比枢轴纪录大的纪录移到高端
L->info++;
}
L->r[low] = L->r[0];
L->info++;
return high;
}
void QSort(Sqlist *L, int low, int high) // 快速排序
{
int pivotloc;
if (low < high)
{ // 长度大于1
pivotloc = serchSort(L, low, high); // 将L.r[low..high]一分为二
QSort(L, low, pivotloc-1); // 对低子表递归排序，pivotloc是枢轴位置
QSort(L, pivotloc+1, high); // 对高子表递归排序
}
}
/**********************************************************************/
void ShellSort(Sqlist *L,int dlta[],int t) //希尔排序
{
int i,k,j;
for(k=1;k<=t;k++)
{
dlta[k]=(int)pow( 2, t-k+1 )-1;//double pow( double base, double exp );函数返回以参数base 为底的exp 次幂
for(i=dlta[k]+1;i<=L->length;i++)
{
L->cmp++;
if(L->r[i].key < L->r[i-dlta[k]].key)
{
L->r[0] = L->r[i];
L->info++;
for(j=i-dlta[k];j>0 && (L->r[0].key<L->r[j].key);j-=dlta[k])
{
L->cmp++;
L->r[j+dlta[k]] = L->r[j];
L->info++;
}
L->r[j+dlta[k]] = L->r[0];
L->info++;
}
}
}
printf("以下数据的排列顺序为ShellSort排序后的排列顺序：\n");
for(i=1;i<=L->length;i++)
{
printf("%d\t",L->r[i]);//输出排序后数组和相关数据
if(i%10==0)printf("\n");
}
printf("\n关键字移动次数为：%d\n",L->info);
printf("关键字比较次数为：%d\n",L->cmp);
}
/**********************************************************************/
void HeapAdjust(Sqlist *L, int s, int m) { // 已知L.r[s..m]中记录的关键字除L.r[s].key之外均满足堆的定义，本函数调整L.r[s]的关键字，使L.r[s..m]成为一个大顶堆（对其中记录的关键字而言）
int j;
RedType rc;
rc = L->r[s];
L->info++;
for (j=2*s; j<=m; j*=2) { // 沿key较大的孩子结点向下筛选
L->cmp++;
if (j<m && L->r[j].key<L->r[j+1].key)
{
++j; // j为key较大的记录的下标
L->cmp++;
}
if (rc.key >= L->r[j].key) break; // rc应插入在位置s上
L->r[s] = L->r[j];
L->info++;
s = j;
}
L->r[s] = rc; // 插入
L->info++;
}
void HeapSort(Sqlist *L) //堆排序
{
int i;
RedType rc;
for(i=L->length/2;i>0;i--) //把H->r[…]建成大顶堆
HeapAdjust ( L, i, L->length );
for(i=L->length;i>1;i--)
{
rc = L->r[i];
L->r[i] = L->r[1];
L->r[1] = rc;
L->info+=3;
HeapAdjust(L, 1, i-1); // 将H.r[1..i-1] 重新调整为大顶堆
}
printf("以下数据的排列顺序为HeapSort排序后的排列顺序：\n");
for(i=1;i<=L->length;i++)
{
printf("%d\t",L->r[i]);//输出排序后数组和相关数据
if(i%10==0)printf("\n");
}
printf("\n关键字移动次数为：%d\n",L->info);
printf("关键字比较次数为：%d\n",L->cmp);
}
/**********************************************************************/
int menu_select() //菜单目录
{
int nu;
char s;
printf("************************************************\n");
printf("*****菜单*****\n");
printf("1.BubbleSort\n"); //冒泡排序
printf("2.insertSort\n"); //直接插入排序
printf("3.SelectSort\n"); // 简单选择排序
printf("4.QSortt\n"); //快速查找排序
printf("5.ShellSort\n"); //希尔排序
printf("6.HeapSort\n"); //堆排序
printf("7.退出程序\n");
printf("************************************************\n");
printf("请输入数字：1-7 选择相应的排序方式或操作：\n");
do
{
s=getchar();
nu=(int)s-48;
}while(nu<0||nu>55);
return (nu);
}
/**********************************************************************/
int main()
{
Sqlist L,A,B,C,D,E;
int i,dlta[MAXSIZE];
int t=(int)(log(MAXSIZE+1)/log(2.0));
/*//*************************************************************
//以下语句是用来验证正序与逆序时关键字的移动次数和比较次数
int str[MAXSIZE]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,19,
20,22,23,24,25,26,27,28,29,31,33,35,37,38,39,41,42,43,
44,45,55,56,57,58,59,62,63,64,66,67,68,69,70,71,72,73,
74,76,77,79,80,81,82,83,84,85,87,88,89,90,91,92,93,94,
95,96,97,98,99,131,133,135,136,137,138,139,141,143,145,
146,147,148,188,189,190,192,194,195,196,197,198,199};
//for(i=1;i<=MAXSIZE;i++)
//L.r[i].key=str[i-1];
for(i=1;i<=MAXSIZE;i++)
L.r[i].key=str[MAXSIZE-i];
//*************************************************************/
L.length=0;
L.info=0;
L.cmp=0;
srand((unsigned)time(NULL));
printf("以下数据为需要排序的数据:\n");
for(i=1;i<=MAXSIZE;i++)
{
L.r[i].key=rand()%200;
L.length++;
printf("%d ",L.r[i].key);
}
A=B=C=D=E=L;
printf("\n");
for(;;)
switch(menu_select())
{
case 1: BubbleSort(&A);break;
case 2: insertSort(&B);break;
case 3: SelectSort(&C);break;
case 4: QSort(&L,1,L.length);
printf("以下数据的排列顺序为serchSort排序后的排列顺序：\n");
for(i=1;i<=L.length;i++)
printf("%d\t",L.r[i]);//输出排序后数组和相关数据
printf("\n关键字移动次数为：%d\n",L.info);
printf("关键字比较次数为：%d\n",L.cmp);
break;
case 5: ShellSort(&D,dlta,t);break;
case 6: HeapSort(&E);break;
case 7: exit(0);
}
}代码 2
#include <bits/stdc++.h>
#include <time.h>
using namespace std;
#define rg register long long
void Merge(int a[],int left,int right,int mid)//合并两组数字
{
int j,i=0;//循环，计数用
int one=left;
int two=mid+1;//one two分别指向第一 第二组数的第一个数字
int temp[right-left+1];//用来存排序数的临时数组，长度为两组数字个数总和
while(one<=mid&&two<=right)//当两组数字都未全部移入临时数组
{
if(a[one]>a[two])//如果one所指数大于two所指的数
temp[i++]=a[two++];//将two所指的数移入临时数组，two右移
else
temp[i++]=a[one++];
}
while(one<=mid)//当第一个数组中还有数未移入临时数组
temp[i++]=a[one++];
while(two<=right)
temp[i++]=a[two++];
i=0;
for(j=left;j<=right;j++)//将临时数组的数移入原数组
a[j]=temp[i++];
}
void MergeSort(int a[],int left,int right)//归并排序
{
if(left<right-1)//如果该组数字个数大于2
{
int mid=(left+right)/2;
MergeSort(a,left,mid);
MergeSort(a,mid+1,right);//分割
Merge(a,left,right,mid);//合并
}
else if(left==right-1)//如果该组数字个数等于2
{
if(a[left]>a[right])//如果前一个数字比后一个数字大，交换
{
int z=a[left];
a[left]=a[right];
a[right]=z;
}
}
//如果该组数字只剩一个，不用处理
}
void binInsertSort(int R[], int n)
{
int i, j, low, high, mid;
int tmp;
for (i = 1; i < n; i++)
{
if (R[i] < R[i - 1])
{
tmp = R[i];
low = 0;
high = i - 1;
while (low <= high)//折半查找
{
mid = (low + high) / 2;
if (tmp < R[mid])
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
for(j = i - 1; j >= high + 1; j--)//集中进行元素后移
{
R[j + 1] = R[j];
}
R[high + 1] = tmp;//插入tmp
}
}
}
void CardinalSort(int arry[], int countArry)
{
int maxx=*max_element(arry+1,arry+countArry+1);
int a[maxx+5];
memset(a,0,sizeof(a));
for(rg i=0;i<countArry;i++)
{
a[arry[i]]++;
}
rg cnt=0;
for(rg i=0;i<=maxx;i++)
{
while(a[i]>=1)
{
cout<<i<<" ";
cnt++;
if(cnt%31==0&&cnt)cout<<endl;
a[i]--;
}
}
}
int main()
{
int n;//序列长度/数的个数
int i;//循环用
srand((unsigned)time(NULL));
while(~scanf("%d",&n))
{
if(n==0)
break;//输入0退出
int a[n*10],b[n*10],c[n*10],d[n*10];
for(i=0;i<n;i++)a[i]=rand()%200,b[i]=a[i],c[i]=a[i],d[i]=a[i];
for(i=0;i<n;i++)//输出排序后序列
{
printf("%d ",a[i]);
if(i%30==0&&i)cout<<endl;
}
printf("\n\n");
clock_t a1,b1;
a1=clock();
binInsertSort(b,n);//折半插入排序
b1=clock();
//cout<<a1<<" "<<b1<<endl;
//printf("Time used = %.2f ms\n", (b1-a1)*1000/10000.0);
a1=clock();
MergeSort(a,0,n-1);//归并排序
b1=clock();
//cout<<a1<<" "<<b1<<endl;
//printf("Time used = %.2f ms\n", (b1-a1)*1000000/10000.0);
a1=clock();
sort(d,d+n);
b1=clock();
//cout<<a1<<" "<<b1<<endl;
//printf("Time used = %.2f ms\n", (b1-a1)*1000000/10000.0);
for(i=0;i<n;i++)//输出排序后序列
{
printf("%d ",a[i]);
if(i%30==0&&i)cout<<endl;
}
printf("\n\n");
for(i=0;i<n;i++)//输出排序后序列
{
printf("%d ",b[i]);
if(i%30==0&&i)cout<<endl;
}
printf("\n\n");
a1=clock();
CardinalSort(c, n);
b1=clock();
//cout<<a1<<" "<<b1<<endl;
//printf("Time used = %.2f ms\n", (b1-a1)*1000/10000.0);
}
return 0;
} 本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/12/20 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
