k=N-1; while(k+1) {
r[k]=a[k]; k--; } Bubblesort(r,N);//冒泡法 } finish = clock(); duration = (double)(finish - start)/1000; print(r,N);
printf( "%f seconds\n", duration ); }break; case(2):
{ r[j]=r[i]; j--;
} } r[i]=swap; if(i>left)
quicksort(r,left,i-1); if(i<right)
quicksort(r,i+1,right); return; } //堆排序先建立堆 void creatheap(int r[],int i,int n) {
int j; int t; t=r[i];j=2*i; while(j<n) {
if((j<n)&&(r[j]<r[j+1]))j++; if(t<r[j]) {
r[i]=r[j]; i=j;j=2*i; } else j=n; r[i]=t; } } //堆排序 void heapsort(int r[],int n) { int t; for(int i=n/2;i>=0;i--) creatheap(r,i,n); for(i= n-1;i>=0;i--) { t=r[0]; r[0]=r[i]; r[i]=t; creatheap(r,0,i-1); } return;
#include <iostream.h> #include <stdlib.h> #include <iomanip.h> #include <time.h> #include <stdio.h>
const int N=1000;//数据量，用于检测算法质量 const int M=1000;//执行次数 //冒泡排序（递增） void Bubblesort(int r[],int n) {
{ cout<<"快速排序法"; start = clock(); for(i=0;i<M;i++) {
k=N-1; while(k+1) {
r[k]=a[k]; k--; } quicksort(r,0,N-1);//快速排序法 } finish = clock(); duration = (double)(finish - start)/1000; print(r,N); printf( "%f seconds\n", duration ); }break; case(3): { cout<<"堆排序法"; start = clock(); for(i=0;i<M;i++) { k=N-1; while(k+1) { r[k]=a[k]; k--; } heapsort(r,N);//堆排序法 } finish = clock(); duration = (double)(finish - start)/1000; print(r,N); printf( "%f seconds\n", duration ); }break; case(4): { cout<<"二路并归法"; start = clock();
for(i=0;i<M;i++) {
k=N-1; while(k+1) {
r[k]=a[k]; k--; } mergesort(r);//二路并归法 } finish = clock(); duration = (double)(finish - start)/1000; print(r,N); printf( "%f seconds\n", duration ); }break; } }
else r1[k++]=r[j++];
} while(i<=mid)
r1[k++]=r[i++]; while(j<=high)
r1[k++]=r[j++];
} void mergepass(int r[],int r1[],int length)//用来区分填入 merge 函数的变量计算式 {
for(int i=0;i<=n-1;i++) {
if(i%10==0){cout<<endl;} cout<<r[i]<<setw(6); } cout<<endl; } //主函数 void main() { int i,j,k; int r[N],a[N]; clock_t start, finish; double duration; cout<<"请选择排序方式,1、冒泡法；2、快速排序法；3、堆排序法；4、二路并归法"<<endl; cin>>j; srand((unsigned)time(NULL)); for(i=0;i<N;i++) { a[i]=rand()%10000; } switch(j) { case(1): { cout<<"冒泡法"; start = clock(); for(i=0;i<M;i++) {
int flag=1;//flag 为 0 停止排序 for(int i=1;i<n;i++) {
flag=0; for(int j=n-1;j>=i;j--)
if(r[j]<r[j-1]) {
int t=r[j]; r[j]=r[j-1]; r[j-1]=t; flag=1; } if(flag==0) return; } } //快速排序 void quicksort(int r[],int left,int right) { int i,j; int swap; i=left;j=right; swap=r[left]; while(i<j) { while((i<j)&&(swap<r[j]))j--; if(i<j) { r[i]=r[j]; i++; } while((i<j)&&(swap>r[i]))i++; if(i<j)
r1[j]=r[j]; } void mergesort(int r[])//二路并归总算法 {
int length=1; int r1[N+1]; while(length<N) {
mergepass(r,r1,length); length=2*length; mergepass(r1,r,length); length=2*length; } return;
} //二路归并 void merge(int r[],int r1[],int low,int mid,int high)//进行二合一的函数 {
int i=low,j=mid+1,k=low; while((i<=mid)&&(j<=high)) {
if(r[i]<=r[j]) r1[k++]=r[i++];
int i=0,j; while(i+2*length<=N) {
merge(r,r1,i,i+length-1,i+2*length-1); i=i+2*length; } if(i+length-1<N-1) merge(r,r1,i,i+length-1,N-1); else for(j=i;j<N;j++)