排序算法PK...!!!

发布网友发布时间：2024-03-28 23:46

共1个回答

热心网友时间：2024-07-19 21:40

//我这用的是c++，不是java
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define MAXNUM 100000.0 // 定义数字最大数值
#define MAXLENGTH 100000 // 定义数组的最大长度
#define TRUE 1
#define FALSE 0

void creatdata();
int readdata(int num[]);
void selectionSort(int num[], int length);
void insertSort(int num[],int length);
void bubbleSort(int num[],int length);
void shellSort(int num[],int length);
void quickSort(int num[], int left, int rigth);
void writefile(int num[],int length,char filename[]);
int judge(int num[],int length);
void sort();

// 主程序
int main ()
{
creatdata(); // 创建数据文件
sort(); // 排序及比较
printf("Press Enter to continue...");
getchar();
return 0;
}

// 创建数据文件
void creatdata()
{
int num[MAXLENGTH] = {0}; // 存储数组
printf("创建数据文件……\n");
printf("请输入数据个数( <%d )：", MAXLENGTH);
int length;
scanf("%d",&length);
getchar();
srand((unsigned)time(NULL));
int i;
for (i = 0; i < length; i++)
{
// num[i] = rand() % MAXNUM;
num[i]=(int)(MAXNUM*rand()/(RAND_MAX+1.0)); // 产生随机数
}
writefile(num,length,"data.txt"); // 数据写入文件
}

// 将数组写入文件
void writefile(int num[],int length,char filename[])
{
FILE *fp;
if ((fp=fopen(filename,"w"))==NULL)
{
printf("文件创建失败，程序将退出!\n");
exit(1);
}
int i;
for (i = 0; i < length; i++)
{
fprintf(fp,"%d\t",num[i]); // 数据写入文件
}
fclose(fp);
}

// 从文件中读取数据
int readdata(int num[])
{
FILE *fp;
if ((fp=fopen("data.txt","r"))==NULL)
{
printf("文件无法打开，程序将退出!\n");
exit(1);
}
int length;
int i;
for (length=0,i=0;!feof(fp);i++,length++)
{
fscanf(fp,"%d",&num[i]); // 读取数据
fgetc(fp);
}
fclose(fp);
return length; // 返回数据长度
}

// 选择排序
void selectionSort(int num[],int length)
{
int i,j,min,temp;
for (i=0;i<length;i++)
{
min=i;
for (j=i+1;j<length;j++)
{
if (num[j]<num[min])
min=j;
}
temp = num[i];
num[i] = num[min];
num[min] = temp;
}
}

// 插入排序
void insertSort(int num[],int length)
{
int i,j,temp;
for (i=1;i<length;i++)
{
temp = num[i];
for (j=i ; j>0 && temp < num[j-1] ; j--)
{
num[j]=num[j-1];
}
num[j]=temp;
}
}

// 冒泡排序
void bubbleSort(int num[],int length)
{
int i,j,temp;
for (i = 0; i < length ; i++)
{
for (j = 0; j < length - i - 1; j++)
{
if (num[j]>num[j + 1])
{
temp=num[j];
num[j]=num[j + 1];
num[j + 1]=temp;
}
}
}
}

// 希尔排序
void shellSort(int num[],int length)
{
int h,i,j,temp;
for (h=length/2;h>0;h=h/2)
{
for (i=h;i<length;i++)
{
temp=num[i];
for (j=i-h;(j>=0&&temp<num[j]);j-=h)
{
num[j+h]=num[j];
}
num[j+h]=temp;
}
}
}

// 实现快速排序
void quickSort(int num[], int left, int right)
{
int i, j;
int middle = left; // 记录中段
int pivot; // 记录中段元素
if (left < right) // 判断递归的终点是否只剩一个数了，即该段是否排序完毕
{
// i和j存储还需要判断排序的范围
for (i = left, j = right; i < j; )
{
// 对中段元素右边进行扫描，然后j往左推
for (; j > middle; j--)
{
// 如果右边有比中段元素小的，进行数据交换并跳出此循环
if (num[j] < num[middle])
{
pivot = num[j];
num[j] = num[middle];
num[middle] = pivot;
middle = j;
break;
}
}
j--;

// i先往右推，然后对中段元素左边进行扫描
i++;
for (; i < middle; i++)
{
// 如果左边有比中段元素大的，进行数据交换并跳出此循环
if (num[i] > num[middle])
{
pivot = num[i];
num[i] = num[middle];
num[middle] = pivot;
middle = i;
break;
}
}
}
// 此循环执行完后,比中段元素小的都在中段左边,比中段元素大的都在中段右边
quickSort(num, left, middle-1); // 递归地使用快速排序方法对支点左段（left）进行排序
quickSort(num, middle+1, right); // 递归地使用快速排序方法对支点右段（right）进行排序
}
}

// 判断排序结果是否正确
int judge(int num[],int length)
{
int i;
for (i = 0; i < length-1; i++)
{
if (num[i] > num[i+1])
{
printf("sort wrong!");
return FALSE;
}
}
return TRUE;
}

// 排序方法比较
void sort()
{
printf("排序方法比较……\n");
int num[MAXLENGTH] = {0}; // 存储数组
int copy[MAXLENGTH] = {0}; // 存储数组
int length = length = readdata(num); // 存储用户建立的数组长度
clock_t start, finish;
double times[5] = {0.0};

memcpy(copy, num, length*sizeof(int));
printf("1.实现选择排序……\n");
start = clock(); //记下初始时间
selectionSort(copy,length);
finish = clock(); //当前时间
times[0]=(double)(finish-start)/CLOCKS_PER_SEC;
if (judge(copy,length))
{
printf("The time is: %f seconds\n",times[0]);
writefile(copy,length,"selectionSort.txt");
}

memcpy(copy, num, length*sizeof(int));
printf("2.实现插入排序……\n");
start = clock(); //记下初始时间
insertSort(copy,length);
finish = clock(); //当前时间
times[1]=(double)(finish-start)/CLOCKS_PER_SEC;
if (judge(copy,length))
{
printf("The time is: %f seconds\n",times[1]);
writefile(copy,length,"insertSort.txt");
}

memcpy(copy, num, length*sizeof(int));
printf("3.实现冒泡排序……\n");
start = clock(); //记下初始时间
bubbleSort(copy,length);
finish = clock(); //当前时间
times[2]=(double)(finish-start)/CLOCKS_PER_SEC;
if (judge(copy,length))
{
printf("The time is: %f seconds\n",times[2]);
writefile(copy,length,"bubbleSort.txt");
}

memcpy(copy, num, length*sizeof(int));
printf("4.实现希尔排序……\n");
start = clock(); //记下初始时间
shellSort(copy,length);
finish = clock(); //当前时间
times[3]=(double)(finish-start)/CLOCKS_PER_SEC;
if (judge(copy,length))
{
printf("The time is: %f seconds\n",times[3]);
writefile(copy,length,"shellSort.txt");
}

memcpy(copy, num, length*sizeof(int));
printf("5.实现快速排序……\n");
start = clock(); //记下初始时间
quickSort(copy,0,length-1);
finish = clock(); //当前时间
times[4]=(double)(finish-start)/CLOCKS_PER_SEC;
if (judge(copy,length))
{
printf("The time is: %f seconds\n",times[4]);
writefile(copy,length,"quickSort.txt");
}

// 排序比较
int temp,i;
for (temp = 0,i = 1; i < 5; i++)
{
if (times[i] < times[i-1])
temp = i;
}
printf("排序最快的方法为：%d\n",temp+1);
printf("所用时间：%f seconds\n",times[temp]);
}