各类排序算法.docx
《各类排序算法.docx》由会员分享，可在线阅读，更多相关《各类排序算法.docx（16页珍藏版）》请在冰点文库上搜索。
各类排序算法
//******************************************************
//各类排序算法
//******************************************************
#include
#include
#include
typedefstruct
{
intkey;//主关键字
}NODE;
//********************************************
//随机数组,作为全局数据
//********************************************
NODEDATA[100];
//********************************************
//创建磁盘文件f:
\resource.dat
//保存100个100以内的随机数（无重复）
//********************************************
voidcreatfile（）
{
FILE*fp;
inti,j,key,flag;
intdata[100]={0};
unsignedseed;
if（（fp=fopen（"f:
\\resource.dat","wb+"））==NULL）
{
printf（"打开文件失败!
\n"）;
exit（0）;
}
seed=time（NULL）;
srand（seed）;//设置随机种子
for（i=0;i<=99;）
{
key=rand（）%1000;
flag=1;
for（j=0;j<=i-1;j++）
if（key==data[j]）
{
flag=0;
break;
}
if（flag）
data[i++]=key;
}
for（i=0;i<=99;i++）
putw（data[i],fp）;//写一个整数到磁盘文件
fclose（fp）;
}
//********************************************
//导入磁盘文件f:
\resource.dat中的信息
//将文件中的数据，存入全局数组中
//********************************************
voidload（）
{
FILE*fp;
inti;
if（（fp=fopen（"f:
\\resource.dat","rb+"））==NULL）
{
printf（"打开文件失败!
\n"）;
exit（0）;
}
for（i=0;i<=99;i++）
DATA[i].key=getw（fp）;
fclose（fp）;
}
//********************************************
//输出随机数组
//********************************************
voidprn（NODEdata[]）
{
printf（"\n"）;
for（inti=0;i<=99;i++）
{
printf（"%3d",data[i].key）;
if（（i+1）%5==0）
printf（"\n"）;
}
}
//********************************************
//快速排序的区域划分算法
//在区间了low和high之间进行一次划分
//********************************************
intpartition（NODEdata[],intlow,inthigh）
{
inti=low;
intj=high;
intt=data[i].key;//t为划分的基准值
//寻找基准点的位置
do{
while（t<=data[j].key&&ij--;//
if（i{
data[i]=data[j];//将基准点与该记录交换,将小的记录放到左半区中
i++;
}
while（data[i].key<=t&&ii++;
if（i{
data[j]=data[i];//将基准点与该记录交换,将大的记录放到右半区中
j--;
}
}while（idata[i].key=t;
returni;
}
//********************************************
//快速排序算法
//********************************************
voidquicksort（NODEdata[],intlow,inthigh）
{
intposition;
if（low{
position=partition（data,low,high）;//将该区间分成两半,position为分界点
quicksort（data,low,position-1）;//对左半区进行快速排序
quicksort（data,position+1,high）;//对右半区快速排序
}
}
//********************************************
//选择排序
//********************************************
voidselesort（NODEDATA[]）
{
inti,j;
NODEt;
for（i=0;i<99;i++）//n个数,排序n-1轮
{
for（j=i+1;j<=99;j++）//选择本轮的最小值
{
if（DATA[i].key>DATA[j].key）//发现更小的数,则交换
{
t=DATA[i];
DATA[i]=DATA[j];
DATA[j]=t;
}
}//本循环结束,DATA[i]中是本轮找到的最小值
}
}
//********************************************
//直接选择排序
//********************************************
voiddselesort（NODEDATA[]）
{
inti,j,k;
NODEt;
for（i=0;i<99;i++）
{
k=i;
for（j=i+1;j<=99;j++）//寻找本轮中的最小值
{
if（DATA[k].key>DATA[j].key）//记下最小值的位置
k=j;
}
//把DATA[i]和最小值DATA[k]交换
if（k!
=i）
{t=DATA[i];DATA[i]=DATA[k];DATA[k]=t;}
}
}
//********************************************
//冒泡排序
//********************************************
voidpasort（NODEDATA[]）
{
inti,j;
NODEt;
for（i=0;i<99;i++）
for（j=0;j<99-i;j++）
if（DATA[j].key>DATA[j+1].key）
{
t=DATA[j],DATA[j]=DATA[j+1],DATA[j+1]=t;
}
}
//********************************************
//改进的冒泡排序
//********************************************
voiddpasort（NODEDATA[]）
{
inti=0,j;
NODEt;
intflag;
do
{
flag=1;
for（j=0;j<99-i;j++）
if（DATA[j].key>DATA[j+1].key）
{
t=DATA[j],DATA[j]=DATA[j+1],DATA[j+1]=t;
flag=0;
}
i++;//比较的轮次增1
}while（!
flag）;
}
//********************************************
//筛选法,将:
以结点i为根的二叉树,调整成一个大根堆
//调整范围:
结点i---结点j
//********************************************
voidsift（NODEdata[],inti,intj）
{
NODEtemp;
intp=2*i;//p指向i的左孩子
intt;
while（p<=j）//如果i的左孩子存在,则调整,否则,i是叶子,不调整
{
t=p;//t指向i的左孩子
if（pif（data[p].keyt=p+1;//p指向键值较大的孩子
if（data[i].key{
temp=data[i];
data[i]=data[t];
data[t]=temp;
i=t;//互换后势必影响以t为根的堆的性质，所以对以t为根的堆再进行调整
p=2*i;
}//将根与较大的孩子互换
elsebreak;//如果根i的键值比两个孩子都大,则是大根堆,无需调整
}
}
//********************************************
//堆排序，建立大根堆
//********************************************
voidcreatheap（NODEdata[],intn）
{
intk;
for（k=n/2;k>=1;k--）
sift（data,k,n）;//对非叶子结点k,利用调整算法
//使以该节点k为根的树变成大根堆
//调整区间:
（k--n）
}
//********************************************
//堆排序算法
//数据集合1--n之间的数进行堆排序
//数据元素data[0]留空
//可作为辅助变量,实现两个元素的互换
//********************************************
voidheapsort（NODEdata[],intn）
{
inti;
creatheap（data,n）;//将data中的n个元素创建成大根堆
for（i=n;i>1;i--）//堆排序,data[1]中始终为无序区的最大值
{
data[0]=data[i];//将根（最大值）换到无序区的末尾
data[i]=data[1];//data[0]作为辅助变量
data[1]=data[0];
sift（data,1,i-1）;//调整无序区中的数据,使之保持大根堆性质
}
}
//********************************************
//归并
//********************************************
voidmerge（NODEdata[],intlow,intm,inthigh）
{
inti=low,j=m+1,p=1;
NODEt[101];//辅助存储空间,可采用动态申请的方式
//t=（NODE*）malloc（sizeof（NODE）*（high-low+1））//动态申请辅助存储空间
while（i<=m&&j<=high）//合并
t[p++]=data[i].keydata[i++]:
data[j++];
while（i<=m）//若前一组还有多余数据,全部复制到辅助空间
t[p++]=data[i++];
while（j<=high）//若后一组还有多余数据,全部复制到辅助空间
t[p++]=data[j++];
for（p=1,i=low;i<=high;i++,p++）
data[i]=t[p];//从辅助空间写回到原数据空间
}
//********************************************
//一个轮次的归并算法
//********************************************
voidmergepass（NODEdata[],intn,intlength）
{
inti;
for（i=1;i+2*length-1<=n;i+=2*length）//在data的某个区间上进行归并排序
//区间下界:
i,上界:
i+2*length-1
//上下界分界点:
i+length-1
merge（data,i,i+length-1,i+2*length-1）;
if（i+length-1merge（data,i,i+length-1,n）;
}
//********************************************
//自底向上的二路归并排序算法
//********************************************
voidmergesort（NODEdata[],intn）
{
intlength;
for（length=1;length//n个数,归并log2n次,分组元素个数为1,2,4,8,16....2^length
mergepass（data,n,length）;
}
//********************************************
//直接插入排序（不带监视哨）
//********************************************
voidinser（）
{
inti,j;
NODEt;
for（i=0;i<99;i++）
{
j=i+1;//j代表无序区的起点
t=DATA[j];//将待插入的结点保存到t中，防止向后移动时被覆盖
for（;j>0;j--）//寻找插入点，并进行元素的移动
{
if（t.keyDATA[j]=DATA[j-1];//结点向后移动
elsebreak;//否则，找到插入点
}
DATA[j]=t;//插入待排序的结点
}
}
//********************************************
//直接插入排序（带监视哨）
//********************************************
voidsinser（NODEdata[]）
{
inti,j;
for（i=2;i<=100;i++）
{
j=i;
data[0]=data[j];//设置监视哨，将其设置为待插入的结点
while（data[0].key{
data[j]=data[j-1];//前一结点向后移动
j--;
}
data[j]=data[0];//插入待排序的结点，即监视哨的值
}
}
//**********************************************************
//希尔排序算法
//**********************************************************
voidshellsort（）
{
intj;
intk;
NODEt;
intn=50;//置初始增量为元素个数的一半
while（n>=1）//依次取出各增量
{
for（k=n;k<100;k++）//对每一元素实施插入排序，将其分别插入各自的分组中
{
t=DATA[k];//保存待插入记录
j=k-n;//待插入记录所属分组的前一记录
while（j>=0&&t.key{
DATA[j+n]=DATA[j];//插入排序，较大的前一记录向后移动
j-=n;//寻找本分组的前一记录
}
DATA[j+n]=t;//插入一个记录
}
n/=2;//增量减半
}
}
//********************************************
//主函数
//********************************************
voidmain（）
{
inti;
creatfile（）;//创建磁盘文件
load（）;//导入磁盘文件信息
prn（DATA）;
//quicksort（DATA,0,99）;//在区间0-99之间进行快速排序
//selesort（DATA）;//选择排序
//dselesort（DATA）;//改进的选择排序
pasort（DATA）;//冒泡排序
//dpasort（DATA）;//改进的冒泡排序
//NODEdata[101];
//for（i=1;i<=100;i++）
//data[i]=DATA[i-1];//为方便描述,将原始数据DATA导入到data[101]中
//data[0]留空
//inser（）;
shellsort（）;
//sinser（data）;
//prn（data）;
//creatheap（data,100）;
//prn（data）;
//heapsort（data,100）;//对data中的100个数进行堆排序,排序区间（1--100）
//mergesort（data,100）;//对data中的100个数进行归并排序,排序区间（1-100）
//for（i=1;i<=100;i++）
//DATA[i-1]=data[i];
prn（DATA）;
//mergesort（data）;
}
升级会员 