/*
** 常见排序算法比较
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#define N 10
#define Demo 1
批量修改文件名称为1到100的方法：
步骤1，下载软件之后安装并打开，点击左上角蓝色“添加文件”按钮，将需要批量修改文件名称的文件添加到软件中。
步骤2，软件左侧是设置窗口，软件命名方式选择“自定义”可以为空；编号设置，起始设置成1，增量设置成1，位数也设置成1。软件右侧可以实时预览新文件名，已经变成从1到100了。
步骤3，预览新文件名没有问题后，点击“开始重命名”红色按钮，启动软件。当界面提示“重命名成功”的d窗出现，点击“确认”文件名称批量修改成功。
通过我的案例可以看出，这些文件成功的从1到100进行了命名。
1.快速排序#include"stdio.h"
#define N 100
int a[N]={0}//存放要排序的数
int Qsort(int m,int n)//对数组中m到n的元素进行快速排序
{
int p,q
int head,sign
if(m!=n)//选定的数列不止一个元素
{
head=a[n]//选择数列的末尾元素作为比较元素
p=m//p标记数列的首元素
q=n-1//标记末尾元素的前一个元素
sign=n//记录比较元素的位置，以其作为空位置
while(p<=q)//分别比较p、q所标记的元素与比较元素的大小，比其小的放在左边，比其大的放在右边
{
while(a[p]<head)//p所指元素比比较元素小，p右移
{
p++
if(p>q)
{
break
}
}
a[sign]=a[p]//将p所指元素移入空位置
sign=p//记录空余位置
p++
if(p>q)
{
break
}
while(a[q]>head)//q所指元素比比较元素大，q左移
{
q--
if(p>q)
{
break
}
}
a[sign]=a[q]
sign=q
q--
}
a[sign]=head//比较完成后，将比较元素移入空位置
if(sign-1>m)
{
Qsort(m,sign-1)//对m到sign-1的数列进行排序
}
if(sign+1<n)
{
Qsort(sign+1,n)//对sign+1到n的数列进行排序
}
}
return(1)
}
int Print(int m,int n)//对m到n的数组序列输出
{
int i
for(i=mi<=ni++)
{
printf("%d\n",a[i])
}
return(1)
}
int main()
{
int n,i
scanf("%d",&n)//输入将要排序的数的个数
for(i=0i<ni++)
{
scanf("%d",&a[i])//输入要排序的数
}
Qsort(0,n-1)
Print(0,n-1)
}
二、 详细设计：重要函数中的算法设计，实现流程，传递参数的说明；
三、调试分析与心得体会：
快速排序的思想时从数组序列中选定一个元素，将序列中其余元素与其进行比较，将比其小的放在左边，比其大的放在右边，然后以比较元素为中点，将序列分成两部分，再将它们分别进行快速排序，依次类推，直到序列中只有一个元素为止。
2.合并排序
#include"stdio.h"
#define N 10000
int a[N]//用a数组记录所给无序数列
int b[N]={0}//用b数组记录每次排序之后的a数组
int sign=0
void Merge(int m,int mid,int n)//将两个有序数列合并成为一个有序数列
{
int i,j,k
i=k=m
j=mid+1
while(i<=mid&&j<=n)//依次比较两个有序数列中的元素，从大到小将其放入b数组相应位置中
{
if(a[i]<a[j])
{
b[k]=a[i]
k++
i++
}
else
{
b[k]=a[j]
k++
j++
}
}
if(i<=mid)//将比较之后的剩余元素放入b数组相应位置
{
while(i<=mid)
{
b[k]=a[i]
k++
i++
}
}
else
{
while(j<=n)
{
b[k]=a[j]
k++
j++
}
}
for(i=mi<=ni++)//将合并后的数列重新放入a数组相应位置
{
a[i]=b[i]
}
}
int Msort(int m,int n)//对所给无序数列进行排序
{
int mid
if(n!=m)
{
mid=(n+m)/2//将数列一分为二直到其只有一个元素
Msort(m,mid)
Msort(mid+1,n)
Merge(m,mid,n)//将分割后的数列重新合并起来
}
return(1)
}
void Print(int num)//将序列依次输出
{
int i
for(i=0i<numi++)
{
printf("%d\n",a[i])
}
}
int main()
{
int sign
int i
int num
scanf("%d",&num)//输入将要排序的数的个数
for(i=0i<numi++)
{
scanf("%d",&a[i])//依次输入要排序的数
}
sign=Msort(0,num-1)
Print(num)//输出完成排序后的有序数列
}
二、 详细设计：重要函数中的算法设计，实现流程，传递参数的说明；
三、调试分析与心得体会：
合并排序是排序的一种常用方法，其主要思想为：将一个无序数列依次分割直到其每个序列只有一个元素为止，然后再将两个序列合并为一个有序数列，依此类推。
3.我的数据结构实验课题（关于排序）
//问题描述：排序器
//要求：实现以下六种排序算法，将给定的不同规模大小的数据文件（data01.txt，data02.txt，data03.txt，data04.txt）进行排序，
//并将排序结果分别存储到sorted01.txt，sorted02.txt，sorted03.txt和sorted04.txt文件中。
//1）、Shell排序；2）、Quick排序
//3）、锦标赛排序； 4）、堆排序
//5）、归并排序；6）、基数排序
//在实现排序算法1）~4）时，统计数据元素比较的次数和交换的次数，进而对这四种算法在特定数据条件下的效率进行分析和评判。
#include"stdio.h"
#include"math.h"
#include"stdlib.h"
#include"malloc.h"
#define Maxsize 10000000
#define N 20
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define LEN sizeof(SqList)
#define Maxr 10
#define MAXNUM 100000000
typedef struct node{
int key
int num
}
typedef struct {
struct node r[Maxsize+1]
long length
}SqList,*qSqList
typedef struct node2{
struct node r
struct node2 *next
}RecType
long shifttimes//统计移动次数
long comparetimes//统计比较次数
qSqList creat(char filename[])//读入文件并且将数据保存
{
FILE *fp
long i
qSqList L
L=(qSqList)malloc(LEN)
L->length=0
if((fp=fopen(filename,"r"))==NULL)//文件不存在时终止程序
{
printf("cannot open file\n")
exit(0)
}
for(i=1i<Maxsize+1i++)
{
fscanf(fp,"%ld (%d)",&(L->r[i].key),&(L->r[i].num))
if(L->r[i].key<0)
break
L->length++//记录读入的数据长度
}
fclose(fp)
return(L)
}
void Print2(qSqList L)//将序列输出到指定的文件中
{
long i
FILE *fp
char filename[N]
printf("\n\t请输入存储文件名：")
scanf("%s",filename)//输入将要储存的文件名
fp=fopen(filename,"w")
for(i=1i<=L->lengthi++)//将链表中数据逐一写入文件中
{
fprintf(fp,"%d (%d)\n",L->r[i].key,L->r[i].num)
}
fclose(fp)
}
void Print(qSqList L)//打印数据个数以及排序过程中的比较次数和移动次数
{
printf("\n\t数据个数:%ld",L->length)
printf("\n\t比较次数:%ld",comparetimes)
printf("\n\t移动次数:%ld",shifttimes)
}
struct node Min1(struct node a,struct node b)//比较两接点关键字的大小
{
struct node temp
if(a.key>b.key)
temp=b
else
temp=a
comparetimes++
return(temp)
}
qSqList shellinsert(qSqList L,int dk)//对顺序表以dk为增量作直接插入排序
{
int i,j
for(i=dk+1i<=L->lengthi++)
{
if(LT(L->r[i].key,L->r[i-dk].key))//将L->r[i]插入到有序增量子表
{
L->r[0]=L->r[i]//将L->r[i]暂时存储在L->r[0]
shifttimes++
for(j=i-dkj>0&<(L->r[0].key,L->r[j].key)j-=dk)//记录后移，查找插入位置
{
L->r[j+dk]=L->r[j]
comparetimes++
shifttimes++
}
if(j>0)
comparetimes++
L->r[j+dk]=L->r[0]//插入
shifttimes++
}
comparetimes++
}
// Print(L)
return(L)
}
qSqList shell(qSqList L)//希尔排序
{
int i,t=0
int k
for(t=0LQ(pow(2,t),(L->length+1))t++)
t=t-1
// printf("%d",t)
for(i=1i<=t++i)
{
k=(int)pow(2,t-i+1)-1//计算排序增量
L=shellinsert(L,k)
}
Print(L)
Print2(L)
return(L)
}
long Quicksort(qSqList L,long low,long high)//交换顺序表L中子表L->r[low..high]的记录，使枢轴记录到位，并返回其所在位置
{
int pivotkey
pivotkey=L->r[low].key//用序列的第一个记录作枢轴记录
while(low<high)//从表的两端交替地向中间扫描
{
while(low<high&&L->r[high].key>=pivotkey)//将比枢轴记录小的记录交换到低端
{
comparetimes++
high--
}
comparetimes++
L->r[0]=L->r[low]
shifttimes++
L->r[low]=L->r[high]
shifttimes++
L->r[high]=L->r[0]
shifttimes++
while(low<high&&L->r[low].key<=pivotkey)//将比枢轴记录大的记录交换到高端
{
comparetimes++
low++
}
comparetimes++
L->r[0]=L->r[low]
shifttimes++
L->r[low]=L->r[high]
shifttimes++
L->r[high]=L->r[0]
shifttimes++
}
return(low)//返回枢轴所在位置
}
qSqList Quick2(qSqList L,long low,long high)//对顺序表L中的子序列L.r[low..high]作快速排序
{
long pivot
if(low<high)//序列长度大于1
{
pivot=Quicksort(L,low,high)//将序列一分为二
Quick2(L,low,pivot-1)//对低位子表递归排序
Quick2(L,pivot+1,high)//对高位子表递归排序
}
return(L)
}
qSqList Quick(qSqList L)//对顺序表作快速排序
{
long low,high
low=1//将第一个数据所在位置定义为低位
high=L->length//将最后一个数据所在位置定义为高位
L=Quick2(L,low,high)//对顺序表作快速排序
Print(L)
Print2(L)
return(L)
}
void TourSort(SqList *L,long n)//锦标赛排序
{
qSqList Lp
long i=0,t=1,k=1,w
while(t<n)//t表示完全二叉树的结点个数
{
t=(long)pow(2,i)
i++
}
t=2*t
Lp=(qSqList)malloc((sizeof(SqList)))
Lp->length=t-1
for(i=t-1i>=t/2i--)
{
if(k>n)
Lp->r[i].key=MAXNUM
else
{
Lp->r[i]=L->r[k]
}
shifttimes++
k++
}
i=t-1
while(i!=1)
{
Lp->r[i/2]=Min1(Lp->r[i],Lp->r[i-1])
i-=2
comparetimes++
shifttimes++
}
for(i=1i<=ni++)
{
L->r[i]=Lp->r[1]
shifttimes++
w=1
while(w<t/2)
{
if(Lp->r[2*w].key==Lp->r[w].key)
w*=2
else
w=2*w+1
}
Lp->r[w].key=MAXNUM//将其赋为最大值
shifttimes++
if(w%2)
Lp->r[w/2]=Lp->r[w-1]
else
Lp->r[w/2]=Lp->r[w+1]
shifttimes++
while(w!=1)
{
if(w%2)
Lp->r[w/2]=Min1(Lp->r[w],Lp->r[w-1])
else
Lp->r[w/2]=Min1(Lp->r[w],Lp->r[w+1])
comparetimes++
shifttimes++
w/=2
}
}
Print(L)
Print2(L)
}
void Heapadjust(qSqList L,long s,long m)//调整L->[s]的关键字，使L->r[s..m]成为一个大顶堆
{
long j
struct node rc
rc=L->r[s]
for(j=2*sj<=mj*=2)//沿key较大的接点向下筛选
{
if(j<m&<(L->r[j].key,L->r[j+1].key))//j为key较大的记录的下标
{
j++
comparetimes++
}
if(!LT(rc.key,L->r[j].key))
{
comparetimes++
break
}
L->r[s]=L->r[j]//rc插入位置s
shifttimes++
s=j
}
L->r[s]=rc//插入
shifttimes++
}
qSqList Heap(qSqList L)//堆排序
{
long i
for(i=L->length/2i>0--i)//把L建成大顶堆
Heapadjust(L,i,L->length)
for(i=L->lengthi>1--i)//将堆顶记录和当前未经排序子序列中最后一个记录交换
{
L->r[0]=L->r[1]
L->r[1]=L->r[i]
L->r[i]=L->r[0]
shifttimes=shifttimes+3
Heapadjust(L,1,i-1)//将L重新调整为大顶堆
}
Print(L)
Print2(L)
return(L)
}
void Merge(qSqList L,int low,int m,int high)//将两个有序表R[low..m]he R[m+1..high]归并为一个有序表R[low,high]
{
int i=low,j=m+1,k=0//k是temp的下标，i,j分别为第1，2段的下标
struct node *temp
temp=(struct node*)malloc((high-low+1)*sizeof(struct node))//用于临时保存有序序列
while(i<=m&&j<=high)//在第1段和第2段均未扫描完时循环
{
if(LT(L->r[j].key,L->r[i].key))//将第1段中的记录放入temp中
{
temp[k]=L->r[j]
j++
k++
}
else//将第2段中的记录放入temp中
{
temp[k]=L->r[i]
k++
i++
}
}
while(i<=m)//将第1段余下的部分复制到temp
{
temp[k]=L->r[i]
k++
i++
}
while(j<=high)//将第2段余下的部分复制到temp
{
temp[k]=L->r[j]
k++
j++
}
for(k=0,i=lowi<=highi++,k++)//将temp复制回L中
{
L->r[i]=temp[k]
}
}
void MSort(qSqList L,int low,int high)//二路归并排序
{
int m
if (low<high)
{
m=(low+high)/2
MSort(L,low,m)
MSort(L,m+1,high)
Merge(L,low,m,high)
}
}
void Merging(qSqList L)//归并排序
{
MSort(L,1,L->length)
Print2(L)
}
void Radixsort(qSqList L)//基数排序
{
int g,i,j,k,d=2
struct node2 *p,*s,*t,*head[10],*tail[10]//定义各链队的首尾指针
for(i=1i<=L->lengthi++) //建立链表
{
s = (struct node2*)malloc(sizeof(struct node2))
s->r.key = L->r[i].key
s->r.num= L->r[i].num
if(i==1)
{
t = s
p = s
g++}
else
{
t->next = s
t = s
g++
}
t->next = NULL
}
d=1
for(i=1i<6i++)
{
for(j=0j<10j++)
{head[j] = tail[j] = NULL} //初始化各链队首、尾指针
while(p!=NULL)//对于原链表中的每个结点循环
{
k = p->r.key/d
k = k%10
if(head[k]==NULL)//进行分配
{
head[k]=p
tail[k]=p
}
else
{
tail[k]->next=p
tail[k]=p
}
p = p->next//取下一个待排序的元素
}
p=NULL
for(j=0j<10j++)//对每一个链队循环
{
if(head[j]!=NULL)//进行搜集
{
if(p == NULL)
{
p = head[j]
t = tail[j]
}
else
{
t->next=head[j]
t = tail[j]
}
}
}
t->next=NULL//最后一个结点的next置为空
d=d*10
}
i=1
while(p!=NULL)
{
L->r[i] = p->r
i++
p=p->next}
Print2(L)
}
char chmenu()//对排序方法进行选择
{
char ch
printf("\n\t请选择排序方法:"
"\n\t*************"
"\n\t1.Shell排序"
"\n\t2.Quick排序"
"\n\t3.锦标赛排序"
"\n\t4.堆排序"
"\n\t5.归并排序"
"\n\t6.基排序"
"\n\t7.结束"
"\n\t*************")
do{
printf("\n\tplease choose (1-7):")
getchar()
ch=getchar()
}while(!(ch>'0'&&ch<'8'))
return(ch)
}
void main()
{
int a=1
FILE *fp
char ch,filename[N]
qSqList L
while(a)
{
printf("\n\t请输入读入文件名:")//输入要读入的文件名
scanf("%s",filename)
if((fp=fopen(filename,"r"))==NULL)
{
printf("cannot open the file\n")
exit(0)
}
L=creat(filename)
while(1)
{
if((ch=chmenu())=='7')
break
switch(ch)
{
case'1':{shifttimes=comparetimes=0shell(L)}break
case'2':{shifttimes=comparetimes=0Quick(L)}break
case'3':{shifttimes=comparetimes=0TourSort(L,L->length)}break
case'4':{shifttimes=comparetimes=0Heap(L)}break
case'5':{shifttimes=comparetimes=0Merging(L)}break
case'6':{shifttimes=comparetimes=0Radixsort(L)}break
}
}
printf("\n\t***************"
"\n\t1.继续读入文件"
"\n\t0.结束"
"\n\t***************")
do{
printf("\n\tplease choose (0-1):")
getchar()
scanf("%d",&a)
}while(!(a==1||a==0))
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）