核心代码
bubble-sort
#include <stdio.h>
using namespace std;
#define MAXN 10000000
//冒泡排序，第一次上机作业
void bubblesort(int a[],int n){
int tmp;
for (int i=0;i<n-1;i++){
for (int j=0;j+i+1<n;j++) {
if (a[j]>a[j+1]){
tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
}
}
}
return;
}
int n;
int a[MAXN];
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
bubblesort(a,n);
for(int i=0;i<n;i++)printf("%d ",a[i]);
return 0;
}
get-alot-randnum
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
//这个程序用来生成题中需要的大量的数据集
//这个程序要调用 getrandnum.c中定义的函数
//默认取值范围0x80000000到0x7FFFFFFF (int范围)
extern void f1(FILE *fp,int N,int s,int t);
extern void f2(FILE *fp,int N,int s,int t);
extern void f3(FILE *fp,int N,int s,int t);
extern void super_rand(int s,int t);
int s=0x80000000,t=0x7FFFFFFF;
char filename[17][128];
char tmp1[]="./dataset/randnum-",tmp2[]=".txt",tmp3[10]="100";
char tmp4[]="-increase",tmp5[]="-decrease",tmp6[]="-rand";
//生成的文件名形如 ./dataset/randnum-100-increase.txt
void Solve_Filename(){
for(int i=1;i<=15;i++){
strcpy(filename[i],tmp1);
}
for(int i=2;i<=6;i++){
strcat(filename[1+(i-2)*3],tmp3);
strcat(filename[2+(i-2)*3],tmp3);
strcat(filename[3+(i-2)*3],tmp3);
strcat(filename[1+(i-2)*3],tmp4);
strcat(filename[2+(i-2)*3],tmp5);
strcat(filename[3+(i-2)*3],tmp6);
strcat(filename[1+(i-2)*3],tmp2);
strcat(filename[2+(i-2)*3],tmp2);
strcat(filename[3+(i-2)*3],tmp2);
tmp3[i+1]='0';
tmp3[i+2]='\0';
}
}
int main(){
srand(time(NULL));
Solve_Filename();
int tmp=100;
for(int i=2;i<=6;i++){
FILE *fp1,*fp2,*fp3;
fp1=fopen(filename[1+(i-2)*3],"w");
fp2=fopen(filename[2+(i-2)*3],"w");
fp3=fopen(filename[3+(i-2)*3],"w");
f1(fp1,tmp,s,t);
f2(fp2,tmp,s,t);
f3(fp3,tmp,s,t);
if(fclose(fp1)){
printf("cannot close the file!\n");
exit(0);
}
if(fclose(fp2)){
printf("cannot close the file!\n");
exit(0);
}
if(fclose(fp3)){
printf("cannot close the file!\n");
exit(0);
}
tmp*=10;
}
return 0;
}
getrandnum-1
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;
bool cmp(int a, int b){return b < a;}
int n,s,t,type,a[1000000+666];
int main() {
srand(time(0));
cin>>n>>s>>t>>type;
ofstream fout("randnum.txt");
for(int i = 0; i < n; i++)a[i] = s + rand() % (t-s+1);
if(type == 1)sort(a, a + n);
else if(type == 2)sort(a, a + n, cmp);
for(int w = 0; w < n; w++)fout<<a[w]<<" ";
fout.close();
return 0;
}
getrandnum
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
//用于生成随机数据
//生成的数据数量是N,范围在[s,t],T是生成数据的类型
//T 1顺序递增 2顺序递减 3随机取值
//这里的递增和递减指的是严格单调递增和严格严格单调递减
int super_rand(int s,int t);
void f1(FILE *fp,int N,int s,int t){
int tmp=super_rand(s,t);
fprintf(fp,"%u ",tmp);
int tmp1;
for(int i=2;i<=N;i++){
tmp1=super_rand(s,t);
while(tmp1<tmp){
tmp1=super_rand(s,t);
}
tmp=tmp1;
fprintf(fp,"%u ",tmp);
}
}
void f2(FILE *fp,int N,int s,int t){
int tmp=super_rand(s,t);
fprintf(fp,"%d ",tmp);
int tmp1;
for(int i=2;i<=N;i++){
tmp1=super_rand(s,t);
while(tmp1>tmp){
tmp1=super_rand(s,t);
}
tmp=tmp1;
fprintf(fp,"%d ",tmp);
}
}
void f3(FILE *fp,int N,int s,int t){
int tmp;
for(int i=1;i<=N;i++){
tmp=super_rand(s,t);
fprintf(fp,"%d ",tmp);
}
}
int super_rand(int s,int t){
//为什么我要写一个super_rand?因为我的库函数中 RAND_MAX仅仅为32767
//rand()生成的数据在[0,RAND_MAX] 这么小的数据，显然是无法很好地获得随机数据
//我通过线性映射，近似地将[0,RAND_MAX]映射到了我们需要的[s,t]
long long randlen=RAND_MAX+1;
long long mylen=(long long)t-(long long)s+1; //由于t-s+1可能超过int的范围，我用long long类型来存
double tmp1=(double)(rand())/randlen;
long long tmp2=mylen*tmp1;
int ans=(int)(tmp2+(long long)s);
return ans;
}
/*
int main(){
int N,s,t,T;
scanf("%d%d%d%d",&N,&s,&t,&T);
srand(time(NULL));
FILE *fp1;
fp1=fopen("get-random-num-result.txt","w");
if(T==1)f1(fp1,N,s,t);
else if(T==2)f2(fp1,N,s,t);
else f3(fp1,N,s,t);
if(fclose(fp1)){
printf("cannot close the file!\n");
exit(0);
}
return 0;
}
*/
insertion-sort
#include<cstdio>
using namespace std;
#define MAXN 10000000
//插入排序，第一次上机作业
int n;
int a[MAXN];
void insertionsort(int arr[],int len){
int tmp,i;
for(int j=1;j<len;j++){
tmp=arr[j];
i=j-1;
while(i>0 && arr[i]>tmp){
arr[i+1]=arr[i];
i--;
}
arr[i+1]=tmp;
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
insertionsort(a,n);
for (int i=0;i<n;i++)printf("%d ",a[i]);
return 0;
}
mergingsort
#include <cstdio>
#include <ctime>
using namespace std;
#define MAXN 10000000
//归并排序，第一次上机作业
int n;
int a[MAXN],b[MAXN];
void merge(int arr[],int left,int mid,int right,int tmp[]){
int i=left;
int j=mid+1;
int t = 0;
while (i<=mid && j<=right){
if (arr[i]<=arr[j]){
tmp[t++]=arr[i++];
}else{
tmp[t++]=arr[j++];
}
}
while(i<=mid)tmp[t++]=arr[i++];
while(j<=right)tmp[t++]=arr[j++];
t=0;
while(left<=right)arr[left++]=tmp[t++];
}
void mergesort(int arr[],int left,int right,int tmp[]){
if (left<right){
int mid=(left+right)/2;
mergesort(arr,left,mid,tmp);
mergesort(arr,mid+1,right,tmp);
merge(arr,left,mid,right,tmp);
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
mergesort(a,0,n-1,b);
for(int i=0;i<n;i++)printf("%d ",a[i]);
return 0;
}
quick-get-random
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <string.h>
using namespace std;
//没办法，这个是用来快速得到需要的数据集而生的
bool cmp(int a, int b){return b < a;}
int s,t,a[1000000+66];
char filename[17][128];
char tmp1[]="./dataset/randnum-",tmp2[]=".txt",tmp3[10]="100";
char tmp4[]="-increase",tmp5[]="-decrease",tmp6[]="-rand";
void Solve_Filename(){
for(int i=1;i<=15;i++){
strcpy(filename[i],tmp1);
}
for(int i=2;i<=6;i++){
strcat(filename[1+(i-2)*3],tmp3);
strcat(filename[2+(i-2)*3],tmp3);
strcat(filename[3+(i-2)*3],tmp3);
strcat(filename[1+(i-2)*3],tmp4);
strcat(filename[2+(i-2)*3],tmp5);
strcat(filename[3+(i-2)*3],tmp6);
strcat(filename[1+(i-2)*3],tmp2);
strcat(filename[2+(i-2)*3],tmp2);
strcat(filename[3+(i-2)*3],tmp2);
tmp3[i+1]='0';
tmp3[i+2]='\0';
}
}
int main() {
s=0,t=0x7FFFFF00;//防止溢出
srand(time(0));
Solve_Filename();
int tmp=100;
for(int i=2;i<=6;i++){
ofstream fout1(filename[1+(i-2)*3]);
ofstream fout2(filename[2+(i-2)*3]);
ofstream fout3(filename[3+(i-2)*3]);
for(int i=0;i<tmp;i++)a[i]=s+rand()%(t-s+1);
for(int i=0;i<tmp;i++)fout3<<a[i]<<" ";
sort(a,a+tmp);
for(int i=0;i<tmp;i++)fout1<<a[i]<<" ";
sort(a,a+tmp,cmp);
for(int i=0;i<tmp;i++)fout2<<a[i]<<" ";
fout1.close();
fout2.close();
fout3.close();
tmp*=10;
}
return 0;
}
test-getans
//要和three-sort.cpp一起编译
// g++ .\test-getans.cpp .\three-sort.cpp -o testcases.exe
#include<iostream>
#include<fstream>
#include<cstdio>
#include<stdio.h>
#include<ctime>
#include<string.h>
using namespace std;
int a[1000000+66],b[1000000+66],n;
char filename[17][128];
char tmp1[]="./dataset/randnum-",tmp2[]=".txt",tmp3[10]="100";
char tmp4[]="-increase",tmp5[]="-decrease",tmp6[]="-rand";
extern void bubblesort(int a[],int n);
extern void mergesort(int arr[],int left,int right,int tmp[]);
extern void insertionsort(int arr[],int len);
void Solve_Filename(){
for(int i=1;i<=15;i++){
strcpy(filename[i],tmp1);
}
for(int i=2;i<=6;i++){
strcat(filename[1+(i-2)*3],tmp3);
strcat(filename[2+(i-2)*3],tmp3);
strcat(filename[3+(i-2)*3],tmp3);
strcat(filename[1+(i-2)*3],tmp4);
strcat(filename[2+(i-2)*3],tmp5);
strcat(filename[3+(i-2)*3],tmp6);
strcat(filename[1+(i-2)*3],tmp2);
strcat(filename[2+(i-2)*3],tmp2);
strcat(filename[3+(i-2)*3],tmp2);
tmp3[i+1]='0';
tmp3[i+2]='\0';
}
}
int main(){
ofstream fout("data.txt");
clock_t startTime, endTime;
Solve_Filename();
int scale=100;
for(int i=2;i<=6;i++){
ifstream fin1(filename[1+(i-2)*3]);
ifstream fin2(filename[2+(i-2)*3]);
ifstream fin3(filename[3+(i-2)*3]);
for(n=0;n<scale;n++)fin1>>a[n];
startTime=clock();
mergesort(a,0,n-1,b);
endTime = clock();
fout<<"Mergesort"<<n<<"Increase"<<"RunTime: "<<(1000*( (double) (endTime - startTime) / CLOCKS_PER_SEC))<<"ms"<<endl;
fin1.close();
for(n=0;n<scale;n++)fin2>>a[n];
startTime=clock();
mergesort(a,0,n-1,b);
endTime = clock();
fout<<"Mergesort"<<n<<"Decrease"<<"RunTime: "<<(1000*( (double) (endTime - startTime) / CLOCKS_PER_SEC))<<"ms"<<endl;
fin2.close();
for(n=0;n<scale;n++)fin3>>a[n];
startTime=clock();
mergesort(a,0,n-1,b);
endTime = clock();
fout<<"Mergesort"<<n<<"Rand"<<"RunTime: "<<(1000*( (double) (endTime - startTime) / CLOCKS_PER_SEC))<<"ms"<<endl;
fin3.close();
scale*=10;
}
scale=100;
for(int i=2;i<=6;i++){
ifstream fin1(filename[1+(i-2)*3]);
ifstream fin2(filename[2+(i-2)*3]);
ifstream fin3(filename[3+(i-2)*3]);
for(n=0;n<scale;n++)fin1>>a[n];
startTime=clock();
insertionsort(a,n);
endTime = clock();
fout<<"Insertsort"<<n<<"Increase"<<"RunTime: "<<(1000*( (double) (endTime - startTime) / CLOCKS_PER_SEC))<<"ms"<<endl;
fin1.close();
for(n=0;n<scale;n++)fin2>>a[n];
startTime=clock();
insertionsort(a,n);
endTime = clock();
fout<<"Insertsort"<<n<<"Decrease"<<"RunTime: "<<(1000*( (double) (endTime - startTime) / CLOCKS_PER_SEC))<<"ms"<<endl;
fin2.close();
for(n=0;n<scale;n++)fin3>>a[n];
startTime=clock();
insertionsort(a,n);
endTime = clock();
fout<<"Insertsort"<<n<<"Rand"<<"RunTime: "<<(1000*( (double) (endTime - startTime) / CLOCKS_PER_SEC))<<"ms"<<endl;
fin3.close();
scale*=10;
}
scale=100;
for(int i=2;i<=6;i++){
ifstream fin1(filename[1+(i-2)*3]);
ifstream fin2(filename[2+(i-2)*3]);
ifstream fin3(filename[3+(i-2)*3]);
for(n=0;n<scale;n++)fin1>>a[n];
startTime=clock();
bubblesort(a,n);
endTime = clock();
fout<<"Bubblesort"<<scale<<"Increase"<<"RunTime: "<<(1000*( (double) (endTime - startTime) / CLOCKS_PER_SEC))<<"ms"<<endl;
fin1.close();
for(n=0;n<scale;n++)fin2>>a[n];
startTime=clock();
bubblesort(a,n);
endTime = clock();
fout<<"Bubblesort"<<scale<<"Decrease"<<"RunTime: "<<(1000*( (double) (endTime - startTime) / CLOCKS_PER_SEC))<<"ms"<<endl;
fin2.close();
for(n=0;n<scale;n++)fin3>>a[n];
startTime=clock();
bubblesort(a,n);
endTime = clock();
fout<<"Bubblesort"<<scale<<"Rand"<<"RunTime: "<<(1000*( (double) (endTime - startTime) / CLOCKS_PER_SEC))<<"ms"<<endl;
fin3.close();
scale*=10;
}
fout.close();
return 0;
}
three-sort
//写好接口，方便调用
#include <stdio.h>
using namespace std;
void bubblesort(int a[],int n){
int tmp;
for (int i=0;i<n-1;i++){
for (int j=0;j+i+1<n;j++) {
if (a[j]>a[j+1]){
tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
}
}
}
return;
}
void merge(int arr[],int left,int mid,int right,int tmp[]){
int i=left;
int j=mid+1;
int t = 0;
while (i<=mid && j<=right){
if (arr[i]<=arr[j]){
tmp[t++]=arr[i++];
}else{
tmp[t++]=arr[j++];
}
}
while(i<=mid)tmp[t++]=arr[i++];
while(j<=right)tmp[t++]=arr[j++];
t=0;
while(left<=right)arr[left++]=tmp[t++];
}
void mergesort(int arr[],int left,int right,int tmp[]){
if (left<right){
int mid=(left+right)/2;
mergesort(arr,left,mid,tmp);
mergesort(arr,mid+1,right,tmp);
merge(arr,left,mid,right,tmp);
}
}
void insertionsort(int arr[],int len){
int tmp,i;
for(int j=1;j<len;j++){
tmp=arr[j];
i=j-1;
while(i>0 && arr[i]>tmp){
arr[i+1]=arr[i];
i--;
}
arr[i+1]=tmp;
}
}