数据结构排序算法的实现与时间比较.docx
《数据结构排序算法的实现与时间比较.docx》由会员分享，可在线阅读，更多相关《数据结构排序算法的实现与时间比较.docx（13页珍藏版）》请在冰点文库上搜索。
数据结构排序算法的实现与时间比较
排序算法的实现与时间比较
#include
#include
#include
#include
#defineN10
typedefstructRecord
{
intkey;
intother;
}RecordType;
typedefstructSort
{
RecordType*ele;
}SortArray;
voidInsertSort（SortArray*a）//直接插入排序
{
inti,j;
RecordTypetemp;
LARGE_INTEGERm_nFreq;
LARGE_INTEGERm_nBeginTime;
LARGE_INTEGERnEndTime;
QueryPerformanceFrequency（&m_nFreq）;//获取时钟周期
QueryPerformanceCounter（&m_nBeginTime）;//获取时钟计数
for（i=0;i{
for（j=0;j{
if（a->ele[j].key>a->ele[j+1].key）
{
temp=a->ele[j];
a->ele[j]=a->ele[j+1];
a->ele[j+1]=temp;
}
}
}
QueryPerformanceCounter（&nEndTime）;
printf（"直接插入排序-升序：
"）;
PrintfSort（a）;
printf（"Timeis%lfms\n",（double）（nEndTime.QuadPart-m_nBeginTime.QuadPart）*1000/m_nFreq.QuadPart）;
for（i=0;i{
for（j=0;j{
if（a->ele[j].keyele[j+1].key）
{
temp=a->ele[j];
a->ele[j]=a->ele[j+1];
a->ele[j+1]=temp;
}
}
}
printf（"直接插入排序-降序：
"）;
PrintfSort（a）;
printf（"\n"）;printf（"\n"）;
}
voidBinsort（SortArray*a）//二分法排序
{
LARGE_INTEGERm_nFreq;
LARGE_INTEGERm_nBeginTime;
LARGE_INTEGERnEndTime;
QueryPerformanceFrequency（&m_nFreq）;//获取时钟周期
QueryPerformanceCounter（&m_nBeginTime）;//获取时钟计数
inti,j;
intleft,right,mid;
RecordTypetemp;
for（i=1;i{
temp=a->ele[i];
left=0;
right=i-1;
while（left<=right）//用二分法查找插入位置
{
mid=（left+right）/2;
if（temp.keyele[mid].key）right=mid-1;
elseleft=mid+1;
}
if（left!
=i）
{
for（j=i-1;j>=left;j--）a->ele[j+1]=a->ele[j];//挪动位置
a->ele[left]=temp;//插入数据
}
}
QueryPerformanceCounter（&nEndTime）;
printf（"二分法排序-升序：
"）;
PrintfSort（a）;
printf（"Timeis%lfms\n",（double）（nEndTime.QuadPart-m_nBeginTime.QuadPart）*1000/m_nFreq.QuadPart）;;
for（i=1;i{
temp=a->ele[i];
left=0;
right=i-1;
while（left<=right）//用二分法查找插入位置
{
mid=（left+right）/2;
if（temp.keyele[mid].key）left=mid+1;
elseright=mid-1;
}
if（left!
=i）
{
for（j=i-1;j>=left;j--）a->ele[j+1]=a->ele[j];//挪动位置
a->ele[left]=temp;//插入数据
}
}
printf（"二分法排序-降序：
"）;
PrintfSort（a）;
printf（"\n"）;printf（"\n"）;
}
voidBubbleSort（SortArray*a）//冒泡排序
{
LARGE_INTEGERm_nFreq;
LARGE_INTEGERm_nBeginTime;
LARGE_INTEGERnEndTime;
QueryPerformanceFrequency（&m_nFreq）;//获取时钟周期
QueryPerformanceCounter（&m_nBeginTime）;//获取时钟计数
inti,j,temp;
for（i=1;i{
for（j=N-1;j>=i;j--）//从后往前循环
{
if（a->ele[j-1].key>a->ele[j].key）//若前一个大于后一个，交换
{
temp=a->ele[j].key;
a->ele[j].key=a->ele[j-1].key;
a->ele[j-1].key=temp;
}
}
}
QueryPerformanceCounter（&nEndTime）;
printf（"冒泡排序-升序：
"）;
PrintfSort（a）;
printf（"Timeis%lfms\n",（double）（nEndTime.QuadPart-m_nBeginTime.QuadPart）*1000/m_nFreq.QuadPart）;
for（i=1;i{
for（j=N-1;j>=i;j--）//从后往前循环
{
if（a->ele[j-1].keyele[j].key）//若前一个大于后一个，交换
{
temp=a->ele[j].key;
a->ele[j].key=a->ele[j-1].key;
a->ele[j-1].key=temp;
}
}
}
printf（"冒泡排序-降序：
"）;
PrintfSort（a）;
printf（"\n"）;printf（"\n"）;
}
voidQuickSort1（SortArray*a,intleft,intright）//快速排序-升序
{
inti,j,temp;
if（left>=right）return;
i=left;
j=right;
temp=a->ele[i].key;//以第一个元素最为基准
while（i!
=j）
{
while（a->ele[j].key>=temp&&j>i）j--;//从右向左
if（i{
a->ele[i].key=a->ele[j].key;
i++;
}
elsebreak;
while（a->ele[i].key<=temp&&j>i）i++;//从左向右
if（i{
a->ele[j].key=a->ele[i].key;
j--;
}
elsebreak;
}
a->ele[i].key=temp;
QuickSort1（a,left,i-1）;
QuickSort1（a,i+1,right）;
}
voidQuickSort2（SortArray*a,intleft,intright）//快速排序-降序
{
inti,j,temp;
if（left>=right）return;
i=left;
j=right;
temp=a->ele[i].key;//以第一个元素最为基准
while（i!
=j）
{
while（a->ele[j].key<=temp&&j>i）j--;//从右向左
if（i{
a->ele[i].key=a->ele[j].key;
i++;
}
elsebreak;
while（a->ele[i].key>=temp&&j>i）i++;//从左向右
if（i{
a->ele[j].key=a->ele[i].key;
j--;
}
elsebreak;
}
a->ele[i].key=temp;
QuickSort2（a,left,i-1）;
QuickSort2（a,i+1,right）;
}
voidJiShuSort（SortArray*a）//基数排序
{
LARGE_INTEGERm_nFreq;
LARGE_INTEGERm_nBeginTime;
LARGE_INTEGERnEndTime;
QueryPerformanceFrequency（&m_nFreq）;//获取时钟周期
QueryPerformanceCounter（&m_nBeginTime）;//获取时钟计数
inti,j;
intvalue=a->ele[0].key;
intdigit=0;
RecordType*b=（RecordType*）malloc（sizeof（RecordType）*N）;
int*count=（int*）malloc（sizeof（int）*N）;//保存b中存放的数据的个数
int*now=（int*）malloc（sizeof（int）*N）;//保存每个待排序数据当前排序位置的值
intdivider[5]={1,10,100,1000,10000};//假设等待排序的数据最大不超过五个
for（i=0;i{
if（a->ele[i].key>value）value=a->ele[i].key;
count[i]=0;//初始化count数组
}
while（value!
=0）//计算最后value的位数
{
value=value/10;
digit++;
}
for（i=0;i{
for（j=0;j{
now[j]=（a->ele[j].key/divider[i]%10）;//统计每个桶中的记录数
count[j]=0;//每次分配前清空计数器
}
for（j=0;jfor（j=1;jfor（j=N-1;j>=0;j--）//从右向左，先入先出
{
b[count[now[j]]-1]=a->ele[j];
count[now[j]]--;
}
for（j=0;jele[j]=b[j];//把b里面的数据放回原来的数组，为下一轮基数排序做准备
}
QueryPerformanceCounter（&nEndTime）;
printf（"基数排序-升序：
"）;
PrintfSort（a）;
printf（"Timeis%lfms\n",（double）（nEndTime.QuadPart-m_nBeginTime.QuadPart）*1000/m_nFreq.QuadPart）;
}
voidPrintfSort（SortArray*s）//输出数组中的元素
{
inti;
for（i=0;iele[i]）;
}
intmain（）
{
SortArray*s=（SortArray*）malloc（sizeof（SortArray））;
inti;
s->ele=（RecordType*）malloc（sizeof（RecordType）*N）;
for（i=0;iele[i].key=rand（）%101;
printf（"随机生成的一组数为：
"）;
PrintfSort（s）;printf（"\n"）;printf（"\n"）;
LARGE_INTEGERm_nFreq;
LARGE_INTEGERm_nBeginTime;
LARGE_INTEGERnEndTime;
QueryPerformanceFrequency（&m_nFreq）;//获取时钟周期
SortArray*Insert_array;Insert_array=s;
InsertSort（Insert_array）;//直接插入排序
SortArray*Binsort_array;Binsort_array=s;
Binsort（Binsort_array）;//二分法排序
SortArray*Bubble_array;Bubble_array=s;
BubbleSort（Bubble_array）;//冒泡排序
SortArray*Quick_array1;Quick_array1=s;
QueryPerformanceCounter（&m_nBeginTime）;//获取时钟计数
QuickSort1（Quick_array1,0,N-1）;//快速排序-升序
QueryPerformanceCounter（&nEndTime）;
printf（"快速排序-升序：
"）;
PrintfSort（Quick_array1）;
printf（"Timeis%lfms\n",（double）（nEndTime.QuadPart-m_nBeginTime.QuadPart）*1000/m_nFreq.QuadPart）;
SortArray*Quick_array2;Quick_array2=s;
QuickSort2（Quick_array2,0,N-1）;//快速排序-降序
printf（"快速排序-降序：
"）;
PrintfSort（Quick_array2）;printf（"\n"）;
printf（"\n"）;
SortArray*JiShu_array;JiShu_array=s;
JiShuSort（JiShu_array）;//基数排序
}
升级会员 