代码

#include<cstdio>
#include<cstdlib>
#include<algorithm> 
#include<ctime>
using namespace std;
const int N=(int)10005;
const int n=10000;
int orgin[N],to_sort[N],tmp[N],tot;
int cal,cal1; 

int random(int x){return (long long)rand()*rand()%x;}

void quick_sort(int q[], int l, int r){
	++cal1; 
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[l];
    while (i < j){
        do i ++,cal1++ ; while (q[i] < x) ;
        do j --,cal1++ ; while (q[j] > x) ;
        ++cal1;
        if (i < j) swap(q[i], q[j]),cal++;
        else break;
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

void merge_sort(int q[], int l, int r){
	++cal1;
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    ++cal1;
    while (i <= mid && j <= r){
    	++cal1;
        if (q[i] < q[j]) tmp[k ++ ] = q[i ++ ],cal++;
        else tmp[k ++ ] = q[j ++ ],cal++;
    }
    while (i <= mid) tmp[k ++ ] = q[i ++ ],cal++,cal1++;
    while (j <= r) tmp[k ++ ] = q[j ++ ],cal++,cal1++;
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j],cal++;
}

void select_sort(int q[],int l,int r){
	for(int i=l;i<=r;i++){
		int sel=q[i],pos=i;
		for(int j=i;j<=r;j++){
			++cal;
			++cal1;
			if(q[j]<sel) sel=q[j],pos=j;
		}
		swap(q[i],q[pos]),++cal;
	}
}

void up(int p){
	while(p>1){
		++cal1;
		if(tmp[p]<tmp[p/2]) ++cal,swap(tmp[p],tmp[p/2]),p/=2;
		else break;
	}
}

void insert(int val){
	tmp[++tot]=val;
	up(tot);
}

void down(int p){
	int s=p*2;
	while(s<=tot){
		++cal1;
		++cal1;
		if(s<tot && tmp[s]>tmp[s+1]) ++cal,s++;
		if(tmp[s]<tmp[p]) ++cal,swap(tmp[p],tmp[s]),p=s,s=p*2;
		else break;
	}
}

void heap_sort(int q[],int l,int r){
	tot=0;
	for(int i=l;i<=r;i++) insert(q[i]);
	for(int i=l;i<=r;i++) q[i]=tmp[1],tmp[1]=tmp[tot--],down(1);
}

void insert_sort(int q[],int l,int r){
	for(int i=l+1;i<=r;i++){
		int key=q[i];
		int j=i-1;
		
		while(j>=1 && q[j]>key) ++cal,++cal1,q[j+1]=q[j],j--;
		q[j+1]=key;
	}
} 

void test(){
	for(int i=1;i<=n;i++) to_sort[i]=orgin[i];
	cal=cal1=0;
	select_sort(to_sort,1,n);
	printf("选择排序比较次数%d移动次数%d\n",cal1,cal);
	for(int i=1;i<=n;i++) to_sort[i]=orgin[i];
	cal=cal1=0;
	heap_sort(to_sort,1,n);
	printf("桶排序比较次数%d移动次数%d\n",cal1,cal);
	for(int i=1;i<=n;i++) to_sort[i]=orgin[i];
	cal=cal1=0;
	merge_sort(to_sort,1,n);
	printf("归并排序比较次数%d移动次数%d\n",cal1,cal);
	for(int i=1;i<=n;i++) to_sort[i]=orgin[i];
	cal=cal1=0;
	quick_sort(to_sort,1,n);
	printf("快速排序比较次数%d移动次数%d\n",cal1,cal);
	for(int i=1;i<=n;i++) to_sort[i]=orgin[i];
	cal=cal1=0;
	insert_sort(to_sort,1,n);
	printf("插入排序比较次数%d移动次数%d\n",cal1,cal);
}

int main(){
	srand((unsigned)time(0));
	for(int i=1;i<=n;i++) orgin[i]=random(100000);
	printf("随机数据:\n");
	test();
	for(int i=1;i<=n;i++) orgin[i]=i*10;
	printf("从小到大:\n");
	test();
	for(int i=1;i<=n;i++) orgin[n-i+1]=i*10;
	printf("从大到小:\n");
	test();
	return 0;
}

评测结果