云栖社区聚能聊、问答管理员~发福利、搞怪,八卦我来,论技术、发话题、写博客你上!
//有多种排序法。你看一下#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXSIZE 200000typedef int keytype;
typedef struct
{
keytype key;
}recordtype;typedef struct
{
recordtype r[MAXSIZE + 1];
int length;
}table;/**************************************************************/
/* 二 分 法 插 入 排 序 算 法 */
/**************************************************************/
void binarysort(table *tab)
{
FILE *fa;
fa = fopen("二分法插入排序.txt","w");
int i,j,left,right,mid;
for (i = 2; i <= tab->length; i++) //依次插入从第2个开始的所有元素
{
tab->r[0].key = tab->r[i].key; //保存待插入的元素
left = 1;
right = i - 1;
while (left <= right) //查找第i个元素的插入位置
{
mid = (left + right)/2; //取中间位置
if (tab->r[i].key < tab->r[mid].key)
right = mid - 1;
else
left = mid + 1;
} //插入位置为left
for (j = i - 1; j >= left; j--)
tab->r[j + 1].key = tab->r[j].key; //后移、空出插入位置
tab->r[left].key = tab->r[0].key; //插入第i个元素的副本
}
fprintf(fa,"经过二分法插入排序之后的结果为: \n");
for( i = 1; i <= tab->length; i++)
fprintf(fa,"%d ",tab->r[i].key);
fclose(fa);
}/**************************************************************/
/* 冒 泡 排 序 算 */
/**************************************************************/
void bubblesort(table *tab)
{
FILE *fb;
fb = fopen("冒泡排序.txt","w");
int i,j,done;
i = 1;
done = 1;
while(i <= tab->length && done) //最多进行tab->length 次冒泡、如果没有发生交换则结束
{
done = 0;
for (j = 1; j <= tab->length - i; j++)
if(tab->r[j + 1].key < tab->r[j].key)
{
tab->r[0].key = tab->r[j].key; //以第0个元素作为中间单元进行交换
tab->r[j].key = tab->r[j + 1].key;
tab->r[j + 1].key = tab->r[0].key;
done = 1;
}
i++;
}
fprintf(fb,"\n经过冒泡排序之后的结果为: \n");
for( i = 1; i <= tab->length; i++)
fprintf(fb,"%d ",tab->r[i].key);
fclose(fb);
}/**************************************************************/
/* 快 速 排 序 算 法 */
/**************************************************************/
void quicksort(table *tab,int left,int right)
{
int i,j;
if (left < right)
{
i = left;
j = right;
tab->r[0].key = tab->r[i].key; //准备以本次最左边的元素值为标准进行划分、先保存其值
do
{
while(tab->r[j].key > tab->r[0].key && i < j) //从右向左找第1个不小于标准值的位置j
j--;
if (i < j)
{
tab->r[i].key = tab->r[j].key; //将第j个元素置于左端并重置i
i++;
}
while(tab->r[i].key = tab->r[0].key && i < j) //从左向右找第1个不小于标准值的位置i
i++;
if (i < j)
{
tab->r[j].key = tab->r[i].key; //将第i个元素置于左端并重置j
j--;
}
} while (i != j);
tab->r[i].key = tab->r[0].key; //将标准值放入它的最终位置、本次划分结束
quicksort(tab,left,i - 1); //对标准值左边递归调用本函数
quicksort(tab,i + 1,right); //对标准值右边递归调用本函数
}
}/**************************************************************/
/* 直 接 选 择 排 序 算 法 */
/**************************************************************/
void simpleselectsort(table *tab)
{
FILE *fc;
fc = fopen("直接选择排序.txt","w");
int i,j,k;
for (i = 1; i <= tab->length -1; i++) //每次选择一个最小的元素(的位置)、和第i个元素交换
{
k = i; //记下当前最小元素的位置
for (j = i + 1; j <= tab->length; j++) //向右查找更小的元素
if (tab->r[j].key < tab->r[k].key) //修改当前最小元素的位置
k = j;
if (k != i) /*如果第i次选到的最小元素位置k不等于i、则将第k、i个元素交换*/
{
tab->r[0].key = tab->r[k].key; //以没有用到的第0个元素作为中间单元进行交换
tab->r[k].key = tab->r[i].key;
tab->r[i].key = tab->r[0].key;
}
}
fprintf(fc,"\n经过直接选择排序之后的结果为: \n");
for( i = 1; i <= tab->length; i++)
fprintf(fc,"%d ",tab->r[i].key);
fclose(fc);
}/**************************************************************/
/* 堆 排 序 算 法 */
/**************************************************************/
void sift(table *tab,int k,int m)
{
int i,j,finished;
i = k;
j = 2 * i;
tab->r[0].key = tab->r[k].key;
finished = 0;
while ((j <= m) && (!finished))
{
if((j < m) && (tab->r[j + 1].key < tab->r[j].key))
j++;
if(tab->r[0].key <= tab->r[j].key)
finished = 1;
else
{
tab->r[i].key = tab->r[j].key;
i = j;
j = 2 * j;
}
}
tab->r[i].key = tab->r[0].key;
}
void heapsort(table *tab)
{
FILE *fd;
fd = fopen("堆排序.txt","w");
int i;
for (i = tab->length/2; i >= 1; i--)
sift(tab,i,tab->length); //对所有元素建堆
for (i = tab->length; i >= 2; i--) //i表示当前堆的大小、即等待排序的元素的个数
{
tab->r[0].key = tab->r[i].key;
tab->r[i].key = tab->r[1].key;
tab->r[1].key = tab->r[0].key; /*上述3条语句为将堆中最小元素和最后一个元素交换*/
sift(tab,1,i - 1);
}
fprintf(fd,"\n经过堆排序之后的结果为: \n");
for( i = 1; i <= tab->length; i++)
fprintf(fd,"%d ",tab->r[i].key);
fclose(fd);
}
/**************************************************************/
/* 归 并 排 序 算 法 */
/**************************************************************/
void merge(table *tabs,table *tabg,int u,int m,int v)
{
int i,j,k,t;
i = u;
j = m + 1;
k = u;
while(i <= m && j <= v)
{
if (tabs->r[i].key <= tabs->r[j].key)
{
tabg->r[k].key = tabs->r[i].key;
i++;
}
else
{
tabg->r[k].key = tabs->r[j].key;
j++;
}
k++;
}
if(i <= m)
for(t = i; t <= m; t++)
tabg->r[k + t - i].key = tabs->r[t].key;
else
for(t = j; t <= v; t++)
tabg->r[k + t - j].key = tabs->r[t].key;}
void mergepass(table *tabs, table *tabg, int len)
{
int i,j,n;
n = tabg->length = tabs->length;
i = 1;
while(i <= n - 2 * len + 1)
{
merge(tabs,tabg,i,i + len - 1,i + 2 * len - 1);
i = i + 2 * len;
}
if (i + len - 1 < n)
merge(tabs,tabg,i,i + len - 1,n);
else
for(j = i; j <= n; j++)
tabg->r[j].key = tabs->r[j].key;
}
void mergesort(table *tab)
{
FILE *fe;
fe = fopen("归并排序.txt","w");
int len,i;
table temp; //中间变量
len = 1; //初始时有序段的长度为1
while (len < tab->length) //有序段的长度小于待排序元素的个数、继续归并
{
mergepass(tab,&temp,len); //一趟归并、结果在temp中
len = 2 * len;
mergepass(&temp,tab,len); //一趟归并、结果在tab中
len = 2 * len;
}
fprintf(fe,"\n经过归并排序之后的结果为: \n");
for( i = 1; i <= tab->length; i++)
fprintf(fe,"%d ",tab->r[i].key);
}
double max(double x,double y)
{
double z;
z =(x>y)?x:y;
return z;
}
/**************************************************************/
/* 主 函 数 */
/**************************************************************/
void main()
{
printf("\n\n\n\n");
printf(" /**********************************************************/\n");
printf(" /*****************本程序使用了二分法插入排序***************/\n");
printf(" /****冒泡排序、快速排序、直接选择排序、堆排序、归并排序****/\n");
printf(" /**************运用六种方法找出三种较快的方法**************/\n");
printf(" /***************结果已经保存在各文件的.txt中***************/\n");
printf(" /**********************************************************/\n");
int i;
double max1,max2,max3;
table tab;
FILE *fs;
fs = fopen("快速排序及其各种排序的速度.txt","w"); srand(10);
for(i = 1; i <= MAXSIZE; i++)
tab.r[i].key = rand() + 2000;
tab.length = MAXSIZE;
clock_t start, finish;
double duration[6];
start = clock();
binarysort(&tab);
finish = clock();
duration[0] = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "二分法插入排序所花费的时间 %f seconds:\n ", duration[0]);
start = clock();
bubblesort(&tab);
finish = clock();
duration[1] = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "冒泡排序所花费的时间 %f seconds:\n ", duration[1]);
fprintf(fs,"\n经过快速排序之后的结果为: \n");
for( i = 1; i <= tab.length; i++)
fprintf(fs,"%d ",tab.r[i].key);
start = clock();
quicksort(&tab,1,10);
finish = clock();
duration[2] = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "快速排序所花费的时间 %f seconds:\n ", duration[2]);
start = clock();
simpleselectsort(&tab);
finish = clock();
duration[3] = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "直接选择排序所花费的时间 %f seconds:\n ", duration[3]);
start = clock();
heapsort(&tab);
finish = clock();
duration[4] = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "堆排序所花费的时间 %f seconds:\n ", duration[4]);
start = clock();
mergesort(&tab);
finish = clock();
duration[5] = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "归并排序所花费的时间 %f seconds:\n ", duration[5]);
fprintf( fs,"\n\n 二分法插入排序所花费的时间 %f seconds:\n ", duration[0]);
fprintf( fs,"冒泡排序所花费的时间 %f seconds:\n ", duration[1]);
fprintf( fs,"快速排序所花费的时间 %f seconds:\n ", duration[2]);
fprintf( fs,"直接选择排序所花费的时间 %f seconds:\n ", duration[3]);
fprintf( fs,"堆排序所花费的时间 %f seconds:\n ", duration[4]);
fprintf( fs,"归并排序所花费的时间 %f seconds:\n ", duration[5]);
max1 = max(duration[0],duration[1]);
max2 = max(duration[2],duration[3]);
max3 = max(duration[4],duration[5]); printf("\n\n\n");
printf(" /**********************************************************/\n");
if(max1 == duration[0])
printf(" /***********************冒泡排序排序快*********************/\n");
else
printf(" /**********************二分法插入排序快********************/\n");
if(max2 == duration[2])
printf(" /***********************直接选择排序快*********************/\n");
else
printf(" /*************************快速排序快***********************/\n");
if(max3 == duration[4])
printf(" /*************************归并排序快***********************/\n");
else
printf(" /************************堆排序排序快**********************/\n");
printf(" /**********************************************************/\n"); fclose(fs); //system("pause"); }
2019-07-17 22:50:49